威尔逊定理

判定整数 $p$ 为质数的充分必要条件是：

$$ (p-1)!\equiv -1 (\mathrm{mod}\ 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$ 满足等式

$$ ax+by=\mathrm{gcd}(a,b) $$

证明：

设正整数 $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)$