0801数论

GCD & exGCD

首先我们考虑辗转相除法的过程，因为 \((a,b)=(b \bmod a,a)(0<a<b)\)，\((0,b)=b\)，所以我们就可以每次将 \(b\) 转化为严格更小的 \(b\) 的问题。归纳则得到答案。

现在我们考虑扩欧的过程，我们需要对 \(ax+by=1\) 找到一组解。那么我们实际上就是要对一个形如 \((a,b)\) 的问题找到答案。

我们考虑对两边除以 \(a\)，就变成 \(x+\lfloor \dfrac{b}{a}\rfloor y-r_1=0\)（商方程）且 \((b\bmod a)y+ar_1=1\)（\(r_1\) 用于配平余数小于 \(a\) 的条件）而假如我们能找到 \(by+ar_1=1\) 的解，也就可以表出 \(x=r_1-\lfloor \dfrac{b}{a}\rfloor y\)。而显然问题的规模和 \(\gcd\) 一样，是严格变小的。直到问题变成 \(0r_{n+1}+1r_{n}=1\)，就能直接 \(r_n=1\)。

同时我们发现，如果 \((a,b)\neq 1\)，则方程 \(ax+by=1\) 是无解的，这是显然的。因此引出贝祖定理：\(c=(a,b)\) 是方程 \(ax+by=c\) 有解的充要条件。

费马小定理

费马小定理：对素数 \(p\)，有 \(a^{p-1}\equiv 1(\bmod p)(0<a<p)\)。

考虑证明费马小定理。

引理：对素数 \(p\) 和 \(0<a<p\)，如果有 \(ab\equiv ac(\bmod p)\)，则 \(b\equiv c(\bmod p)\)。

考虑移项，\(a(b-c)\equiv 0(\bmod p)\)，即 \(p|a(b-c)\)，那么我们只需要说明 \(p|(b-c)\) 即可。

考虑证明 \(p|ab\)，\(p\) 为质数，\(0<a<p\)，则 \(p|b\)。如果证明了这个东西，就可以同时证明算术基本定理（唯一分解定理）。

于是我们考虑 \(p|k\) 等价于 \((p,k)=p\)，而显然 \((p,a)=1,(p,ab)=p\)。根据贝祖定理，如果 \((p,b)\neq p\)，\(px+by=p\) 是无解的。但是显然 \(y=a\) 时方程有解 \(x=\dfrac{p-ab}{p}\)。存在矛盾。得 \((p,b)=p\)，即 \(p|b\)。

因此上面的内容迎刃而解。

考虑第一种证明，设 \(1\) 到 \(p-1\) 的所有数在集合 \(S\) 中，那么这个集合的乘积就是 \((p-1)!\)。现在我们给 \(S\) 中每个数乘上 \(a\) 形成集合 \(T\)。这里面的乘积是 \((p-1)!a^{p-1}\)。只要证明 \(S=T\)，则可以根据上面的引理得到费马小定理。

考虑若 \(ax\equiv ay(\bmod p)\)，\(x\equiv y(\bmod)\)，所以 \(T\) 中数两两不同。但是其元素个数和可选元素个数是 \(p-1\)，因此 \(1\) 到 \(p-1\) 每个数出现一次。得证。

考虑第二种证明。首先，我们从 \(a^0\) 开始，一定存在某个 \(0<k<p\)，使得 \(a^k\equiv 1(\bmod p)\)。

因为我们一共只有 \(p-1\) 个数可以选，所以根据抽屉原理，如果 \([1,p-1]\) 不出现 \(1\)，显然有 \(a^x\equiv a^y(\bmod p)(0<x<y<p)\)。但是我们有 \(a^{x}\cdot 1\equiv a^x\cdot a^{y-x}(\bmod p)\)，根据引理得到 \(a^{y-x}\equiv 1(\bmod p)\)。而显然 \(y-x<p\)。

但是我们只是证明了 \(p-1\) 的范围内存在 \(a^k\equiv 1(\bmod p)\)，没有证明 \(p-1\) 一定是这样的 \(k\)。

我们考虑从 \(a^0\) 开始，第一次出现 \(1\) 的位置是 \(a^k\)。而每次乘 \(a\) 所得到的必然是一个长度为 \(k\) 的周期。从任意的 \(a^x\) 开始，因为 \(a^k\) 是第一个 \(1\)，所以必然都是长度为 \(k\) 的周期。而且每一个不同的周期没有交集。

那么我们发现，所有的 \(p-1\) 个数被划分成了若干个长度为 \(k\) 的周期。所以 \(p-1\) 是 \(k\) 的倍数。

因此，\(p-1=nk\)，则 \(a^{p-1}\equiv a^{nk}\equiv (1)^n\equiv 1(\bmod p)\)。

同学说这就是群论的拉格朗日定理，不太清楚。