初等数论简明教程

本文给出初等数论中的一些重要的定理与例题，证明风格采用 整除线法 与 命题节点法。

整除线法 指推理的第 $n$ 步左边的字符可由前面左边的字符得到，右边的字符可由前面右边的字符得到，整除线变成了推理线，既少写了很多字，又对下一步推理有一定提示作用。

---

公共约定

• A={a1,a2,...,an}=ajA = \{a_1, a_2, ..., a_n\} = a_jA={a1​,a2​,...,an​}=aj​
• $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^{\prime }$：公倍数
• $d$：公约数
• {Pn}\{P_n\}{Pn​}：素数列 $2,3,5,7,11,13,...$
• $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}...p_t^{{\alpha }_t}$

这些约定是本文的默认约定，优先级弱于具体题目中的约定。

---

约定

• $a\mid s_1$，
  $\mid s_2$：$a$ 同时整除 $s_1$ 和 $s_2$
• $a\mid$
  $b\mid s$：$a$ 和 $b$ 都整除 $s$
• $a,b\Rightarrow c$：$a$ 且 $b$ 推出 $c$

---

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

$$a_j\mid L^{\prime }⟺L\mid L^{\prime }$$

证明

（$\Leftarrow$）

1. $L\mid L^{\prime }\Rightarrow L^{\prime }=kL$
2. $L=q_j{a}_j$
3. $L^{\prime }=k{q}_j{a}_j\Rightarrow a_j\mid L^{\prime }$

（$\Rightarrow$）

1. $L^{\prime }=qL+r$
2. $a_j\mid L^{\prime }$
   $\mid L$
   $\mid r<L$
   $\mid r=0$
3. $L\mid L^{\prime }$

---

定理2：公约数是最大公约数的约数

$$d\mid a_j⟺d\mid D$$

证明

（$\Leftarrow$）

1. $d\mid D\Rightarrow D=kd$
2. $a_j=q_{j}D$
3. $a_j=q_{j}kd\Rightarrow d\mid a_j$

（$\Rightarrow$）

方法1

1. $D=a_1{x}_1+a_2{x}_2+...+a_k{x}_k（裴蜀定理）$
2. $d|D$

方法2

1. : $$L=[d,D]\to L\ge D$$
2. $$对L=D和L>D分类讨论$$
   2.1 $$L=D\to d\mid D(可以)$$
   2.2 $$L>D(排除这种情况)$$
   $$d|a_j\wedge D|a_j\to L|a_j\to L\le D(矛盾)$$

定理3：$$m(a_1,...,a_k)=(m{a}_1,...,m{a}_k)=$$

---

令

• $d=(a_1,...,a_k)$
• $D=(m{a}_1,...,m{a}_k)$

则:
$D\mid m{a}_j$
$\frac{D}{m}\mid a_j\Rightarrow \frac{D}{m}\le d$
$d\mid a_j$
$md\mid m{a}_j$
$\mid D\Rightarrow md\le D$

---

定理4：$$m[a_1,...,a_k]=[m{a}_1,...,m{a}_k]$$

---

令

• $L^{\prime }=[a_1,...,a_k]$
• $L=[m{a}_1,...,m{a}_k]$

则:
$m{a}_j\mid L$
$a_j\mid \frac{L}{m}\Rightarrow L^{\prime }\le \frac{L}{m}$
$\mid L^{\prime }$
$m{a}_j\mid m{L}^{\prime }\Rightarrow L\le m{L}^{\prime }$

---

定理5：裴蜀定理

若 S={s∣s>0∧s=a1x1+a2x2+⋯+akxk}S = \{ s \mid s > 0 \land s = a_1 x_1 + a_2 x_2 + \cdots + a_k x_k \}S={s∣s>0∧s=a1​x1​+a2​x2​+⋯+ak​xk​}，则

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

• $s_0=\min S$
• $D\mid a_j\Rightarrow D\mid s_0$
• $a_j=q_j{s}_0+r_j\Rightarrow r_j\in S\wedge r_j<s_0\Rightarrow r_j=0\Rightarrow s_0\mid a_j\Rightarrow s_0\mid D$

定理6：一次同余方程

参见 电枢公式

一次同余方程 $ax\equiv b(\mathrm{mod}n)$ 有解的充要条件是 $a_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$）也是解。
• $t\ge a_0$ 会导致模 $n$ 同余的解重复。
• 因为绕法 $a$，绕 $|a|$ 次会第一次回到起点，所以 $a(x_0+|a|t)\equiv b(\mathrm{mod}n)$。

注意：

• $ax\equiv b(\mathrm{mod}n)$ 等价于 $ax-b=ny$。
• 可用辗转相除法找到 $x^{\prime },n^{\prime }$ 满足方程。

---

一次同余方程的规律

1. 解的个数为最小绕数 $a_0$。
2. 解就是与阶同绕的可达点，向右偏移最小特解。
3. 如果有解，则 $[0,|a|)$ 中一定存在唯一一个最小特解，特别当 $a$ 是全达绕法时，$0\sim n-1$ 一定存在一个唯一特解。
4. 方程有解，$b$ 只能取 $a$ 的可达点。
5. 方程 $ax+by=c$ 的一个特解为 $\frac{c}{d}(x_0,y_0)$，其中 $d=(a,b)$，$(x_0,y_0)$ 可通过如下方式得到：

$$\left(\begin{array}{cc}a& b\\ 1& 0\\ 0& 1\end{array}\right)\stackrel{列变换}{\to }\left(\begin{array}{cc}d& 0\\ x_0& s_0\\ y_0& t_0\end{array}\right)$$

$(x_0,y_0,s_0,t_0,d)$ 满足：

1. $(a,b)=d$
2. $a{x}_0+b{y}_0=d⟹a\left(\frac{c}{d}{x}_0\right)+b\left(\frac{c}{d}{y}_0\right)=c$
3. $a{s}_0+b{t}_0=0$
4. $\left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{c}{x}_{特}\\ y_{特}\end{array}\right)+k\left(\begin{array}{c}{s}_0\\ t_0\end{array}\right)$，其中 $(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---------------------

0

15

-2

---

$$\left(\begin{array}{cc}14& 105\\ & \\ 1& 0\\ & \\ 0& 1\end{array}\right)\sim \left(\begin{array}{cc}0& 7\\ & \\ 15& -7\\ & \\ -2& 1\end{array}\right)$$

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

$$(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-sn$；
$(a^m-1,a^n-1)=D$；

证明：

$$\begin{gathered} a^d-1\mid a^{(m,n)}-1 \\ \mid a^m-1 \\ \mid a^n-1 \\ \mid D \end{gathered}$$

$$\begin{gathered} D\mid a^m-1 \\ \mid a^n-1 \\ \mid a^{ns}-1\Rightarrow (ns,D)=1 \\ \mid a^{km}-1 \\ \mid a^{km}-a^{ns} \\ \mid a^{ns}(a^{km-ns}-1) \\ \mid a^{ns}(a^d-1) \\ \mid a^d-1 \end{gathered}$$

例2：$m>1⟹m\nmid 2^m-1$

证明思路：

1. $p$ 为 $m$ 的最小素因子
2. $(m,p-1)=1$

$$\begin{gathered} m\mid 2^m-1(假设) \\ p\mid 2^m-1(P1) \\ \mid 2^{p-1}-1(欧拉公式) \\ \mid 2^{(m,p-1)}-1(例1) \\ \mid 1⟹p=1(P3假设错误) \end{gathered}$$