[ 新着記事
| 数学・プログラミング
| 天文・暦
| シリア語・Unicode・詩
| ジョーク
| 漫画・アニメ
| 字幕
| 哲学・ファンタジー
| 全記事
| チラ裏 ]
チラ裏
「チラ裏」は適当な走り書き。誤字・誤記・脱線が多いです！
2022-06-28 フェルマーの小定理で遊んじゃえっ
【1】 3以上の素数 p を考える。その素数 p より 1 小さい数を q としよう。このとき、2q − 1 は p で割り切れる。
これは面白い現象だ！ 「pマイナス1」乗から 1 を引くと p で割り切れる――事実は単純だが、なぜそうなるのかはミステリー。
一方、p が素数でない場合、似たことを考えると、例えば…
p が素数かどうかによって、2q − 1 の振る舞いが異なるようだ。2q − 1 という数は、q が「素数マイナス1」かどうか、どうやって「感じる」ことができるのだろうか？
【2】 q 乗される数 b は「2」に限る必要ない。素数 p の倍数以外なら、何でもいい。試しに b を「3」としてみよう。
一般に、p を素数、b を p の倍数以外の任意の整数とするとき、
bq − 1 は p で割り切れる（q = p − 1）。
つまり bp−1 − 1 は p で割り切れる。
bp−1 − 1 が p で割り切れるのだから、それより 1 大きい数を考えると、こうなる:
bp−1 を p で割ると、割り切れずに 1 余る。
式で書くと:
bp−1 ≡ 1 (mod p)
これがフェルマーの小定理だ！
合同記号 ≡ の意味は「小定理への道②」参照。
【3】 私たちはカレンダーを使って、この不思議な定理（何の役に立つのか分からないが…）を証明した。道筋を振り返ってみよう。ある月の次の日付は、もちろん全部曜日が違う:
S1 = {1, 2, 3, 4, 5, 6}
ところが、S1 の日付をそれぞれ2倍した次の日付も、やはり全部曜日が違う:
S2 = {2, 4, 6, 8, 10, 12}
しかも S2 の日付に含まれる6種類の曜日は、S1 の日付の6種類の曜日と同じなのだ！
例えば、2022年6月のカレンダーでは、
S1 の要素 ←同じ曜日→ S2 の要素
の1対1の対応が、次のように成り立っている:
1 ≡ 8 (mod 7) 水曜日
2 ≡ 2 (mod 7) 木曜日
3 ≡ 10 (mod 7) 金曜日
4 ≡ 4 (mod 7) 土曜日
5 ≡ 12 (mod 7) 日曜日
6 ≡ 6 (mod 7) 月曜日
合同式の左辺には S1 の日付が過不足なく1回ずつ現れ、右辺には S2 の日付が過不足なく1回ずつ現れている。
普通の等式について、例えば x = A, y = B なら xy = AB となるのは当たり前だが（ピンとこなければ x = A = 5, y = B = 3 のように具体的な数を当てはめてみよう）、合同式についても、法が一定の場合、x ≡ A, y ≡ B なら xy ≡ AB が成り立つ（パラレルワールドの掛け算）。それどころか、合同式が3個以上に増えて、例えば z ≡ C が追加されたとすると、xyz ≡ ABC も成立。すると、上の曜日の対応表から、
1 × 2 × 3 ≡ 8 × 2 × 10 (mod 7)
が成り立つはずだ。この事実は、実際に計算すれば簡単に確かめられる:
6 ≡ 160 (mod 7) 左辺も右辺も7で割った余りは同じ
この理屈を6個の数の積に拡張して、再び曜日の対応表を使うと:
1 × 2 × 3 × 4 × 5 × 6 ≡ 8 × 2 × 10 × 4 × 12 × 6 (mod 7)
――この左辺は S1 の全要素の積、右辺は S2 の全要素の積に他ならない。掛け算の順序を入れ替えると:
1 × 2 × 3 × 4 × 5 × 6 ≡ 2 × 4 × 6 × 8 × 10 × 12 (mod 7)
より一般的に、b を7の倍数以外の任意の数とするとき、次の2個の集合は、同じ曜日の日付をちょうど1個ずつ含む（ただし、現実のカレンダーと無関係に、例えばその月の「26日」の10日後を、その月の「36日」とみなす）。
S1 = {1, 2, 3, 4, 5, 6}
S3 = {1b, 2b, 3b, 4b, 5b, 6b}
この場合も、前者の全要素の積と、後者の全要素の積は合同（理由は後述）なので:
1 × 2 × 3 × 4 × 5 × 6 ≡ 1b × 2b × 3b × 4b × 5b × 6b (mod 7)
つまり 1 × 2 × 3 × 4 × 5 × 6 ≡ (1 × 2 × 3 × 4 × 5 × 6)b6 (mod 7)
この最後の合同式の両辺を (1 × 2 × 3 × 4 × 5 × 6) で割ると、
1 ≡ b6 (mod 7)
つまり b6 ≡ 1 (mod 7)
となって、フェルマーの小定理の p = 7 の場合が証明されたことになる。
この割り算が本当に許されるのか確かめることは、結構面倒だったが、私たちは「秘技」と呼ばれるものを証明した――この「秘技」を使うと「割り算の規則1」が証明され、上記の割り算の正しさが保証される。具体的に、mod m の世界では、m と互いに素な数で割るのなら、合同式の両辺を自由に割り算できる！
上の例の場合、(1 × 2 × 3 × 4 × 5 × 6) は、mod 7 の「7」と互いに素。
【4】 さらにさらに一般的に、任意の素数 p について、次の2個の集合を考えよう:
T1 = {1, 2, 3, 4, …, p−1}
T2 = {1b, 2b, 3b, 4b, …, (p−1)b}
ここで b は p の倍数以外の任意の整数。
この場合も2個の集合のそれぞれについて、全要素の積は合同で:
1 × 2 × 3 × 4 × … × (p−1) ≡ 1b × 2b × 3b × 4b × … × (p−1)b (mod p)
つまり 1 × 2 × 3 × 4 × … × (p−1) ≡ [1 × 2 × 3 × 4 × … × (p−1)]bp−1 (mod p)
両辺を 1 × 2 × 3 × 4 × … × (p−1) で割り算すると（☆）:
1 ≡ bp−1 (mod p)
つまり、フェルマーの小定理が成り立つ！
（☆）の割り算が許される根拠として、z = 1 × 2 × 3 × 4 × … × (p−1) と p は互いに素。なぜなら p は素数なので、2 以上 p 未満の約数を持たず、z と p の最大公約数は 1。「割り算の規則1」が適用される。
T1 と T2 の各要素が mod p において1対1対応すること（例えば、1週間が11日で曜日が11種類あるパラレルワールドでは、どちらの集合も同じ10種類の曜日を過不足なく含んでいること）については、「小定理への道①」である程度観察したが、この点をもう少し分析してみよう。
「秘技」によると、XY が Z で割り切れるとき、X と Z が互いに素なら、Y が Z で割り切れる。裏を返せば:
《な》 X と Z が互いに素なのに、Y が Z で割り切れないなら、XY は Z で割り切れない。
T1 のどの要素も、もちろん p で割り切れない。T2 のどの要素も、やはり p で割り切れない。なぜ？ この場合、X に当たるのは 1, 2, 3, …, p−1 のどれか。Y = b で、Z = p に当たり、X と Z は互いに素。しかも「b は p の倍数ではない」と仮定しているから、Y = b は Z = p で割り切れない。だから《な》によって、XY = 1b, 2b, 3b, etc. が Z = p で割り切れることはない。
すると、T1 も T2 も「p で割り切れる数」――言い換えれば ≡ 0 (mod p) の数――を含んでいない。つまり T1 の日付は、その月の p 日目の曜日を含んでいないが、T2 も、この曜日を含んでいない。一方、mod p ということは「1週間が p 日で曜日が p 種類」なのだから、T1 は、p 日目の曜日以外の全曜日を1回ずつ含む。
もしも T1 と T2 の曜日（mod p での区別）が1対1対応していないのなら、集合 T2 の日付を考えると、T1 に含まれるどれかの曜日（どれかの要素と合同な要素）が「抜けている」はず。けれど、どちらの要素も p−1 個なので、T1 の日付にあって T2 の日付にない曜日があるとするなら、その分、T2 の日付には「同じ曜日の重複」がある。それは不可能。というのも、もしも T2 のとある要素 Nb と別の要素 Mb の曜日が「衝突」（重複）していれば――要するに
Nb ≡ Mb (mod p)
ここで Nb と Mb は T2 の相異なる要素。
つまり N も M も 1 以上 p−1 以下
が成り立つとすれば――、その両辺から Mb を引いて:
Nb − Mb ≡ 0 (mod p)
つまり b(N − M) ≡ 0 (mod p)
従って b(N − M) は p で割り切れるはず。そうすると、b と p は互いに素なので、「秘技」によって N − M が p で割り切れるはず。N も M も 1 以上 p−1 以下なのだから、N と M をどう選択しても、そんなことは起こり得ない（強いて言えば N = M なら N − M = 0 は p で割り切れるが、その場合 Nb と Mb は同一の要素であり、相異なる要素ではないので、「別々の2要素が同じ曜日」という「衝突」はない）。
以上のことから、T1 と T2 は、全体として、同じ曜日の日付を一つずつ含む。つまり（☆）の割り算の前の「掛け算による合同式」には、きちんとした根拠がある。
T1 = {u1, u2, u3, …, up−1}, T2 = {v1, v2, v3, …, vp−1} とすると、u1 は v○ のどれか一つと合同、u2 は v○ のどれか一つと合同、等々。具体的にどの要素とどの要素が合同なのかはさておき、全体として1対1で合同なのだから、u1u2…up−1 という積は、全体として v1v2…vp−1 という積と合同。
【5】 論理的には、これでフェルマーの小定理が証明されたわけだが、算数のようなことを組み合わせて…というのは、とっつきやすい半面、見通しが悪い点もあるだろう。
フェルマーの小定理の証明法は、もちろんこれだけではない。
今回の主眼は、教科書をトレースすることではなく、「2・4・6・8・10・12・14日」は曜日が違うといった日常的なことからの（ちょっと奇抜な）アプローチ…。全てを「公倍数は、最小公倍数の倍数」という算数に帰着させ、ユークリッドの補題を小学生的な方法で証明した。これらの方法はエレガントではないかもしれないが、少し掘り下げると、いろんなことと結び付いてる。
注意！ フェルマーの小定理は、p が素数なら、bp−1 ≡ 1 (mod p) が必ず成り立つことを保証している（ここで b は p の倍数以外）。言い換えると、bp−1 ≡ 1 (mod p) が成り立たなければ p は絶対に素数ではない。一方、逆に bp−1 ≡ 1 (mod p) が成り立つからといって、必ずしも p が素数とは限らない（実際には素数であることが多いが、保証はない）。「4の倍数なら必ず偶数」だが、逆に「偶数だからといって、必ずしも4の倍数とは限らない」…それとと同じこと。
「チラ裏」は、きちんとまとまった記事ではなく、断片的なメモです…
![2016 = (28+28+28)×[28−(28+28+28+28)/28]](/image/2016/2016-28.png)
Map の長所、splice より速い要素挿入法も紹介。 〔最終更新: 2016年4月10日〕bdi 要素と Unicode 6.3 の新しい双方向アルゴリズム (2012-12-04)dir 属性は落とし穴が多い。HTML5 の <bdi> は役立つ。近い将来、「ユーザー入力欄などの語句は、このタグで隔離」が常識になるかも。 〔最終更新: 2014年4月27日〕
fad() は濁りやすい。各種の代替手段を紹介。forum.doom9.org / videolan.org
Tor Project | Anonymity Online / 
Tor Browser
The SeaMonkey® Project
LibreWolf Browser