一些基础数论的知识和证明

算术基本定理

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)

证明

见欧拉定理的证明过程