• 数论基础4
  • 欧拉函数
    • 欧拉函数的性质
    • 求欧拉函数
  • 欧拉定理
  • 费马小定理(欧拉特例)

数论基础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}$