算术基本定理
N=p^{alpha _{1}}*p^{alpha _{2}}*...*p^{alpha _{k}}
约数个数
(alpha _{1} 1)*(alpha _{2} 1)...*(alpha _{k} 1)
证明：
已知N=p^{alpha _{1}}*p^{alpha _{2}}*...*p^{alpha _{k}}
设d=p^{beta _{1}}*p^{beta _{2}}*...*p^{beta _{k}}，且d是N的一个约数，对于[beta_{1},beta_{k}]的每一种取法，d都是N的不同约数。
对于beta_{1}，可以取[0,alpha_{1}]，即存在alpha_{1} 1种取法；对于beta_{2}，可以取[0,alpha_{2}]，即存在alpha_{2} 1种取法；对于beta_{k}，可以取[0,alpha_{k}]，即存在alpha_{k} 1种取法。
由乘法原理得，约数个数为(alpha _{1} 1)*(alpha _{2} 1)...*(alpha _{k} 1)
证毕。
约数之和
(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}})
证明
已知N=p^{alpha _{1}}*p^{alpha _{2}}*...*p^{alpha _{k}}
(1)计算p^{alpha_{1}}的约数之和，显然有(p_{1}^0 p_{1}^1 ... p_{1}^{alpha_{1}})
(2)计算p^{alpha_{2}}的约数之和，显然有(p_{2}^0 p_{2}^1 ... p_{2}^{alpha_{2}})
...
(k)计算p^{alpha_{k}}的约数之和，显然有(p_{k}^0 p_{k}^1 ... p_{k}^{alpha_{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}})
证毕。
欧拉函数
设varphi(N)为[1,N]中与N互质的数的个数。
N可以分解质因数为N=p^{alpha _{1}}*p^{alpha _{2}}*...*p^{alpha _{k}}
存在公式varphi(N)=N(1-frac{1}{p_{1}})(1-frac{1}{p_{2}})...(1-frac{1}{p_{k}})
证明
欧拉函数的证明使用容斥原理。
1.减去p_{1},p_{2}...p_{k}的倍数的个数，即frac{N}{p_{i}}
2.加上p_{i}*p_{j}的倍数的个数，即frac{N}{p_{i}*p_{j}}
3.减去p_{i}*p_{j}*p_{k}的倍数的个数，即frac{N}{p_{i}*p_{j}*p_{k}}
...
得到：N-frac{N}{p_{i}} frac{N}{p_{i}*p_{j}}...，化简得N(1-frac{1}{p_{1}})(1-frac{1}{p_{2}})...(1-frac{1}{p_{k}})。
证毕。
欧拉定理
若a与n互质，则a^{phi_{(n)}}{equiv}1 (mod n)
证明
设[1,n]中与n互质的数分别为a_{1},a_{2}...a_{phi_(n)}。由于a与n互质，所以a*a_{1},a*a_{2}...a*{a_k}也分别与n互质，且互不相同。
关于互不相同的证明
假设a*a_{1}与a*a_{2}相同，则有如下式子
a*a_{1} {equiv}a*a_{2} (mod n) a(a_{1}-a_{2}) {equiv} 0 (mod n） a_{1}-a_{2} {equiv} 0 (mod n) a_{1}=a_{2} 与phi_{(n)}的定义矛盾，故a*a_{1},a*a_{2}...a*{a_k}互不相同
整理得以下式子
a*a_{1},a*a_{2}...a*{a_k} {equiv} a_{1},a_{2}...a_{phi_(n)} (mod n)
a^{phi_{(n)}}*(a_{1},a_{2}...a_{phi_{(n)}}) {equiv} a_{1},a_{2}...a_{phi_(n)} (mod n)
a^{phi_{(n)}}{equiv} 1 (mod n)
证毕。
费马小定理
a^{p-1}{equiv}1 (mod p)
证明
见欧拉定理的证明过程
