[ 新着記事
| 数学・プログラミング
| 天文・暦
| シリア語・Unicode・詩
| ジョーク
| 漫画・アニメ
| 字幕
| 哲学・ファンタジー
| 全記事
| チラ裏 ]
チラ裏
「チラ裏」は適当な走り書き。誤字・誤記・脱線が多いです！
2022-06-29 フェルマーの小定理のスパイシーな話題 4k+1型素数は無限個
Hardy & Wright（1938）が「more difficult」と呼び、第20章でようやく証明を完成させている定理。高木
どちらも有名な古典的名著だが、この証明に関しては、高木に軍配が上がるだろう。
美しい証明を紹介し、若干の冒険を試みる。
【1】 多くの人はご存じだろう。「素数は無限個存在する」こと、そして、ユークリッドによるそのエレガントな証明を…
2000年以上前、日本列島の住民が文字も持たず、1冊の本も持たず、竪穴住居でつましく暮らし（？）、イネを植えたりドングリを拾って食べたりしていた頃、ギリシャでは既に公理論的数論の研究書が執筆され、素数の無限が証明されていた。それから1000年以上たっても、ヨーロッパの住民は、古代ギリシャの教科書を読んで数論を勉強していた。驚くべきことだ！
ユークリッドの方法を少し変えると、4k+3型の素数（愛称: チョコレート素数）が無限個存在することも、簡単に示される。矛盾を導くため、チョコレート素数が有限個しかないと仮定する。その場合、一番大きいチョコレート素数が存在するので、それを C としよう。C 以下のチョコレート素数を、全部掛け合わせる:
3 × 7 × 11 × … × C
ユークリッドはこのような積に 1 を足したが、ここでは、この積を4倍して 1 を引いたものを D とする:
《に》 D = 4(3 × 7 × 11 × … × C) − 1
《ぬ》 D = 4(3 × 7 × 11 × … × C) − 4 + 3 = 4[(3 × 7 × 11 × … × C) − 1] + 3
D は、4の倍数プラス3なので、4k+3型の奇数。言い換えれば:
《ね》 D ≡ 3 (mod 4)
D は、もちろん C よりでかい。もし D が素数だったらそれは C より大きい4k+3型素数であり、上記の仮定が間違ってたことが直ちに分かる。一方、D が合成数だとすると、D は、C 以下のどの4k+3型素数 p でも割り切れない（なぜなら《に》によれば、D は p の倍数より 1 小さい、つまり p の倍数ではない）。だが、仮定によれば C より大きい4k+3型素数は存在しない。ということは、D は4k+3型素数では一切割り切れないことになり、D の素因数は全部「4k+1型」でなければならない（D は奇数なので、因子2を含まない）。今、D が、次のように h 個の素因数に分解されたとしよう:
D = v1v2v3…vh
ここで v1, v2, … は、どれも4k+1型素数（必ずしも相異ならない）
言い換えると v1, v2, … は、どれも ≡ 1 (mod 4)
このとき D = v1v2v3…vh ≡ 1⋅1⋅1⋅…⋅1 ≡ 1 (mod 4)
この最後の合同式は《ね》と矛盾する。□
〔例1〕 4k+3型素数が {3, 7} だけだと仮定（C = 7)。D = 4(3⋅7) − 1 = 83 は4k+3型素数で C より大きいので矛盾。
〔例2〕 4k+3型素数が {3, 7, 11} だけだと仮定（C = 11)。D = 4(3⋅7⋅11) − 1 = 923 = 13 × 71 と素因数分解される。71 は4n+3型素数で C より大きいので矛盾。
【2】 同様な方法で「4k+1型素数（愛称: バニラ素数）も無限にあること」も、示せそうな気がする。実際には、これは【1】より少し難しい。
Hardy & Wright は、この証明の完成を200ページくらい先延ばしして、x² + y² = n の解の個数の議論の特別な場合（n の因子としてチョコレート素数の1乗が含まれると、解がないこと）に帰着させている。高木は、これをフェルマーの小定理を使ってあっさり片付け、続けて「一般に、ak+1型素数が無限にある」ことまで証明している（4k+1型は a=4 に当たる）。
以下ではまず高木の方法を紹介する。これは次の補題に依存していて、含蓄があるのだが、微妙に回りくどい。【3】では、この補題を使わないで済むような、ショートカットを研究しよう。
補題 b を任意の整数とする。b2 + 1 が、4k+3型素数で割り切れることはない。
証明 p を 3 以上の素数とする。b2 + 1 が p で割り切れるとする。
p で割り切れるということは b2 + 1 ≡ 0 (mod p) つまり
《の》 b2 ≡ −1 (mod p)
《の》の両辺を平方して b4 ≡ 1。補助定理1から、この指数 4 は b の位数の倍数。《の》から b の位数は 2 以下でないので、b の位数は「4」。補助定理1.1より、位数「4」は p − 1 の約数。従って
4 × 整数 = p − 1 つまり p = 4 × 整数 + 1
と書ける。つまり、3 以上の p は4k+1型: b2 + 1 が4k+3型素数で割り切れることはない。□
〔付記〕 原始根の存在を認めるなら…。p = 4k+3 のとき、《の》に解がない理由は、p − 1 = 4k+2 が 4 で割り切れないから（詳細）。補題の実体は、平方剰余の第一補充法則に他ならない。
定理（高木 §10.2） 4k+1型の素数が無限に存在する。
証明 矛盾を導くため、4k+1型の素数が有限個だと仮定する。すると、一番大きい4k+1型素数が存在がする。それを V としよう。このとき、4k+1型の全素数の積は:
5 × 13 × 17 × … × V
この積の平方の4倍に 1 を足したものを W とする:
《は》 W = 4(5 × 13 × 17 × … × V)2 + 1 つまり
《ひ》 W = 22(5 × 13 × 17 × … × V)2 + 1 = (2 × 5 × 13 × 17 × … × V)2 + 1
《は》から分かるように、W は4k+1型の奇数で V より大きい: もし W が素数なら直ちに矛盾が生じる。一方、W が合成数だとした場合、
b = 2 × 5 × 13 × 17 × … × V
と置くと、《ひ》は W = b2 + 1 となるが、上の補題によれば、この数が4k+3型素数で割り切れることはない。つまり奇数 W が合成数なら、その素因数は4k+1型に限られる。ところが《ひ》から分かるように、V 以下のどの4k+1型素数で W を割っても、1 余ってしまい、割り切れない。要するに W が合成数なら、その素因数は4k+1型で、しかも V より大きい。いずれにしても最初の仮定は誤りで、V より大きい4k+1型素数が存在する。□
〔例3〕 4k+1型素数が {5, 13, 17} だけだと仮定（V = 17)。W = 4(5⋅13⋅17)2 + 1 = 4884101 は4k+1型素数で V より大きいので矛盾。
〔例4〕 4k+1型素数が {5, 13, 17, 29} だけだと仮定（V = 29)。W = 4(5⋅13⋅17⋅29)2 + 1 = 4107528101 = 37 × 173 × 641701 と素因数分解される。どの素因数も4n+1型で V より大きいので矛盾。
【3】 上記の高木の証明（若干改変している）は、フェルマーの小定理を直接使わず、位数の理論に依存する補題を経由している。以下では、この依存を取り除き、フェルマーの小定理だけを直接使って、同じ結論を得る。
ユークリッドは、素数のリストが有限だと仮定し「リストにある全素数の積プラス1」を考えて、矛盾を導いた。現代では、もう少し具体的に、最大の素数 x の存在を仮定して「x以下の全素数の積プラス1」を考えることが普通だろう。ここでも V 以下の全素数の積を考える（V は4k+1型の素数）。ただし、高木の工夫をまねて「V以下の全素数の積の2乗、プラス1」を考え、それをあらためて W と呼ぼう。
W = (2 × 3 × 5 × … × V)2 + 1 = 4(3 × 5 × … × V)2 + 1
この W は4k+1型の奇数で V より大きいので、もし W が素数なら、証明が完了する。一方、W が合成数の場合、その素因数の一つをどれでも勝手に選んで p とすると…。W は、V 以下のどの素数で割っても 1 余って割り切れないので、W の素因数 p は V より大きい。さて、W が p で割り切れるということは:
W ≡ 0 つまり (2 × 3 × 5 × … × V)2 + 1 ≡ 0 (mod p)
従って (2 × 3 × 5 × … × V)2 ≡ −1 (mod p)
この両辺を (p−1)/2 乗すると〔注1〕:
《ふ》 (2 × 3 × 5 × … × V)p−1 ≡ (−1)(p−1)/2 (mod p)
〔注1〕 V は4k+1型の素数なので、最低でも5、p はそれより大きい素数なので奇数: (p−1)/2 は割り切れて整数になる。
p は素数なので、もちろん (2 × 3 × 5 × … × V) の倍数ではない。だから《ふ》の左辺にフェルマーの小定理を適用できる:
《へ》 (2 × 3 × 5 × … × V)p−1 ≡ 1 (mod p)
分かりにくければ (2 × 3 × 5 × … × V) を b と置いてみよう。
《ふ》と《へ》の左辺同士は等しいので、もちろん右辺同士も等しい:
《ほ》 (−1)(p−1)/2 ≡ 1 (mod p)
−1 の奇数乗は −1、偶数乗は 1 なので、(p−1)/2 が奇数か偶数かに応じて、《ほ》は
−1 ≡ 1 (mod p) もしくは 1 ≡ 1 (mod p)
となる。前者は、ばかげている〔注2〕。従って (p−1)/2 は偶数でなければならない: 2 で割って偶数になるのだから、(p−1) は 4 の倍数でなければならない。だから、とある整数 k を使って
p−1 = 4k つまり p = 4k+1
と書くことができる。すなわち、V より大きい4k+1型素数が存在する。これが証明されるべきことだった。□
〔注2〕 A ≡ B (mod p) の意味は「A − B が p の倍数」。だから −1 ≡ 1 (mod p) の意味は「−2 が p の倍数」。上記の p は奇数なので「−2 が p の倍数」ということは不可能。
この別証明は、高木のオリジナル版から補題を除去して簡単化したもの。p は勝手に選んだ W の素因数であり、どの素因数を選んでもそれが4k+1型になることが示されたのだから、「W の素因数は4k+1型に限られる」という点に関しては、オリジナル版と変わらない。補題を使わないで同じ結論が出るのだから、この道の方が良いだろう。ただし W の定義が異なり、高木版と比べ、数値的には、無駄に大きい。「両辺を (p−1)/2 乗する」という操作も、若干、天下り的で不自然かもしれない。「遊び」としては、トリッキーな式変形もまた一興…
〔例5〕 4k+1型素数が {5, 13, 17} だけだと仮定（V = 17)。W = (2⋅3⋅5⋅7⋅11⋅13⋅17)2 + 1 = 260620460101 = 1409 × 184968389 と素因数分解される。どの素因数も4n+1型で V より大きい。例3の W = 4(5⋅13⋅17)2 + 1 = 4884101 に比べると、桁違いに大きい W を考えている。
今回の命題に関しては、Hardy & Wright の証明法を紹介すらしなかった（高木の証明の方が簡潔なので）。話題の選択上そうなっただけで、別に Hardy & Wright の偉業にけちをつけるつもりはない！
2022-06-28 フェルマーの小定理で遊んじゃえっ
【1】 3 以上の素数 p を考える。その素数 p より 1 小さい数を q としよう。このとき、2q − 1 は p で割り切れる。
これは面白い現象だ！ q 乗から 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, XY = 2b, XY = 3b などが 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