大家好，欢迎来到IT知识分享网。
欧拉定理：当 a a a与 n n n互质时，有 a ϕ ( n ) ≡ 1 m o d n a^{\phi(n)}\equiv 1\mod n aϕ(n)≡1modn
通项公式及其证明：
如果 n = p k n=p^k n=pk， p p p为质数，则 ϕ ( p k ) = p k − p k − 1 \phi(p^k)=p^k-p^{k-1} ϕ(pk)=pk−pk−1
证明：当一个数不包含质因子 p p p时就能与 n n n互质，小于等于 n n n的数中包含质因子p的只有 p k − 1 p^{k-1} pk−1个，即 p , 2 ∗ p , . . . , p k − 1 ∗ p p,2*p,…,p^{k-1}*p p,2∗p,...,pk−1∗p，把他们去除即可
由唯一分解定理可知， n = p 1 a 1 p 2 a 2 . . . p k a k n=p_{1}^{a_1}p_{2}^{a_2}…p_{k}^{a_k} n=p1a1p2a2...pkak
ϕ ( n ) = ϕ ( p 1 a 1 ) ϕ ( p 2 a 2 ) . . . ϕ ( p k a k ) = p 1 a 1 ( 1 − 1 p 1 ) p 2 a 2 ( 1 − 1 p 2 ) . . . p k a k ( 1 − 1 p k ) = n ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p k ) \begin{aligned} \phi(n) &=\phi(p_{1}^{a_1})\phi(p_{2}^{a_2})…\phi(p_{k}^{a_k})\\ &=p_{1}^{a_1}(1-\frac{1}{p_1})p_{2}^{a_2}(1-\frac{1}{p_2})…p_{k}^{a_k}(1-\frac{1}{p_k})\\ &=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k}) \end{aligned} ϕ(n)=ϕ(p1a1)ϕ(p2a2)...ϕ(pkak)=p1a1(1−p11)p2a2(1−p21)...pkak(1−pk1)=n(1−p11)(1−p21)...(1−pk1)
这就是欧拉函数的通项公式
欧拉定理证明：
设 A = { x 1 , x 2 , . . . , x ϕ ( n ) } A=\left\{x_1,x_2,…,x_{\phi(n)}\right\} A={
x1,x2,...,xϕ(n)}是 1 − n 1-n 1−n中与 n n n互质的数的集合
则他们模 n n n两两不相同，且余数与 n n n互质
下面我们证明 B = { a x 1 , a x 2 , . . . , a x ϕ ( n ) } B=\left\{ax_1,ax_2,…,ax_{\phi(n)}\right\} B={
ax1,ax2,...,axϕ(n)}也有这两个性质
模 n n n两两不相同：反证法，设 i ! = j i!=j i!=j且 a x i ≡ a x j m o d n ax_i\equiv ax_j\mod n axi≡axjmodn，即 a ( x i − x j ) ≡ 0 m o d n a(x_i-x_j)\equiv 0\mod n a(xi−xj)≡0modn
由于 a a a与 n n n互质，且 ( x i − x j ) (x_i-x_j) (xi−xj)不可能是 n n n的倍数，所以不可能存在这样的 i i i和 j j j。
余数都与 n n n互质：因为 a a a与 n n n互质， x i x_i xi与 n n n互质，所以 a x i ax_i axi也与 n n n互质， a x i ax_i axi模 n n n后也与 n n n互质。
所以 B B B这个集合模 n n n后一定是 ϕ ( n ) \phi(n) ϕ(n)个两两不同且与 n n n互质的数，即为 A A A
∏ i = 1 ϕ ( n ) a x i ≡ ∏ i = 1 ϕ ( n ) x i ( m o d n ) ⟶ a ϕ ( n ) ∏ i = 1 ϕ ( n ) x i ≡ ∏ i = 1 ϕ ( n ) x i ( m o d n ) ⟶ a ϕ ( n ) ≡ 1 ( m o d n ) \displaystyle\prod_{i=1}^{\phi(n)}ax_i\equiv\displaystyle\prod_{i=1}^{\phi(n)}x_i(\mod n)\longrightarrow a^{\phi(n)}\displaystyle\prod_{i=1}^{\phi(n)}x_i\equiv\displaystyle\prod_{i=1}^{\phi(n)}x_i(\mod n)\longrightarrow a^{\phi(n)}\equiv 1(\mod n) i=1∏ϕ(n)axi≡i=1∏ϕ(n)xi(modn)⟶aϕ(n)i=1∏ϕ(n)xi≡i=1∏ϕ(n)xi(modn)⟶aϕ(n)≡1(modn)
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/151432.html
