数论四大定理

发表于 | 分类于

威尔逊定理、费马小定理、欧拉定理、中国剩余定理的简介与证明。

同余的性质

  1. 整除性: $a\equiv b:(mod: m)=>m|(a-b)$
  2. 传递性: $a\equiv b:(mod: m),: a\equiv c:(mod: m)=>b\equiv c:(mod: m)$
  3. 保持基本运算： $a\equiv b:(mod: m)=>\begin{cases}an\equiv bn:(mod: m) \ a^n\equiv b^n:(mod: m) \end{cases}$
  4. 放大缩小底数: $(km\pm a)^n\equiv (\pm a)^n:(mod: m)$
  5. 放大缩小模数: $a\equiv b:(mod: m)<=>ka\equiv kb:(mod: km)$
  6. 除法原理: $ka\equiv kb:(mod: m),k\perp m=>a\equiv b:(mod: m)$

威尔逊定理

  • 简介

    $p$是一个素数的充要条件为$(p-1)!\equiv -1(mod: p)$，这个定理给出了一种素数判断方法，不过阶乘增长速度较快，实际应用不可行。

  • 证明

    先证明$p$的剩余系$S$关于模$p$乘法构成群，网上的资料貌似很少证这个：

    1. $\forall a,b\in S$不难推出$ab\perp p=>ab:mod:p\perp p$，所以运算封闭。
    2. 单位元为1
    3. $\forall a\in S$，若$\exists x,ax\equiv 1:(mod:p)$，即方程$ax+py=1$有解，由于$a\perp p$，根据裴蜀定理可知有解。所以$a$的逆元存在。

    下面证明威尔逊定理：

    1. 充分性：若p不为素数，有$p|(p-1)!$，所以$(p-1)!\equiv 0(mod: p)$ ，这样就证明了p一定是素数。
    2. 必要性：取p的剩余系$S={1,2,..p-1 }$，由于它关于模p乘法是封闭的，所以对$\forall x,\exists y\in S,xy:mod:p=1$，显然这样的xy只有两种情况：$x=y,x\neq y$。当$x=y$时，解同余方程$x^2\equiv 1:(mod:p)$可得只有两个解$1,p-1$，所以除了这两个数剩下的两两都能配对，且乘积模p是1。所以$(p-1)!\equiv 1*(p-1) \equiv -1:(mod: p)$，必要性得证。

    证毕

费马小定理

  • 简介

    对于整数a，质数p，有$a^p\equiv a:(mod: p)$。特别的，当a不是p的倍数时，有$a^{p-1}\equiv 1:(mod: p)$，这个形式更加常用。

  • 证明

    构造两个集合：$A={ 1,2,…p-1},B={ ak|k\in A}$。下面证明B中的p-1个元素在模p意义下各不相同。

    若存在$ak_1,ak_2\in B$且$ak1\equiv ak_2:(mod: p)$，由于$a\perp p$根据同余的性质6可知$k_1=k_2$，这样就证明了B中p-1个元素在模p意义下互不相同，并且由于a不是p的整数倍，所以$ak: mod: p\neq 0$，所以B中元素在模p意义下正好就是A中的p-1个元素的重新排列。

    于是$1\ast2\ast…\ast(p-1)\equiv a\ast2a\ast…(p-1)a:(mod: p)$又因为$\prod_{i=1}^{p-1} i\perp p$， 再根据同余的性质6就得到了$a^{p-1}\equiv 1:(mod: p)$。

    证毕

  • 应用

    同余式的第二种形式两边同除以a，就得到了$a^{p-2}\equiv a^{-1}:(mod: p)$，这样就得到求a逆元的一种方法，并且比使用扩欧算法更为常用。

欧拉定理

  • 简介

    $\psi(x)$为欧拉函数，当$a\perp n$时，有$a^{\psi (n)}\equiv 1: (mod : n)$

  • 证明

    证明过程与费马小定理类似。构造一个n的简化剩余系(模m意义下与m互质的$\psi(m)$个数)$r_1,r_2…r_{\psi(m)}$，再构造$ar_1,ar_2…ar_{\psi(m)}$，不难证明$ar\perp m=>ar:mod: m\perp m$，再用类似费马小定理证明的方法可证$ar_i$模m意义下互不相同，这样就证明了构造的两组数列在模m意义下是相同的。

    于是$r_1\ast r_2\ast…r_{\psi(m)}\equiv ar_1\ast ar_2\ast…ar_{\psi(m)}(mod:m)$，化简可得$a^{\psi (n)}\equiv 1: (mod : n)$。

    证毕

  • 应用

    求$7^{222}$的个位数：由于$7\perp 10$，由欧拉定理$7^{\psi(10)}\equiv 7^4\equiv 1(mod:10)$，而$222=4*55+2$，所以$7^{222}\equiv 7^2\equiv 9(mod:10)$，所以个位数为9

  • 扩展欧拉定理

    $a^b\equiv \begin{cases} &a^{b:mod: \psi(p)}\qquad \qquad a\perp p
    &a^b\qquad \qquad \quad \qquad gcd(a,p)\neq 1且b<\psi(p)
    &a^{b:mod: \psi(p)+\psi(p)}\qquad gcd(a,p)\neq 1且b\geq \psi(p) \end{cases}$

    证明过程比较长，此处不证。

中国剩余定理

  • 简介

    中国剩余定理用于求解如下类型的方程组($n_1n_2…n_k$两两互素)

    $\qquad \begin{cases} &x\equiv a_1:(mod: n_1)
    &x\equiv a_2:(mod: n_2)
    &\quad …
    &x\equiv a_k:(mod: n_k)
    \end{cases}$

  • 求解过程

    1. 计算$n=\prod_{i=1}^k n_i$。
    2. 对于第$i$个方程：①计算$m_i=\frac{n}{n_i}$②计算$m_i$关于$n_i$的逆元$m_i^{-1}$ ③计算$c_i=m_i*m_i^{-1}$(不需要对$n_i$取模)
    3. 计算方程在模$n$下的唯一解$:a=\sum_{i=1}^k a_ic_i(mod:n)$

  • 应用

    计算$x:mod:p$时，如果p不是质数，并且p质因数分解后不含平方项因子，也就是说$p=p_1p_2…p_k$，那么可以分别计算x在k个质因数下的模，再用中国剩余定理求解如下方程：

    $\qquad \begin{cases} &x\equiv a_1:(mod: p_1)
    &x\equiv a_2:(mod: p_2)
    &\quad …
    &x\equiv a_k:(mod: p_k)
    \end{cases}$