オイラーの定理…a^φ(n)≡1 (mod n)

自分で言うのもなんですが ^^;…

この欄に訪問するのは超お久…Orz〜

知らぬ間に...最初の勉強しようとしてたサイトが消えている…^^;;…

と思ったら…ありましたぁ☆

http://aozoragakuen.sakura.ne.jp/suuron/suuron.html

今回は…別のところから…^^

http://www.tcp-ip.or.jp/~n01/math/euler.pdf より 引用 Orz〜

「定義 1 

自然数 n に対して,n 以下の自然数で n との最大公約数が 1 であるものの個数を φ(n) で表す.

φはオイラー関数と呼ばれる. 

(*オイラーの φ 関数（ファイかんすう、phi function）)

(*オイラーのトーシェント関数（Euler's totient function）)

φ(1) = 1

である。

定理 3 

p^n と互いに素でないそれ以下の自然数は p^(n−1) 個ある

[証明]

p^n と互いに素でない自然数は p*x とかける. 

x は 1 ≤ x ≤ pn−1 の全ての自然数の値を取り得,

なおかつそのどの x についても p*x が重複することはない(つまり p の倍数).

よってその個数は p^(n−1) である.　[証明おわり]

定理 4 

画像：http://ja.wikipedia.org/wiki/オイラーのφ関数 より Orz〜

φ(n)の最初の1000個の値

定理 8    (オイラーの定理)

自然数 n と互いに素である自然数 a について,

が成り立つ.

[証明] 

n 以下の自然数で n と互いに素な数を

r1,r2,r3,··· ,rφ(n)　　　　　　 (1) 

と表す.これらに,n と互いに素である自然数 a をかけた数,

ar1, ar2, ar3, · · · , arφ(n) 　　　(2) 

を考える.これらも全て n と互いに素である.

また,i̸=j=⇒ari

である.なぜならば,もし ari ≡ arj とすると,a(ri − rj) ≡ 0 つまり ri − rj は n で割り切れ,ri ≡ rj となってしまい,仮定と矛盾する.つまり (2) の各数は (1) のどれか一つと合同になり,なおかつ重複することはない.したがってこれらをすべててかけ合わせたものも合同になる.すなわち,

aφ(n)r1r2r3 ···rφ(n) ≡ r1r2r3 ···rφ(n) ( mod n )

よって

 aφ(n) ≡ 1

この定理の特殊な場合が次の定理である.

定理 9 (フェルマーの小定理)

p の倍数でない自然数 a について,

が成り立つ.

これらの定理は a が正の整数として証明したが,整数全体に拡張してもよい. 

問題 4 

2009^2009 の下 3 桁を求めよ.

[解]

φ(1000) = φ(2^3*5^3)
= 2^2*5^2*(2−1)(5−1) = 400

2009^2009 ≡ 9^2009 ( mod 1000) 

≡ 9^(400×5+9)

≡ 9^9
≡ (81^2)^2 × 9

≡ 561^2 × 9 

≡721×9

≡489··(·こたえ)

*こういう問題が解ける武器になるのって偉大だわ☆

これらの定理は n を法として 1 を得る最小の冪を与えるものではないことを注意しなければならない.たとえば

p = 7, a = 4

とすると,フェルマーの小定理は

4^6≡1 (mod7) 

となることを主張しているわけだが,

4^3=64≡1 (mod7)

なので 6 より小さい冪 3 で既に 1 に合同になっている.この小さい冪というのは必ず p − 1 の約数になっている.しかしながら,p の倍数で無いあらゆる整数 a について 1 と合同になる最小の冪は p − 1 である.これらの証明はここでは記述しない.　[証明おわり] 　」

*たとえば…4^6≡1 (mod 7)

ならば…6の約数である 1,2,3で…4^1≡±1, 4^2≡1, 4^3≡±1　でなければならないものねぇ ^^…じっさいは…4, 4^2 は違うわけだけど…

素数pのとき、p-1は偶数なので、a^{(p-1)/2}≡±1 であることは言えますね ^^