数论基础H
威尔逊定理
判定整数 \(p\) 为质数的充分必要条件是：
充分性证明：当 \(p\) 不为质数时
-
\(p\) 可以被表示为完全平方数，即 \(p=k^2\)
当 \(k>2\) 时，显然有 \(2k<p=k^2\)，则 \((p-1)!=1\times2\times\cdots\times k\times \cdots \times 2k\times\cdots \times (p-1)\)
提出 \(k,2k\) 得 \((p-1)!=k^2\times \alpha=p\times \alpha\) ，那么 \((p-1)!\equiv 0(\mathrm{mod}\ p)\)
-
\(p\) 不是完全平方数，即 \(p=a\times b\ (a\ne b)\)
令 \(1<a<b<p\) ，则 \((p-1)!=1\times2\times\cdots\times a\times \cdots \times b\times\cdots \times (p-1)\)
提出 \(a,b\) 得 \((p-1)!=a\times b\times \alpha=p\times \alpha\) ，那么 \((p-1)!\equiv 0(\mathrm{mod\ }p)\)
必要性证明：当 \(p\) 为质数
质数 \(p\) 的简化剩余系为 \(\{1,2,\cdots,(p-1)\}\) ，模意义下的逆元形式为 \(ax\equiv 1(\mathrm{mod\ }p)\)
引理：对于模 \(m\) 的简化剩余系中每个元素 \(a\) 都存在唯一元素 \(x\)（也在同一简化剩余系内） 满足 \(ax\equiv 1(\mathrm{mod\ }m)\)
-
当 \(a=x\) 时，有 \(x^2 \equiv 1(\mathrm{mod\ }p)\) ，分解得到 \((x-1)(x+1)\equiv 0(\mathrm{mod\ }p)\) 。则 \(a=x=1,(p-1)\)
-
当 \(a\ne x\) 时，满足 \(ax\equiv 1(\mathrm{mod\ }p)\) 的 \((a,x)\) 从 \([2,p-2]\) 的集合中取得，必然存在 \(\frac{p-3}{2}\) 对不同的 \((a,x)\) 使得同余式成立
即 \((p-2)!\equiv 1(\mathrm{mod\ }p)\)
\((p-2)!\equiv 1 (\mathrm{mod}\ p)\) 在同余式两侧都乘上 \(p-1\) 后，有 \((p-1)!\equiv 1(\mathrm{mod\ }p)\) ，证毕
推论：
- 若正整数 \(p\) 为质数，则 \((p-1)!+1\equiv 0(\mathrm{mod\ }p)\)
- 若正整数 \(p\) 为大于 \(4\) 的合数，则 \((p-1)!\equiv 0(\mathrm{mod\ }p)\)
裴蜀定理
对于给定的整数 \(a,b\) 一定存在整数 \(x,y\) 满足等式
证明：
设正整数 \(x,y,a,b\) 有 \(ax+by\) ，设 \(x=x_0,y=y_0\) 时有等式 \(ax+by=s\) ，其中 \(s\) 为满足等式的最小正整数
-
显然存在整除关系：\(\mathrm{gcd}(a,b)\mid ax_0\ ,\ \mathrm{gcd}(a,b)\mid by_0\)，则 \(\mathrm{gcd}(a,b)\mid s\) 也成立
-
设 \(a=qs+r(0\le r<s)\) 即 \(a\) 通过 \(s\) 的除法余数表示，那么有：
\[r=a-qs=a-q(ax_0+by_0)\\ \implies r=a(1-qx_0)+b(-qy_0) \]因为 \(q\) 为整数，所以 \((1-qx_0),(-qy_0)\) 也都为整数，那么对于相同的 \(a,b\) 上述等式可以被改写为
\[ r=a(1-qx_0)+b(-qy_0)=ax_1+by_1 \]那么 \(r\) 也为形如 \(ax+by=s\) 的数，因为 \(s\) 是最小正整数解，那么 \(r=0\)
所以 \(a=qs\) ，则 \(s\mid a\) ，同理得到 \(s\mid b\) ，故 \(s\mid \mathrm{gcd}(a,b)\)
\(\mathrm{gcd}(a,b)\mid s,s\mid \mathrm{gcd}(a,b)\) 同时成立当且仅当 \(s= \mathrm{gcd}(a,b)\) ，证毕
特别的 ，当 \(a,b\) 有负数时，计算的 \(\mathrm{gcd}(a,b)\) 也为负数，但由于正负性不改变解，所以可以直接取绝对值计算
推广定理：
- 对于给定的整数 \(a,b\) 一定存在整数 \(x,y\) 满足 \(ax+by=\mathrm{gcd}(a,b)\times n\) ，\(n\) 为正整数
- 对于给定的整数集合 \(A\) ，一定存在整数 \(X\) 集合满足 \(\sum A_iX_i=\mathrm{gcd}(A_1,A_2,\cdots,A_n)\)