前言
小技巧
已知 (a*b equiv x*b ~(mod~p)) , 且 (gcd(b ,p)=1) ,则 (aequiv x~(mod~p))
证
移项 (b*(a-x) equiv 0~(mod~p)) 即 $(a-x)b=kp $ ,因为 (gcd(b,p)=1) ,所以 (b|k) , 所以 (a-x=p* dfrac {k}{b}) , 即 (a -xequiv 0~(mod~p)) , 所以 (a equiv x~(mod~p))
欧拉函数
1
当p是质数,显然 (varphi(p)=p-1)
2
当p是质数 , (varphi(p^k)=p^k-p^{k-1})，因为 (p)是质数，所以只有 (p) 的倍数与 (p) 不互质，也就是 (p'=p*K) , 而 (K) 的取值范围只有 (1sim p^{k-1}-1)，剩余的数都与 (p) 互质 , 所以小于 (p^k)的数有 $p^k -1 $ 个, 还有(p^{k-1}-1) 个与 (p) 不互质的数则
(varphi(p^k)=p^k-1-(p^{k-1}-1)=p^k-p^{k-1})
(建议3,4一起看)
3
当 (gcd(a,b)=1) 时 (varphi(a*b)=varphi(a)*varphi(b))
证
$varphi(a)=aprod(1-frac 1{p_i}) ,varphi(b)=bprod'(1-frac 1{p_i}) $
因为 (gcd(a,b)=1) , 所以 (prod(1-frac 1{p_i}))和(prod'(1-frac 1{p_i})) 可以合并 , (a*b=a*b) , 所以 (varphi(a*b)=varphi(a)*varphi(b))
4
当 (p=prod p_i^{k_i}) , ((p_i) 为 (p) 的质因子) 时 (varphi(p)=p*prod (1-frac{1}{p_i}))
证
由2知 (varphi(p)=prod(p_i^{k_i}-p_i^{k_i-1})) , 每项提出来一个 (p_i^{k_i}) 式子变为 $prod p_i^{k_i}* prod(1-frac{1}{p_i}) $
而 (prod p_i^{k_i}=p) , 所以(varphi(p)=p*prod (1-frac{1}{p_i}))
欧拉定理
已知 (a,p) 当 (gcd(a,p)=1) 时, (a^{varphi(p) } equiv 1~(mod~p))
证明
(p) 的剩余系为 (p_1,p_2~,~p_3~,~...~,~p_{varphi(p)}) , (p_i) 为与 (p) 互质的数
所有数同时乘 $a,(gcd(a,p)=1) $ 得
(p_1*a~,~p_2*a~,~p_3*a~,~...~,~p_{varphi(p)}*a)
(p_1*a~,~p_2*a~,~p_3*a~,~...~,~p_{varphi(p)}*a) 成为了一个 (p) 的剩余系
我们用反证法
假设(p_i*a equiv p_j*a~ (mod~p)) 且 $i
e j $,则 (a*(p_i-p_j) equiv 0) , 即 (a*k=p*k'), 因为 (gcd(a,p)=1) 所以 (a|k',p_i-p_j=p*frac {k'}{a}) , 即 (i =j) 与 (i
eq j) 矛盾
那么我们说 (prodlimits_{i=1}^{varphi(p)} p_i equiv prodlimits_{i=1}^{varphi(p)} (p_i*a)~(mod~p)) ,
将 (a) 提出
(prodlimits_{i=1}^{varphi(p)} p_i equiv prodlimits_{i=1}^{varphi(p)} p_i*a^{varphi(p)}~(mod~p))
根据小技巧
因为 (gcd(prodlimits_{i=1}^{varphi(p)} p_i, p)=1)
所以 (a^{varphi (p) } equiv 1~(mod~p))
证毕