数论基础

呃呃，群论有部分涉及数论

居然还有辗转相除的事情吗。。

后面看情况单独拎一章

欧几里得算法

又称辗转相除法。

$$设a，b的公约数为d \\ d \mid a，d \mid b \\ 设a = kd + c\\ \frac{a}{d} = k + \frac{c}{d} \\ 由d \mid a得d \mid c \\ 所以d是b，a \mod b的公约数 \\ 下面证明最大公约数\\ 由于 a\mod b \lt b \\ 所以c单调递减 \\ 所以欧几里得算法收敛 \\ 所以欧几里得算法得到的第一个整除结果为最大公约数$$

最大公约数的性质

$$\gcd(a，b)=d \iff \gcd(a/d，b/d) = 1$$

证明略

贝祖定理（同余逆元性质）

$$(a,b) = 1 \iff \exist k \in \mathbb{Z}, ak \equiv 1 \pmod b$$