カーマイケル数の話
Wikipediaの日本語版だと無かったので適当に英語版にリンク. Carmichael number - Wikipedia, the free encyclopedia.
奇合成数nについて, 任意の1以上n-1以下の整数aに対してa^n≡a (mod n)が成立するとき, そのnをカーマイケル数と呼ぶ. (今日の説明では互素ということを言っていないので間違っていた.)
奇合成数nがカーマイケル数であることの必要十分条件は以下である.
- nは平方因子を持たない. (n=p1^e1 ... pk^ekと書いたとき, eiは全て1. ここも間違えて話していた.)
- 素数pについてpがnを割り切るなら, p-1もn-1を割り切る.
以下の証明はS.C. Coutinho著・林彬訳『暗号の数学の基礎』を参考にしている.
ちょっと記法を乱用しているが, その辺は各自正確ししていただきたい.
1, 2が成立→n:カーマイケル数
nの素因数pを考える. aがpで割り切れないとすると, フェルマーの小定理よりa^{p-1}≡1 (mod p)である.
条件2よりn-1はp-1で割り切れるので, a^{n-1}≡1 (mod p)である.
よって, a^{n}≡a (mod p)を得る.
一方, aがpで割り切れたとしても, a^{n}≡a (mod p)である.
従って, 任意の正整数aについて, a^{n}≡a (mod p)である.
以下, 条件1を使って a^{n}≡a (mod n)を示す.
今, 任意のnの素因子pについて, a^{n}≡a (mod p)が成立している. 従って, a^{n}-aはpで割り切れる. よって, a^{n}-aはnでも割り切れ, a^{n}≡a (mod n)を得る.
n:カーマイケル数→1,2が成立
まず, →1を示してみよう. 背理法を用いる.
ある素数pがnの約数かつp^2がnを割り切ると仮定する.
p^{n}-p=p(p^{n-1}-1)を考える. ちょっと証明が要るが, p^{n-1}-1はpで割り切れない. よって, p^{n}-pはp^2は割り切れないことになり, 当然nでも割り切れないことになる.
一方, nはカーマイケル数なのでp^{n}≡p (mod n)であるから, 矛盾.
次に→2を示す.
中国式剰余定理より, 写像(a mod n)→(a mod p_1,...,a mod p_k)を用いて,
と左と右が環として同型になる.
対偶を示す. 条件2が成り立たないと仮定するとnがカーマイケル数でなくなることを示せば良い.
ある素因数pで, p-1がn-1を割り切らないと仮定する. (面倒なので, p_1 = pとする.)
このとき, に注目する. この群の位数はp-1である. また, 1以上p未満の整数tが存在し, tがこの群の原始根となる. ( (t mod p)は位数が丁度p-1になる.)
さて, (t, 1, ..., 1)という右側の環の要素を考えよう. これをn-1乗すれば, (t^{n-1} mod p, 1 mod p_2, ..., 1 mod p_k)となる. 今, n-1はp-1で割り切れないので, tが原始根であることより, t^{n-1}≠1 mod pとなる. 従って, t^{n-1}≠1 (mod n)である. (中国式剰余定理より1⇔(1,1,...,1)なので.) よって, t^{n}≠t (mod n)も言える.
