初等数论入门 Lesson 1

整除

$b \mid a$ 等价于 $a = bq$ 等价于 $a\bmod b = 0$，读作 $b$ 整除 $a$。

除法算式定理

定理：设 $a,b \in \mathbb{Z},\ b>0$，则存在唯一的整数对 $(q,r)$，满足：

$$a = bq + r,\quad 0 \le r < b$$

gcd-lcm 关系

$$\gcd(a,b)\cdot \operatorname{lcm}(a,b)=|ab|$$

欧几里得算法

$$\gcd(a,b)=\gcd(b,a\bmod b)$$

证明：

若 $d\mid a$ 且 $d\mid b$， 则 $d\mid (a-bq)=r$

贝祖定理

设 $a,b \in \mathbb{Z}$，不全为 $0$，令 $d = \gcd(a,b)$。

则存在整数 $x,y$，使得

$$ax + by = d$$

这对 $(x,y)$ 称为贝祖系数（Bézout 系数）。

贝祖定理强调的是必然存在的问题。

同时 $\gcd(a,b)$ 也是 $ax+by$ 能表示出来的最小正整数

推论：

1. $ax+by=1$ 有解，则 $\gcd(a,b)=1$
2. $ax+by=c$ 有解，则 $\gcd(a,b)\mid c$

扩展欧几里得算法

求解 $ax+by=d$，$d=\gcd(a,b)$

1. 若 $b = 0$，此时 $a=d$

则对于 $ax+0\cdot y = a$ 的解为 $(1,0)$

2. 否则我们可以先求出 $bx'+(a\bmod b)y'=d$ 的 $(x',y')$

然后上面式子可以化简成 $ay'+b(x'-\lfloor\frac a b\rfloor y')=1$。

不定方程求解

求解 $ax+by=c$

1. 判断是否有解 $c\mid \gcd(a,b)$
2. 求解 $ax_0+by_0=d$
3. 其中一个解：$x=x_0\frac c d$
4. 通解：$x'=x-\frac b d k$，$y'=y+\frac a dk$