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

数论四大定理

Ⅰ.威尔逊定理

Ⅱ.欧拉定理

Ⅲ.孙子剩余定理

Ⅳ.费马小定理

欧拉定理

内容

对于整数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)$