一些基礎數論的知識和證明

算識訓本定理

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?p1?1?)(1?p2?1?)...(1?pk?1?)

證明

歐拉函式的證明使用容斥原理，
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}} pi?N?
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??pj?N?
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??pk?N?
. . . ... ...
得到： N ? N p i + N p i ? p j . . . N-\frac{N}{p_{i}}+\frac{N}{p_{i}*p_{j}}... N?pi?N?+pi??pj?N?...，化簡得 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?p1?1?)(1?p2?1?)...(1?pk?1?)，
證畢，

歐拉定理

若 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)

證明

見歐拉定理的證明程序