数论四大定理
Ⅰ.威尔逊定理
Ⅲ.孙子剩余定理
欧拉定理
内容
对于整数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的欧拉函数值
1 | //实践复杂度为O(sqrt(n)) |
求n个数的欧拉函数值打表
1 | //时间复杂度为O(n) |
费马小定理
内容
对于一个素数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互质,所以由费马小定理得,上式成立。
证明完毕。
应用
于是我们就可以使用这个引理将求幂运算取模时的幂减小。