7. 数论四大定理（威尔逊定理、欧拉定理、费马小定理、孙子定理）

一、准备工作

查看数论基础知识

二、威尔逊定理

威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。但是由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大。

1. 定理及其变形

当且仅当p为素数时，( p -1 )! ≡ -1 ( mod p )
当且仅当p为素数时，( p -1 )! ≡ p-1 ( mod p )
若p为质数，则p能被(p-1)!+1整除
当且仅当p为素数时，p∣(p−1)!+1

2. 例题

hdu 2973 YAPTCHA

题解分析

三、欧拉定理（费马-欧拉定理）（Euler Theorem）

1. 定理

若n,a为正整数，且n,a互质，即gcd(a,n) = 1，则 $a^{φ(n)} ≡ 1 (mod\space n)$

2. 欧拉定理拓展

将欧拉定理拓展到A和C不互质的情况：
在这里插入图片描述

3. 举例

例1：（验证定理是否与结果相符）
令a = 3，n = 5，这两个数是互素的。
比5小的正整数中与5互素的数有1、2、3和4，所以φ(5)=4。
计算: $a^{φ(n)}$ = $3^4$ = 81，而 $\space81=80+1\equiv1(mod\space5)$ 。
与定理结果相符。

例2：（实现简化幂的模运算）
计算 $7^{222}$ 的个位数。
解：
实际是求 $7^{222}$ 被10除的余数。
因为7和10互质，令a=7，n=10，则据欧拉函数公式易得：φ(10)=4。
由欧拉定理知： $7^4\equiv1(mod\space10)$ 。
$\therefore$
$\begin{aligned} 7^{222}(mod\space10)&=[(7^4)^{55}*(7^2)](mod\space10)\\ &=[(7^4)^{55}(mod\space10)]*[(7^2)(mod\space10)]\\ &=1^{55}*[7^2(mod\space10)]\\ &=49(mod\space10)\\ &=9(mod\space10)\end{aligned}$ 。
于是该 $7^{222}$ 的个位数就是9。

总结：
利用欧拉定理来简化幂模运算： $a^x≡a^{x\%φ(m)}(mod\space m)$

4. 例题

hdu 1395 2^x(mod n) = 1

题解分析

四、费马小定理（Fermat’s little theorem）

1. 定理及其变形

$对任意a和任意质数p，有a^p\equiv a(mod\space p)$

$对任意a和任意质数p，当a与p互质时，有a^{p-1}\equiv 1(mod\space p)$

$若p能被a整除，则a^{p-1} ≡0(mod\space p)$

2. 举例

计算 $2^{100}$ 除以 13 的余数：

设a=2，p=13，正好满足gcd(a,p)=1。可以利用费马小定理： $a^{p-1}\equiv 1(mod\space p)$ 。

$\therefore 2^{13-1}=1(mod\space 13)\Rightarrow2^{12}=1(mod\space 13)$

解：

$\begin{aligned} 2^{100}(mod\space 13)&=2^{12\times8+4}(mod\space 13)\\ &=[(2^{12})^8\cdot2^4](mod\space 13)\\ &=[(2^{12})^8(mod\space 13)]\cdot[2^4(mod\space 13)]\\ &=1^8\cdot[16(mod\space 13)]\\ &=3\end{aligned}$

3. 例题

hdu 4196 Remoteland

题解分析

五、孙子定理（中国剩余定理）

1. 定理及其变形

中国剩余定理说明：假设整数m1,m2, … ,mn两两互质，则对任意的整数：a1,a2, … ,an，方程组S有解，并可构造得出。
在这里插入图片描述

2. 基本公式的运用

中国剩余定理的孙子解法并没有什么高深的技巧，就是以下两个基本数学定理的灵活运用：

如果 a%b=c , 则有 (a+kb)%b=c (k为非零整数)。
如果 a%b=c，那么 (a*k)%b=kc (k为大于零的整数)。

3. 原理

4. 逆

求解中国剩余定理时，一般会用到逆。
逆实现的原理和代码总结可以参考这篇博客，非常全面！膜orz
逆的求法总结（3种基本方法+4种实现）

5. 孙子定理模版

【接口】
int CRT(int a[],int m[],int n);
复杂度：O(nlogm)，其中m和每个 $m_i$ 同阶。
输入：a，m——第i个方程表示为 $x\equiv a_i(mod\space m_i)$
$\space\space\space\space\space\space\space\space\space\space$ n——方程个数
输出：方程组在 $[0,\prod_{i=0}^{n-1}m_i)$ 中的解
调用外部函数：拓展欧几里得

【代码】

int CRT( int a[], int m[], int n )//中国剩余定理 { 
    int M = 1; for(int i=0;i<n;++i) M *= m[i]; int ret = 0; for(int i=0;i<n;++i) { 
    int x,y; int tm = M/m[i]; extend_gcd(tm,m[i],x,y);//调用外部函数：拓展欧几里得 ret = (ret+tm*x*a[i])%M; } return (ret+M)%M; }

6. 顺便附上拓展欧几里得模版

【接口】
int extend_gcd(int a,int b,int &x,int &y);
复杂度：O(logN)，其中N和a，b同阶
输入：a，b——两个整数
$\space\space\space\space\space\space\space\space\space\space$ &x，&y——引用，ax+by=GCD(a,b)的一组解
输出：a和b的最大公约数
调用后x，y满足方程ax+by=GCD(a,b)

【代码】

int extend_gcd( int a, int b, int &x, int &y )//函数返回a,b的最大公约数 { 
    if( b==0 ) { 
    x = 1; y = 0; return a; } else { 
    int r = extend_gcd(b,a%b,y,x); y -= x*(a/b); return r; } }

今天的文章 7. 数论四大定理（威尔逊定理、欧拉定理、费马小定理、孙子定理）分享到此就结束了，感谢您的阅读。

7. 数论四大定理（威尔逊定理、欧拉定理、费马小定理、孙子定理）

一、准备工作

二、威尔逊定理

1. 定理及其变形

2. 例题

三、欧拉定理（费马-欧拉定理）（Euler Theorem）

1. 定理

2. 欧拉定理拓展

3. 举例

4. 例题

四、费马小定理（Fermat’s little theorem）

1. 定理及其变形

2. 举例

3. 例题

五、孙子定理（中国剩余定理）

1. 定理及其变形

2. 基本公式的运用

3. 原理

4. 逆

5. 孙子定理模版

6. 顺便附上拓展欧几里得模版

相关推荐