数论基础4
欧拉函数
欧拉函数的计算结果是小于等于n且与n互素的正整数的个数 \(e.g.φ(8)=4\) 小于等于n且与n互素的正整数的个数：1,3,5,7
欧拉函数的性质
- p和q均为素数
- p为素数，k为正整数
- 若gcd(a,b)=1,则
求欧拉函数
求解思路，大数字通过素数唯一分解定理分解成小数字
再利用知识求解 \(\begin{array}{l}{\varphi(3000)} \\ {=\varphi\left(3 \times 2^{3} \times 5^{3}\right)} \\ {=\varphi(3) \times \varphi\left(2^{3}\right) \times \varphi\left(5^{3}\right)} \\ {=(3-1) \times 2^{2} \times \varphi(2) \times 5^{2} \times \varphi(5)} \\ {=2 \times 4 \times 1 \times 25 \times 4=800}\end{array}\)
欧拉定理
设n≥2，如果gcd(a,n)=1，则（…..模n=1） \(a^{\varphi(n)} \equiv 1(\bmod n)\) 同理有， \(a^{\varphi(n)+1} \equiv 1(\bmod n)\) e.g. \(\begin{array}{l}{\varphi(15)=\varphi(3) \times \varphi(5)=2 \times 4=8} \\ {4^{8}, 7^{8}, 11^{8} \equiv 1(\bmod 15)}\end{array}\) e.g. \(\begin{array}{l}{13^{\varphi(60)} \equiv 1(\bmod 60)} \\ {\varphi(60)=\varphi\left(2^{2}\right) \times \varphi(3) \times \varphi(5)=2 \times 2 \times 4=16} \\ {13^{16} \equiv 1(\bmod 60)} \\ {13^{2001}=13^{16 \times 125+1}=13(\bmod 60)} \\ {13^{2001} \bmod 60=13}\end{array}\)
费马小定理(欧拉特例)
若p是素数，且gcd(a,p)=1，则（…..模n=1） \(a^{p-1} \equiv 1(\bmod p)\) 同理有， \(a^{p} \equiv a(\bmod p)\) e.g. \(\begin{array}{l}{\operatorname{gcd}(310,199)=1} \\ {310^{19-1} \equiv 1\left(\bmod _{1} 199\right)} \\ {310^{198} \bmod 199=1}\end{array}\)