初等數論簡明教程

本文給出初等數論中的一些重要的定理與例題，證明風格采用 整除線法 與命題節點法。

整除線法 指推理的第 $n$ 步左邊的字符可由前面左邊的字符得到，右邊的字符可由前面右邊的字符得到，整除線變成了推理線，既少寫了很多字，又對下一步推理有一定提示作用。

公共約定

$A = \{a_1, a_2, ..., a_n\} = a_j$
$L = [a_1, a_2, ..., a_n] = [a_j]$ （最小公倍數）
$D = (a_1, a_2, ..., a_n) = (a_j)$ （最大公約數）
$r$ ：余數
$f(a_j)$ ：集合 $A$ 所有元素均符合 $f(a_j)$
$L^{'}$ ：公倍數
$d$ ：公約數
${P_n\}$ ：素數列 $2, 3, 5, 7, 11, 13, ...$
$p_1^{\alpha_1} p_2^{\alpha_2} ... p_t^{\alpha_t}$

這些約定是本文的默認約定，優先級弱于具體題目中的約定。

約定

$\mid s_1$ ，
$∣s2\quad \mid s_2$ ： $a$ 同時整除 $s_1$ 和 $s_2$
$\mid$
$\mid s$ ： $a$ 和 $b$ 都整除 $s$
$\Rightarrow c$ ： $a$ 且 $b$ 推出 $c$

定理1：公倍數是最小公倍數的倍數

$aj∣L′?L∣L′a_j \mid L' \iff L \mid L'$

證明

（ $?\Leftarrow$ ）

$\mid L' \Rightarrow L' = kL$
$L = q_j a_j$
$q_j a_j \Rightarrow a_j \mid L'$

（ $?\Rightarrow$ ）

$L^{'} = q L + r$
$aj∣L′a_j \mid L'$
$∣L\quad \mid L$
$∣r<L\quad \mid r < L$
$∣r=0\quad \mid r = 0$
$\mid L'$

定理2：公約數是最大公約數的約數

$\mid a_j \iff d \mid D$

證明

（ $?\Leftarrow$ ）

$\mid D \Rightarrow D = k d$
$a_j = q_j D$
$aj=qjkd?d∣aja_j = q_j k d \Rightarrow d \mid a_j$

（ $?\Rightarrow$ ）

方法1

$D= a_1x_1+a_2x_2+...+a_kx_k （裴蜀定理）$
$d ∣ D$

方法2

: $L = [d, D] \to L \geq D$
$對 L = D 和 L > D 分類討論$
2.1 $d\mid D (可以)$
2.2 $L > D (排除這種情況)$
$|a_j \land D |a_j → L |a_j → L ≤ D (矛盾)$

定理3： $m(a_1, ..., a_k) = (ma_1, ..., ma_k)=$

令

$d=(a_1, ..., a_k)$
$D=(ma_1, ..., ma_k)$

則:
$\mid ma_j$
$Dm∣aj?Dm≤d\dfrac{D}{m} \mid a_j \Rightarrow \dfrac{D}{m} \leq d$
$d∣aj\quad d \mid a_j$
$\mid ma_j$
$∣D?md≤D\quad \quad \mid D \Rightarrow md \leq D$

定理4： $m[a_1, ..., a_k] = [ma_1, ..., ma_k]$

令

$L'=[a_1, ..., a_k]$
$L=[ma_1, ..., ma_k]$

則:
$maj∣Lma_j \mid L$
$aj∣Lm?L′≤Lm\quad a_j \mid \dfrac{L}{m} \Rightarrow L' \leq \dfrac{L}{m}$
$∣L′\quad \quad \mid L'$
$maj∣mL′?L≤mL′ma_j \mid mL' \Rightarrow L \leq mL'$

定理5：裴蜀定理

若 $\{ s \mid s > 0 \land s = a_1 x_1 + a_2 x_2 + \cdots + a_k x_k \}$ ，則

$D = (a_1, ..., a_k) = \min S$

$s_0 = \min S$
$\mid a_j \Rightarrow D \mid s_0$
$aj=qjs0+rj?rj∈S∧rj<s0?rj=0?s0∣aj?s0∣Da_j = q_j s_0 + r_j \Rightarrow r_j \in S \land r_j < s_0 \Rightarrow r_j = 0 \Rightarrow s_0 \mid a_j \Rightarrow s_0 \mid D$

定理6：一次同余方程

參見電樞公式

一次同余方程 $\equiv b \pmod n$ 有解的充要條件是 $a0∣ba_0 \mid b$ ，此時恰有 $a_0$ 個關于模 $n$ 不同余的解。

其中 $a_0 = (n, a)$ ， $a| = n / a_0$

證明

設 $x_0$ 是方程的一個特解，則 $x = x_0 + t|a|$ （ $t = 0, 1, ..., a_0-1$ ）也是解。
$\geq a_0$ 會導致模 $n$ 同余的解重復。
因為繞法 $a$ ，繞 $∣ a ∣$ 次會第一次回到起點，所以 $a(x0+∣a∣t)≡b(modn)a(x_0 + |a| t) \equiv b \pmod n$ 。

注意：

$\equiv b \pmod n$ 等價于 $a x ? b = n y$ 。
可用輾轉相除法找到 $x^{'}, n^{'}$ 滿足方程。

一次同余方程的規律

解的個數為最小繞數 $a_0$ 。
解就是與階同繞的可達點，向右偏移最小特解。
如果有解，則 $[0, ∣ a ∣)$ 中一定存在唯一一個最小特解，特別當 $a$ 是全達繞法時， $\sim n-1$ 一定存在一個唯一特解。
方程有解， $b$ 只能取 $a$ 的可達點。
方程 $a x + b y = c$ 的一個特解為 $cd(x0,y0)\frac{c}{d}(x_0, y_0)$ ，其中 $d = (a, b)$ ， $x_0, y_0)$ 可通過如下方式得到：

$(ab1001)→列變換(d0x0s0y0t0)\begin{pmatrix} a & b \\ \hline 1 & 0 \\ 0 & 1 \end{pmatrix} \xrightarrow{列變換} \begin{pmatrix} d & 0 \\ \hline x_0 & s_0 \\ y_0 & t_0 \end{pmatrix}$

$x_0, y_0, s_0, t_0, d)$ 滿足：

