算术基本定理
N = p α 1 ∗ p α 2 ∗ . . . ∗ p α k N=p^{\alpha _{1}}*p^{\alpha _{2}}*...*p^{\alpha _{k}} N=pα1∗pα2∗...∗pαk
约数个数
( α 1 + 1 ) ∗ ( α 2 + 1 ) . . . ∗ ( α k + 1 ) (\alpha _{1}+1)*(\alpha _{2}+1)...*(\alpha _{k}+1) (α1+1)∗(α2+1)...∗(αk+1)
证明：
已知 N = p α 1 ∗ p α 2 ∗ . . . ∗ p α k N=p^{\alpha _{1}}*p^{\alpha _{2}}*...*p^{\alpha _{k}} N=pα1∗pα2∗...∗pαk
设 d = p β 1 ∗ p β 2 ∗ . . . ∗ p β k d=p^{\beta _{1}}*p^{\beta _{2}}*...*p^{\beta _{k}} d=pβ1∗pβ2∗...∗pβk，且 d d d是 N N N的一个约数，对于 [ β 1 , β k ] [\beta_{1},\beta_{k}] [β1,βk]的每一种取法， d d d都是 N N N的不同约数。
对于 β 1 \beta_{1} β1，可以取 [ 0 , α 1 ] [0,\alpha_{1}] [0,α1]，即存在 α 1 + 1 \alpha_{1}+1 α1+1种取法；对于 β 2 \beta_{2} β2，可以取 [ 0 , α 2 ] [0,\alpha_{2}] [0,α2]，即存在 α 2 + 1 \alpha_{2}+1 α2+1种取法；对于 β k \beta_{k} βk，可以取 [ 0 , α k ] [0,\alpha_{k}] [0,αk]，即存在 α k + 1 \alpha_{k}+1 αk+1种取法。
由乘法原理得，约数个数为 ( α 1 + 1 ) ∗ ( α 2 + 1 ) . . . ∗ ( α k + 1 ) (\alpha _{1}+1)*(\alpha _{2}+1)...*(\alpha _{k}+1) (α1+1)∗(α2+1)...∗(αk+1)
证毕。
约数之和
( p 1 0 + p 1 1 + . . . + p 1 α 1 ) ∗ ( p 2 0 + p 2 1 + . . . + p 2 α 2 ) ∗ . . . ∗ ( p k 0 + p k 1 + . . . + p k α k ) (p_{1}^0+p_{1}^1+...+p_{1}^{\alpha_{1}})*(p_{2}^0+p_{2}^1+...+p_{2}^{\alpha_{2}})*...*(p_{k}^0+p_{k}^1+...+p_{k}^{\alpha_{k}}) (p10+p11+...+p1α1)∗(p20+p21+...+p2α2)∗...∗(pk0+pk1+...+pkαk)
证明
已知 N = p α 1 ∗ p α 2 ∗ . . . ∗ p α k N=p^{\alpha _{1}}*p^{\alpha _{2}}*...*p^{\alpha _{k}} N=pα1∗pα2∗...∗pαk
( 1 ) (1) (1)计算 p α 1 p^{\alpha_{1}} pα1的约数之和，显然有 ( p 1 0 + p 1 1 + . . . + p 1 α 1 ) (p_{1}^0+p_{1}^1+...+p_{1}^{\alpha_{1}}) (p10+p11+...+p1α1)
( 2 ) (2) (2)计算 p α 2 p^{\alpha_{2}} pα2的约数之和，显然有 ( p 2 0 + p 2 1 + . . . + p 2 α 2 ) (p_{2}^0+p_{2}^1+...+p_{2}^{\alpha_{2}}) (p20+p21+...+p2α2)
…
(k)计算 p α k p^{\alpha_{k}} pαk的约数之和，显然有 ( p k 0 + p k 1 + . . . + p k α k ) (p_{k}^0+p_{k}^1+...+p_{k}^{\alpha_{k}}) (pk0+pk1+...+pkαk)
由乘法原理得，约数之和为 ( p 1 0 + p 1 1 + . . . + p 1 α 1 ) ∗ ( p 2 0 + p 2 1 + . . . + p 2 α 2 ) ∗ . . . ∗ ( p k 0 + p k 1 + . . . + p k α k ) (p_{1}^0+p_{1}^1+...+p_{1}^{\alpha_{1}})*(p_{2}^0+p_{2}^1+...+p_{2}^{\alpha_{2}})*...*(p_{k}^0+p_{k}^1+...+p_{k}^{\alpha_{k}}) (p10+p11+...+p1α1)∗(p20+p21+...+p2α2)∗...∗(pk0+pk1+...+pkαk)
证毕。
欧拉函数
设 φ ( N ) \varphi(N) φ(N)为 [ 1 , N ] [1,N] [1,N]中与 N N N互质的数的个数。
N N N可以分解质因数为 N = p α 1 ∗ p α 2 ∗ . . . ∗ p α k N=p^{\alpha _{1}}*p^{\alpha _{2}}*...*p^{\alpha _{k}} N=pα1∗pα2∗...∗pαk
存在公式 φ ( N ) = N ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p k ) \varphi(N)=N(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{k}}) φ(N)=N(1−p11)(1−p21)...(1−pk1)
证明
欧拉函数的证明使用容斥原理。
1. 1. 1.减去 p 1 , p 2 . . . p k p_{1},p_{2}...p_{k} p1,p2...pk的倍数的个数，即 N p i \frac{N}{p_{i}} piN
2. 2. 2.加上 p i ∗ p j p_{i}*p_{j} pi∗pj的倍数的个数，即 N p i ∗ p j \frac{N}{p_{i}*p_{j}} pi∗pjN
3. 3. 3.减去 p i ∗ p j ∗ p k p_{i}*p_{j}*p_{k} pi∗pj∗pk的倍数的个数，即 N p i ∗ p j ∗ p k \frac{N}{p_{i}*p_{j}*p_{k}} pi∗pj∗pkN
. . . ... ...
得到： N − N p i + N p i ∗ p j . . . N-\frac{N}{p_{i}}+\frac{N}{p_{i}*p_{j}}... N−piN+pi∗pjN...，化简得 N ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p k ) N(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{k}}) N(1−p11)(1−p21)...(1−pk1)。
证毕。
欧拉定理
若 a a a与 n n n互质，则 a ϕ ( n ) ≡ 1 a^{\phi_{(n)}}{\equiv}1 aϕ(n)≡1 ( m o d mod mod n n n)
证明
设 [ 1 , n ] [1,n] [1,n]中与 n n n互质的数分别为 a 1 , a 2 . . . a ϕ ( n ) a_{1},a_{2}...a_{\phi_(n)} a1,a2...aϕ(n)。由于 a a a与 n n n互质，所以 a ∗ a 1 , a ∗ a 2 . . . a ∗ a k a*a_{1},a*a_{2}...a*{a_k} a∗a1,a∗a2...a∗ak也分别与 n n n互质，且互不相同。
关于互不相同的证明
假设 a ∗ a 1 与 a ∗ a 2 a*a_{1}与a*a_{2} a∗a1与a∗a2相同，则有如下式子
a ∗ a 1 ≡ a ∗ a 2 a*a_{1} {\equiv}a*a_{2} a∗a1≡a∗a2 ( m o d mod mod n n n)
a ( a 1 − a 2 ) ≡ 0 a(a_{1}-a_{2}) {\equiv} 0 a(a1−a2)≡0 ( m o d mod mod n n n）
a 1 − a 2 ≡ 0 a_{1}-a_{2} {\equiv} 0 a1−a2≡0 ( m o d mod mod n n n)
a 1 = a 2 a_{1}=a_{2} a1=a2
与 ϕ ( n ) \phi_{(n)} ϕ(n)的定义矛盾，故 a ∗ a 1 , a ∗ a 2 . . . a ∗ a k a*a_{1},a*a_{2}...a*{a_k} a∗a1,a∗a2...a∗ak互不相同
整理得以下式子
a ∗ a 1 , a ∗ a 2 . . . a ∗ a k ≡ a 1 , a 2 . . . a ϕ ( n ) a*a_{1},a*a_{2}...a*{a_k} {\equiv} a_{1},a_{2}...a_{\phi_(n)} a∗a1,a∗a2...a∗ak≡a1,a2...aϕ(n) ( m o d mod mod n n n)
a ϕ ( n ) ∗ ( a 1 , a 2 . . . a ϕ ( n ) ) ≡ a 1 , a 2 . . . a ϕ ( n ) a^{\phi_{(n)}}*(a_{1},a_{2}...a_{\phi_{(n)}}) {\equiv} a_{1},a_{2}...a_{\phi_(n)} aϕ(n)∗(a1,a2...aϕ(n))≡a1,a2...aϕ(n) ( m o d mod mod n n n)
a ϕ ( n ) ≡ 1 a^{\phi_{(n)}}{\equiv} 1 aϕ(n)≡1 ( m o d mod mod n n n)
证毕。
费马小定理
a p − 1 ≡ 1 a^{p-1}{\equiv}1 ap−1≡1 ( m o d mod mod p p p)
证明
见欧拉定理的证明过程
