数论入门:四大定理之欧拉定理与费马小定理

数论四大定理

Ⅰ.威尔逊定理

Ⅱ.欧拉定理

Ⅲ.孙子剩余定理

Ⅳ.费马小定理

欧拉定理

内容

对于整数n,a且n,a互质则有
$a^{φ（n）}≡ 1（\mod n）$
其中$φ（n）$为n的欧拉函数值

欧拉函数

百度百科

$φ(n)$为小于n的正整数种与n互质的数的数目。

证明

要证$a^{φ(n)}≡ 1（\mod n）$只要证明$a^{φ（n)}-1≡ 0（\mod n）$
接下来我们先将这$φ(n)$个数按顺序排列，设排列后得到：
$x_1,x_2……x_{φ(n)} $

再者，我们令

$m_1=a_{x_1},m_2=a_{x_2}……m_{φ(n)} = a_{φ(n)} $

最后分两步证明：

Ⅰ.证明$m_1,m_2……m_{φ(n)} $中两两不同余n

Ⅱ.证明$m_1,m_2……m_{φ(n)} $中的所有数取模n得到的结果$r_1,r_2……r_ {φ(n)}$与n互质

证明Ⅰ

正面证明不方便，于是考虑反正法：

假设从中任取两个数$m_x,n_y$，有$m_x≡ m_y（\mod n）$

则设$m_x > m_y$,那么$m_x-m_y≡0(\mod n)$,

也就是$a\times (x_x-x_y)≡0(\mod n)$,

由于$x_x < n 且 x_y < n$，所以$x_x-x_y < n$，

显然$x_x-x_y$与n互质。所以$a≡0(\mod n)$显然矛盾。

证毕

证明Ⅱ

同样使用反正法

设其中某个数$m_t$的余数$r_t$与n有公因子q,

设$a\times x_t=p\times n+R$

$R=q\times i$

$n=q\times j$

则$a\times x_t=p\times n+q\times i$

则$a\times x_t=q\times (p\times j+i)$

因为q是n的一个因子，所以从此式可以得到$a\times x_t≡0 (\mod n)$显然矛盾

所以得证

总结

所以$m_1,m_2……m_{φ(n)} $中对n取模得到的值包含于$x_1,x_2……x_{φ(n)} $中。

则$m_1\times m_2……\times m_{φ(n)}≡x_1\times x_2\times ……\times x_{φ(n)} (\mod n)$

于是令$k=x_1\times x_2\times ……\times x_{φ(n)}$.

则原式为$a_{φ(n)}\times k≡k(\mod n)$

得到$k\times (a_{φ(n)}-1)≡0(\mod n)$

由于k显然与n互质,所以$ (a_{φ(n)}-1)≡0(\mod n)$

证明完毕

性质

1.对于质数p，$φ(p)=p−1$。

2.若p为质数，$n=p^k$
，则$φ(n)=p^k-p^{k-1}$ 。

3.欧拉函数是积性函数，但不是完全积性函数。若m,n互质，则$φ(m∗n)=φ(m)∗φ(n)$ 。特殊的，当$m=2$，n为奇数时，$φ(2*n)=φ(n)$。

4.当$n > 2$时，$φ(n)$是偶数。

5.小于n的数中，与n互质的数的总和为：$φ(n) * n / 2 (n < 1)。$

6.$n=∑_{d∣n}φ(d) $，即n的因数（包括1和它自己）的欧拉函数之和等于n。

证明略，详见欧拉函数性质原地址

代码

求单个数n的欧拉函数值

//实践复杂度为O(sqrt(n))
LL oula(LL n)
{
	LL ans=n;
	for(LL i=2;i*i<n;i++)
	{
		if(!n%i)//找n的因子
		{
			ans=ans/i*(1-i);
			while(!n%i)//利用唯一分解定理
			{
				n/=i;
			}
		}
	}
	if(n>1)ans=ans/n*(n-1);
	return ans;
}

求n个数的欧拉函数值打表

//时间复杂度为O(n)
#include<cstdio>
using namespace std;
const int N = 1e6+10 ;
int phi[N], prime[N];
int tot;//tot计数，表示prime[N]中有多少质数 
void Euler(){
    phi[1] = 1;
    for(int i = 2; i < N; i ++){
        if(!phi[i]){
            phi[i] = i-1;
            prime[tot ++] = i;
        }
        for(int j = 0; j < tot && 1ll*i*prime[j] < N; j ++){
            if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j]-1);
            else{
                phi[i * prime[j] ] = phi[i] * prime[j];
                break;
            }
        }
    }
}
 
int main(){
    Euler();
}

费马小定理

内容

对于一个素数p，另一个不是p的倍数的整数a，有$a^{(p-1)}≡1(\mod p)$

证明

显然由于p为素数，那么所有小于p的数，都与p互质，则$φ(p)=p-1$，那么由欧拉定理得证费马小定理。

费马小定理引理

在ACM中费马小定理本身使用的不如他的引力平凡，下面介绍一条费马小定理的引理：

内容

若正整数$a,n$互质，那么对于任意正整数$b$，有$a^b≡a^{b mod φ(n)}(\mod n)$

证明

我们先将原式进行变形：

$a^{b-b\mod φ(n)}\times a^{b mod φ(n)}≡a^{b mod φ(n)}(\mod n)$

于是得到

$a^{b-b\mod φ(n)}≡1(\mod n)$

于是我们只需要证明上式成立即可。

由于$(b-b\mod φ(n))|φ(n)$（因为b可以表示为$b=q\times φ(n)+b\mod φ(n)$）,于是我们设$(b-b\mod φ(n))=q\times φ(n)$,则有$a^{q\times φ(n)}≡1(\mod n)$,即$a^{q^{φ(n)}}≡1(\mod n)$

由于a与n互质，那么$a^{q}$与n互质，所以由费马小定理得，上式成立。

证明完毕。