代数的整数論 011

〔フェルマーの小定理〕
pが素数のとき　a^p -a ≡ 0,　(mod p)

〔系〕
pが素数で、gcd(a,p)=1 のとき　a^(p-1) -1 ≡ 0,　(mod p)

(略証)
　aについての帰納法による。
・a=1 のとき、明らか。
・a^p -a ≡0 とする。
　　1≦k≦p-1　⇒　p | Ｃ[p,k] より
　(a+1)^p -(a+1) = a^p -a + Σ[k=1,p-1] Ｃ[p,k] a^k ≡ 0,　(mod p)

http://mathworld.wolfram.com/FermatsLittleTheorem.html

〔オイラーのTotient定理〕
　gcd(a,n)=1　⇒　a^φ(n) -1 ≡ 0,　(mod n)
　φ(n) はnの剰余類の正則元の数。（Eulerのtotient函数とか云うらしい･･･）

(略証)
nの剰余類 Ｚ/(n) のうち、gcd(x,n)=1 となるx（正則元）全体の集合を考える。
　{x|gcd(x,n)=1, x∈Ｚ/(n)} = G,
Gは乗法について閉じている。
∴ Gは乗法群をなす。　[Ｚ/(n)]† とも書くらしいが･･･
　a∈G, a≠1, aの位数をrとする。
　位数rの巡回群{1,a,a^2,････,a^(r-1)} = H はGの部分群となる。
ラグランジュの定理（ #H | #G ）から、
　r | φ(n),
　a^φ(n) ≡ 1^{φ(n)/r} = 1,　(mod n)　　　　　　(終)

http://mathworld.wolfram.com/EulersTotientTheorem.html

〔小定理の逆〕
　∀x;　x^n -x ≡ 0,　(mod n)
ならば、nは素数。

(略証)
　背理法による。
　(左辺) を f(x) とおく。
　f(x+1) - f(x) = (x+1)^n - x^n -1
　　　= Σ[k=1,n-1] Ｃ[n,k] x^k
　　　= Σ[k=1,n-1] (n/k)Ｃ[n-1,k-1] x^k,
　nは合成数と仮定したから、nの素因数をpとする。
　　Ｃ[n-1,p-1] = (n-1)(n-2)････(n-p+1)/(p-1)!,
　はpで割り切れないから、x^p の係数はnで割り切れない。
　上式は 恒等的に ≡0 (mod n) ではない。
　n次式だから高々n個の根しかない。
　∃a;　f(a+1) - f(a) ≠0,　　(mod n)
　∴ f(a+1)≠0, または f(a)≠0,　　　(終)

〔小定理の系の逆〕 ･･･は成り立たない。
　gcd(a,n) =1　⇒　a^(n-1) ≡ 1,　(mod n)
を満たす合成数nが存在する。orz
例
　3･11･17=561, 5･13･17＝1105,　7･13･19＝1729,　5･17･29=2465,　7･13･31=2821,　など
これを カーマイケル数と呼ぶらしい。

http://en.wikipedia.org/wiki/Carmichael_number
http://en.wikipedia.org/wiki/Knödel_number

nがカーマイケル数となる条件は、
　1. nは平方因数をもたない。
　2. p|n　⇒　(p-1)|(n-1)
http://d.hatena.ne.jp/smoking186/20081217/1229474226