数論のオーラの定理の証明&オーラの関数の公式

オーラ関数:
Euler関数は数論において重要な関数であり、Euler関数とは、正の整数nより小さく、nと相互作用する正の整数(1を含む)の個数について、φ(n) .
完全な余剰セット:
nより小さくnとの互質の数からなる集合をZnと定義し,この集合をnの完全剰余集合と呼ぶ.明らかに|Zn|=φ(n) .
関連性:
素数pについては、φ(p) = p -1 .
2つの異なる素数p,qに対して,それらの積n=p*qはφ(n) = (p -1) * (q -1)  .
これは,Zn＝｛1,2,3,…,n−1｝−｛p,2 p,…,(q−1)＊p｝−｛q,2 q,…,(p−1)＊q｝であるためである.φ(n) = (n - 1) - (q - 1) - (p - 1) = (p -1) * (q -1)  ＝
φ(p) *
φ(q)
.
オーラの定理:
互質の正の整数aとnに対して、
a
φ(n)
  ≡ 1 mod n  .
証明:(1)Zn={x
1, x
2, ..., x
φ(n)} , S = {a * x
1 mod n, a * x
2 mod n, ... , a * x
φ(n) mod n} ,
Zn＝Sである.
①aとnは相互作用するため、x
i
(1 ≤ i ≤ φ(n))
nと互質なのでa*x
i
nと互質なのでa*x
i
  mod n ∈ Zn .
②i≠jであればx
i
≠ x
j
a,n互質からa*xを得ることができる
i
mod n ≠ a * x
j
mod n(消去法則).
( 2 )     a
φ(n) * x
1 * x
2 *... * x
φ(n) mod n
      ≡ ( a * x
1 ) * ( a * x
2 ) * ... * ( a * x
φ(n) ) mod n
      ≡ ( a * x
1 mod n ) * ( a * x
2 mod n ) * ... * ( a * x
φ(n) mod n ) mod n
      ≡   x
1 * x
2 * ... * x
φ(n) mod n
等式の左右両端を比較すると、x
i
  (1 ≤ i ≤ φ(n))nと互質であるため,a
φ(n) 
≡1 mod n(消去則).
注意:
消去法則:gcd(c,p)=1の場合、ac≡bc mod p⇒a≡b mod p.
フェルマの定理:
正の整数aと素数pが互いに質を合わせれば、
a
p - 1
≡ 1 mod p .
この定理は非常に簡単であることを証明した.φ(p)=p−1,オーラ定理に代入すれば証明できる.
参照元:http://zhidao.baidu.com/question/15882452.html?si=2』』』』』』』』』』』』』』補足:オラ関数公式
(1)pkのオーラ関数
与えられた素数pに対して、φ(p) = p -1.正の整数n=pkに対して、

 φ(n) = pk - pk -1
  
  ：
    pk         pk - 1 ，  
   pk         {p * 1,p * 2,...,p * (pk - 1-1)}    pk - 1 - 1  
    φ(n) = pk - 1 - (pk - 1 - 1) = pk - pk - 1 。

(2)p*qのオーラ関数
p,qが2つの相互質の正の整数であると仮定すると,p*qのEuler関数は
φ(p * q) = φ(p) * φ(q) , gcd(p, q) = 1 .

  ：
   n = p * q ， gcd(p,q) = 1
         ， 
 Zn   Zp × Zq         
（     ： a ∈ Zp ， b ∈ Zq ⇔ b * p + a * q ∈ Zn 。）
    n                  Zp × Zq      。
           φ(p) * φ(q) ，   
 φ(p * q) = φ(p) * φ(q) 。

(3)任意の正の整数のEuler関数
いずれの整数nも、その素因子の積として表すことができる.

      I
 n = ∏  piki (I   n        )
     i=1

前の2つの結論から、そのオーラ関数は簡単に得られます.

         I                      I
 Φ(n) = ∏  piki -1(pi -1) = n ∏ (1 - 1 / pi)
        i=1                    i=1

任意のn>2に対して、2|Φ(n)pi−1が必ず存在するため偶数である.
プログラムコードは以下を参照してください.http://blog.csdn.net/Rappy/archive/2007/08/16/1747489.aspx
参照元:http://blog.csdn.net/ray58750034/archive/2006/03/27/640074.aspx