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)
见欧拉定理的证明过程
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。