欧拉定理:
当 a 与 p 互质的时候则有 \(a^{\varphi(p)} \equiv 1 \ (mod \ p)\)
通项公式及证明:
若 \(n = p ^ k ,p\) 为质数, 则 \(\varphi (p^k) = p ^k - p ^{k - 1}\)
当一个数不包含质因子 \(p\) 时就能与 \(n\) 互质,
小于等于 \(n\) 的数中包含质因子 \(p\) 的只有 \(p^{k-1}\) 个, 他们是:
\(p, 2*p, 3* p, ...,p ^{k - 1} ?p\), 把他们去除即可.
由唯一分解定理可得: \(n = p_1 ^{a_1} p_2 ^{a_2}p_3 ^{a_3}...p_k ^{a_k}\)
则 \(\varphi (n) = \varphi(p_1^{a_1})\varphi(p_2^{a_2})\varphi(p_3^{a_3})...\varphi(p_k^{a_k})\)
根据上述 \(\varphi (p^k) = p ^k - p ^{k - 1}\) 可得:
$????????????\varphi (p) = p^k(1 - $\({1}\over {p^k}\))
则 \(\varphi (n) = \varphi(p_1^{a_1})\varphi(p_2^{a_2})\varphi(p_3^{a_3})...\varphi(p_k^{a_k})\) 可化为
- \(\ \ \ \ \varphi (n) = p_1 ^{
- a_1
- }(1 - \frac {
- 1
- } {
- p_1
- }) p_2 ^{
- a_2
- }(1 - \frac {
- 1
- } {
- p_2
- })p_3 ^{
- a_3
- }(1 - \frac {
- 1
- } {
- p_3
- })...p_k ^{
- a_k
- }(1 - \frac {
- 1
- } {
- p_k
- })\)
- \(\ \ \ \ \ \ \ \ \ \ \ = n (1 - \frac {
- 1
- } {
- p_1
- })(1 - \frac {
- 1
- } {
- p_2
- })(1 - \frac {
- 1
- } {
- p_3
- })...(1 - \frac {
- 1
- } {
- p_k
- })\)
欧拉函数
\(\varphi(n) or \phi(n)\)
表示小于 n 的正整数与 n 互质的数的个数.
显然有:
当 n 为质数时 \(\varphi(n)\)
当 n 为奇数时 \(\varphi(2n) = \varphi(n)\)
证明:
\(\because\) 欧拉函数为积性函数.
- \(\therefore \varphi(2n) = \varphi(2) \ast \varphi(n)\)
- \(\because \varphi(2)=1\)
- \(\therefore \varphi(2n) = \varphi(n)\)
证明欧拉函数的积性证明.
条件是 m 与 n 互质
可以得到 \(\phi(mn) = \phi(m) \ast \phi(n)\)
证明:
- \(m = p_1^{
- a_1
- }p_2^{
- a_2
- }...p_k^{
- a_k
- }\)
- \(\phi (m) = m(1- \frac {
- 1
- }{
- p_1
- })(1- \frac {
- 1
- }{
- p_2
- })...(1- \frac {
- 1
- }{
- p_k
- })\)
- \(n = p_1'^{a_1'}p_2'^{a_2'}...p_k'^{a_k'}\)
- \(\phi(n) = n(1- \frac {
- 1
- }{
- p_1'})(1- \frac {1}{p_2'
- })...(1- \frac {
- 1
- }{
- p_k'
- })\)
- \(\because m 与 n 互质 \)
\(\therefore p_1,p_2...p_k 与 p_1'p_2'...p_k'\) 两两互不相同
- \(\therefore \phi(mn) = mn(1- \frac {
- 1
- }{
- p_1
- })(1- \frac {
- 1
- }{
- p_2
- })...(1- \frac {
- 1
- }{
- p_k
- })(1- \frac {
- 1
- }{
- p_1'})(1- \frac {1}{p_2'
- })...(1- \frac {
- 1
- }{
- p_k'
- })\)
- \(\therefore \phi(mn) = \phi(m) \ast \phi(n)\)
来源: http://www.bubuko.com/infodetail-3345155.html