$(a, b) = d$
$x_0 + b y_0 = d \implies a \left( \frac{c}{d} x_0 \right) + b \left( \frac{c}{d} y_0 \right) = c$
$a s_0 + b t_0 = 0$
$(xy)=(x特y特)+k(s0t0)\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} x_{特} \\ y_{特} \end{pmatrix} + k \begin{pmatrix} s_0 \\ t_0 \end{pmatrix}$ ，其中 $(x特,y特)=cd(x0,y0)(x_{特}, y_{特}) = \frac{c}{d}(x_0, y_0)$

例1

求解 8x≡4(mod 12)

本該約去公因數4，但為說明解的個數，所以不這么做，|8|=3 從0~3 試根

x0=2為其特解,8的最小饒數為4,階是3，所以其非同余特解有4個,

為2+30,2+31,2+32，2+33

2,5,8,11

例2

解方程14x+105y=49

對矩陣解法稍做優化,下面兩個列變換可以寫到一起，節約紙張（2個連續列變換可寫在一起)

14 105

1 0

0 1

--------------c2-7c1---------------------

 7-71

--------------c1-2c2---------------------

-2

$(141051001)～(0715?7?21)\begin{pmatrix} 14 & 105 \\\\ 1 & 0 \\\\ 0 & 1 \end{pmatrix} \sim \begin{pmatrix} 0 & 7 \\\\ 15 & -7 \\\\ -2 & 1 \end{pmatrix}$

==> $x_0, y_0, s_0, t_0, d) = (-7, 1, 15, -2, 7)$

$(x特,y特)=cd(x0,y0)=497(?7,1)(x_{\text{特}}, y_{\text{特}}) = \frac{c}{d}(x_0, y_0) = \frac{49}{7}(-7, 1)$

可以觀察發現如果僅僅是為了解方程，第二個列變換是可以省略的，一個列變換就得到了 $d, x_0, y_0)$

例題

例1： $a^m - 1, a^n - 1) = a^{(m,n)} - 1$

令
$(m, n) = d = km ? s n$ ；
$a^m - 1, a^n - 1) = D$ ；

證明：

$ad?1∣a(m,n)?1∣am?1∣an?1∣Da^d - 1 \mid a^{(m,n)} - 1 \\ \quad\quad\quad \mid a^m - 1 \\ \quad\quad\quad \mid a^n - 1 \\ \quad\quad\mid D$

$D∣am?1∣an?1∣ans?1?(ns,D)=1∣akm?1∣akm?ans∣ans(akm?ns?1)∣ans(ad?1)∣ad?1D\quad\quad \mid a^m - 1 \\ \quad\quad\quad \mid a^n - 1 \\ \quad\ \quad\ \quad\ \quad\ \quad\quad \quad\quad\quad \mid a^{ns} - 1\Rightarrow(ns,D)=1 \\ \quad\quad\quad\quad \mid a^{km} - 1 \\ \quad\quad\quad\quad\quad \mid a^{km} - a^{ns} \\ \quad\quad\quad\quad\quad\quad\quad\quad \mid a^{ns}(a^{km-ns}-1) \\ \quad\quad\quad\quad\quad\quad \mid a^{ns}(a^d-1) \\ \quad\quad\quad\quad \mid a^d-1$

例2： $\implies m \nmid 2^m - 1$

證明思路：

$p$ 為 $m$ 的最小素因子
$(m, p ? 1) = 1$

$\mid 2^m-1 \quad (假設) \\ p \mid 2^m-1 \quad (P1) \\ \quad\quad\quad\quad \mid 2^{p-1}-1 \quad (歐拉公式) \\ \quad\quad\quad \mid 2^{(m,p-1)}-1 \quad (例1) \\ \quad\quad\quad\quad\quad\quad\quad \mid 1 \implies p=1 \quad (P3假設錯誤)$

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/91404.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/91404.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/91404.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！