メモ（数論5）: 原始根の存在証明　完全解説

チラ裏　＞　数論　＞　メモ5

「チラ裏」は、きちんとまとまった記事ではなく、断片的なメモです。誤字脱字・間違いがあるかもしれません。

• 2021-12-25　げんしこん　現代視覚文化・混乱困惑コンテンツ
• 2022-01-14　b の位数は p−1 の約数　げんしこん・補足
• 2021-12-28　げんしこん（その2）　コピペで手抜き
• 2021-12-31　xⁿ − yⁿ は x − y で割り切れる　n次方程式の解の個数
• 2022-01-08　げんしこん（その3）　プチ定理
• 2022-01-15　げんしこん（その4）　冪（べき）という漢字
• 2022-01-18　げんしこん（その5）　2数の積の約数は…
• 2022-01-22　げんしこん（その6）　存在の証明
• 2022-01-26　げんしこん（その7）　おまえはもう矛盾している
• 2022-01-31　げんしこん（その8）　高木先生の証明法
• 2022-02-05　「商」と「総」　超入門／オイラーのファイ関数
• 2022-02-11　げんしこん（その9・最終回）　アッと驚くガウスの証明

2021-12-25　げんしこん　現代視覚文化・混乱困惑コンテンツ

我々はぁ！　現代視覚文化混乱の根源たるウェブ上においてぇ！　このような意味の分からない題名のぉ！　訳の分からないコンテンツの混在にぃ！　根本的・闘魂的・痛恨的決意をもってぇ！　断固！　抗議するものであ～るっ！！！

まぁ、そんなことは、どうでもいいとして。

p を素数とする。フェルマーの小定理によると、1 以上 p 未満の任意の整数 b について、b^p−1 を p で割ると 1 余る。例えば p = 7 として、b = 3 とすると:
　　b^p−1 = 3⁷⁻¹ = 3⁶ = 729
　　729 ÷ 7　　→　　104 余り 1♪

b = 3 は、6乗して初めて「余り1♪」になる（1乗～5乗では「余り1」にならない）。一方、b = 2 は、6乗して「余り1♪」になるだけでなく、中間の b³ でも「余り1☆」になっている。一覧表にすると:

bの自然数乗（上段）と、それを7で割った余り（下段）

	b1	b2	b3	b4	b5	b6
b = 1	1	1	1	1	1	1
	1☆	1☆	1☆	1☆	1☆	1♪
b = 2	2	4	8	16	32	64
	2	4	1☆	2	4	1♪
b = 3	3	9	27	81	243	729
	3	2	6	4	5	1♪
b = 4	4	16	64	256	1024	4096
	4	2	1☆	4	2	1♪
b = 5	5	25	125	625	3125	15625
	5	4	6	2	3	1♪
b = 6	6	36	216	1296	7776	46656
	6	1☆	6	1☆	6	1♪

ランダムな数値が並んでるようにも見えるが、この表には、面白いパターンや秘密がいろいろと隠れている。まずは用語の説明から…

b の自然数乗のうち、初めて結果が「余り1」になる指数を b の位数（いすう）という。上の例では、1 の位数は 1 で、6 の位数は 2。2 の位数、4 の位数は、どちらも 3。3 の位数、5 の位数は、どちらも 6。

例えば b = 2 は、1乗しても2乗しても「余り1」にならないが、3乗すると「余り1☆」。だから位数3。一方、b = 3 は、1乗～5乗では「余り1」にならないが、6乗すると「余り1」なので、位数6。

1 以上 p 未満のどの b を考えても、その b の位数は p−1 の約数になる（証明は下記）: この例では p = 7 なので p−1 = 6 であり、位数は最大でも p−1（その約数なので）。b の位数は b によって違うが、全くランダムなのではなく、この例の場合「どの位数も 6 の約数」になっている！

位数が最大値 p−1（上の例では 6 に当たる）であるような b を、原始根（げんしこん）という。上の例では、3 と 5 が原始根。

2022-01-14　b の位数は p−1 の約数　げんしこん・補足

直観的に言えば、「周期的に繰り返され、6回ごとに 1 になる値」は、周期1・2・3・6のどれかで 1 になるしかない。一般に「p−1回ごとに 1 になる値」は、p−1 の約数を周期として 1 になるしかない。きちんと言葉で言うと…

ある素数 p を選んで固定する。b を 1 以上 p 未満の任意の整数とするとき、必ず
　　b^p−1 ≡ 1 (mod p)
が成り立つ。これは「フェルマーの小定理」と呼ばれる（以下「小定理」）。

《例1》　p = 7, b =2 とする。2⁷⁻¹ = 2⁶ = 64 を7で割ると 1 余る。つまり:
　　2⁷⁻¹ ≡ 1 (mod 7)

一方、
　　b^□ ≡ 1 (mod p)
の□に当てはまるような最小の正の整数を、b の位数（いすう）という。小定理によって b^p−1 が ≡ 1 になることは保証されているので、位数はどんなに大きくても p−1 以下。一般には p−1 より小さい。

《例2》　2⁶ ≡ 1 (mod 7) だが（例1参照）、2³ = 8 も ≡ 1 となる（つまり 7 で割ると1余る）。2¹ = 2 と 2² = 4 は、≡ 1 にならない（つまり 7 で割ったとき余りが1ではない）。だから、mod 7 では、2の位数は 3。

b の位数を e とすると、e は p−1 の約数のどれかに等しい（p−1 自身も p−1 の約数であり、b の位数が p−1 に等しいこともある――そのような b が原始根）。より一般的に…

補助定理1　b^□ ≡ 1 (mod p) の□に当てはまるような任意の自然数は、b の位数の倍数。

証明　b の位数を e とする。今、仮に b^f ≡ 1 (mod p) となるような自然数 f があって、f は e の倍数ではないとしよう。このような f は e で割り切れない（e の倍数でないので）。f を e で割った商を q、余りを r とすると:
　　f = eq + r　　（ただし r は 1 以上 e 未満の整数）
仮定より b^f ≡ 1 なので、その f に上の式の右辺を代入すると:
　　b^(eq + r) = b^eq × b^r ≡ 1　　‥‥　①
ところが e は b の位数なので、b^e ≡ 1、従って b^eq = (b^e)^q ≡ (1)^q ≡ 1。よって①は、次の意味を持つ:
　　b^eq × b^r ≡ 1 × b^r ≡ 1
　　要するに　b^r ≡ 1　　‥‥　②
ここで r は 1 以上 e 未満だが（e で割った余りなので）、②が成り立つとすると、話に矛盾が生じる。だって e は位数――つまり、
　　b^□ ≡ 1 (mod p)
に当てはまる最小の正の整数――なんだから、もっと小さい r が□に当てはまるっていうのでは、つじつまが合わない。つまり「e の倍数でない f が、b^f ≡ 1 を成り立たせることもある」という最初の仮定は、無理。b^□ ≡ 1 の□に当てはまる数は、e の倍数に限られる。（証明終わり）

補助定理1.1　mod p において、0 と合同でない任意の b について、b の位数 e は、p−1 の約数。

証明　小定理から b^p−1 ≡ 1 なので、補助定理1により p−1 は e の倍数。言い換えると、e は p−1 の約数。□

2021-12-28　げんしこん（その2）　コピペで手抜き

b¹, b², b³, … を素数 p で割った余りの表（前回）はランダムっぽいが、単純なパターンになってる部分もある。

【1】　1 以上の整数 N に対して b^N ≡ 1 (mod p) になるとしよう。そして N 未満の自然数 n では、bⁿ ≡ 1 にならないとしよう。要するに b の位数を N とする。

【例】　b = 2 のとき 2³ = 8 ≡ 1 (mod 7) だが、2¹ = 2 も 2² = 4 も ≡ 1 (mod 7) ではない。つまり、7 で割って 1 余らない。この例では、2 の位数は N = 3。

この場合、b^N+1 は、b を N+1個、掛け合わせたものだから、b^N × b に等しい。ところが b^N ≡ 1 なのだから、b^N+1 ≡ 1 × b = b。同様に、b^N+2 ≡ 1 × b² = b²。一般に、
　　b¹, b², b³, … と
　　b^N+1, b^N+2, b^N+3, … は同じであり、同様に
　　b^2N+1, b^2N+2, b^2N+3, … なども同じ数列。

【例】　2¹ = 2 ≡ 2, 2² = 4 ≡ 4, 2³ = 8 ≡ 1　　［7 で割った余りを考えてる］
2⁴ = 16 ≡ 2, 2⁵ = 32 ≡ 4, 2⁶ = 64 ≡ 1　　［2, 4, 1 がリピートされる］

従って、b の1乗、2乗、3乗…を計算して、あるところで ≡ 1 になったら、あとは同じパターンの反復。その先は個別に計算せず、そこまでの結果をループさせて、コピペすればいい！

【2】　それでも位数は最大 p−1 なので、最悪、1乗から (p−1)乗 まで p−1 個の計算が必要になる…ように思える。ところが…実は、その半分の (p−1)/2 乗を計算した時点で、必ず ≡ 1 または ≡ −1 になる（ここで p は 3 以上の素数）。≡ 1 の場合、【1】のように、残りについては、そこまでの計算結果を機械的にコピペすればいい。≡ −1 の場合、そこまでの計算結果の符号を変えたものをコピペすればいいので、実質的な手間は、前者と変わらない。

【例】　b = 3 とする。mod 7 において、3¹ = 3 ≡ 3, 3² = 9 ≡ 2, 3³ = 27 ≡ 6 ≡ −1 なので、【1】の計算結果を再利用すると 3⁴ = 3³ × 3¹ ≡ (−1) × 3 = −3, 3⁵ = 3³ × 3² ≡ (−1) × 2 = −2, 3⁶ = 3³ × 3³ ≡ (−1) × (−1) = 1。
　　［3, 2, −1 の後、符号を逆にした −3, −2, 1 がリピートされる］

結局、p−1 乗までの表を作らなくても、(p−1)/2 乗までの表で足りる。例えば p = 13 なら p−1 = 12 乗まで計算しなくても、半分の6乗までの計算でOK。これだけでも手間が半分に！

【3】　指数 n だけでなく、底（てい） b についても、正直に b = 1 から b = p−1 まで計算するまでもない。例えば、b = 5 ≡ −2 (mod 7) なので、5¹, 5², 5³, … は (−2)¹, (−2)², (−2)³, … と合同。ということは、2¹, 2², 2³, … を再利用できる。つまり
　　5¹ ≡ (−2)¹ = (−1 × 2)¹ = (−1)¹ × 2¹ ≡ −2 (≡ 5)
　　5² ≡ (−2)² = (−1 × 2)³ = (−1)² × 2² ≡ 4
　　5³ ≡ (−2)³ = (−1 × 2)⁴ = (−1)³ × 2³ ≡ −1 (≡ 6)
　　…
なので、偶数乗なら単純コピペし、奇数乗なら符号を逆にして、コピペすればいい。
　　［【1】の 2, 4, 1 がリピートされる…ただし奇数番目は符号が逆になる］

【4】　正直に全部計算しなくても、実質4分の1以下の計算量で足りる。例えば p = 13 の場合、1～12のそれぞれについて1～12乗を考えなくても、1～6について1～6乗を考えれば十分。

(p−1)/2 乗すれば必ず ≡ ±1 になるという【2】の主張については証明が必要だが（次回以降）、とりあえず前回の表を眺めて、上記のようになってることを確かめてみよう。

2022-01-08　げんしこん（その3）　プチ定理

【1】　フェルマーの定理は、純粋数学でも暗号学などへの応用でも、基本中の基本として常用される。その内容は:

p を素数、b を 任意の整数（p の倍数以外）とする。このとき b の (p−1) 乗を p で割ると 1 余る。

《例》　p = 7, b = 3 とすると、定理の内容は「3⁶ を 7 で割ると 1 余る」。実際、3⁶ = 729 = (700 + 28) + 1 = (7の倍数) + 1。

余談だが、17世紀フランスの数学者ピエール・ド・フェルマーは、いろんな定理を証明あるいは予想した。最も有名なのは「フェルマーの最終定理」だろう。どの定理のことか明示したい場合、上記は「フェルマーの小定理」と呼ばれる。英語では little theorem、フランス語では petit théorème（プティ・テオレム）。「フェルマーのプチ定理」というと、ちょっとかわいい♪

【2】　整数を「7で割った余り」で分類すると、「余り0の数たち」「余り1の数たち」「余り2の数たち」…「余り6の数たち」の7種類に分かれる。この分類上で「同じ種類」の整数を「等しい」と考えてみよう。例えば:
　　9 = 16
これは、9日目と16日目（あるいは、ある月の9日と16日）は同じ曜日だ…とも解釈できる。9 = 16 などと書くと混乱の原因になる場合には、
　　9 ≡ 16 (mod 7)
と書き、言葉では「7を法として9と16は合同」と表現する。誤解の恐れがなければ、面倒なので「mod 7 で 9 = 16」などと言っても構わない。実際、7個の要素から成る有限体（ゆうげんたい）――早い話が上記のような「曜日ワールド」――では、9と16は同じ要素（同一の曜日）を指す。この場合の 9 や 16 は「普通の整数」ではなく「曜日ワールドの要素」（同じ要素に無限個の別名がある）。

またまた余談だが、このような「曜日ワールド」は、正式には ℤ/7ℤ という記号で表される（フォントの都合で Z/7Z とも）。簡略に Z₇ と表記されることもあるが、この簡略表記については、なぜか一部の数学者から毛嫌いされている。いわく、Z_p は p進体の整数を表す記号でもあるから、紛らわしいと。一理あるが、それを言うなら、円周率を表す記号でもある π で二次体の素数を表したり、あるいは素数をカウントする関数を表したりするのは、もっと紛らわしい。一方、小定理の話の途中でp進体が出てくるわけないのだから、誤解が生じる余地はなく、Z_p 表記には何の問題もないと思われる…。まぁ、記号なんて、意味が分かれば何でもいいわけで、好みの問題だろう。

【3】　フェルマーの小定理によると、曜日ワールドの任意の要素 x について（ただし7の倍数以外）、
　　x⁶ = 1
が成り立つ。正確に言えば:
　　x⁶ ≡ 1 (mod 7)　　……　①

さて、方程式①には、合計何種類の解があるだろうか（答えの分かり切った問いかもしれないが）？

n次方程式には、最高でもn個しか解がない（実数や複素数の世界に限らず、曜日ワールドのような世界でも）。だから①の解は6個以内だが、上記のようにフェルマーの小定理から、x = 1, 2, 3, 4, 5, 6 は全て①を満たす。つまり、①の解の個数は「6個以内」という上限ぴったり: ①は6個の解を持つ。

「x は 7の倍数でなければ任意のはず。例えば x = 8 も解では？」という疑問が浮かぶかもしれない。曜日ワールドでは 8 ≡ 1 なので、この解は既に上記のリスト（6種類の解）に含まれていて、解の個数は増えない。

同様に、
　　x³ ≡ 1 (mod 7)
には、3個以内しか解がないわけだが（ここで指数 3 は、①の指数 6 の約数）、正確には何個の解があるか？

「げんしこん」の表を見ると、この場合も、上限ぴったりの3個の解が見つかる（x = 1, 2, 4）。表で b³ の列が「1☆」となっている行がそれ。

さらに、
　　x² ≡ 1 (mod 7)
には、2個以内しか解がないわけだが（ここで指数 2 は、①の指数 6 の約数）、正確には何個の解があるのだろうか？

「げんしこん」の表を見ると、この場合もやはり、上限ぴったりの2個の解が見つかる（x = 1, 6）。

何となく、d が 6 の約数なら p^d ≡ 1 (mod 7) は上限ぴったりの d 個の解を持つのかな…と。実は、その予想は正しい。より一般的に:

• p を素数とする。p−1 の任意の約数を d とすると、x^d ≡ 1 (mod p) は、ちょうど d 個の解を持つ。

以下では、曜日ワールド（mod 7）以外の世界、例えば mod 11, mod 13 などでも上記が成り立つことを具体的に確かめた上で、この命題を証明したい。この命題を利用して、原始根の存在はエレガントに証明される。（続く）

原始根の存在の証明法はいろいろあり、ガウス自身によるものも面白い。一方、高木の教科書（伝説的名著）や、Hardy & Wright の古典的教科書による証明法は、初等的で平易だけど、少々見通しが悪い。ここでは William Stein の Elementary Number Theory: Primes, Congruences, and Secrets（『初等整数論: 素数・合同・そして秘密』）にある証明法を最初に紹介する。この本は、買うと40～50ドル（ざっと5000円）くらいだが、著者自身が全文を無料公開していて（リンク先参照）、しかもダウンロードページには、プライバシーを侵害するグーグルなどのスクリプトがない。高木の名著「初等整数論講義」も著作権が切れ、ウェブ上で自由に読むことができる。

2022-01-15　げんしこん（その4）　冪（べき）という漢字

冪（べき）という漢字は、数学以外ではほとんど使われないが、累乗（るいじょう）つまり指数乗の計算を表す（略字として、単に「巾」とも書かれる）。例えば 11² や 11³ は素数 11 のべき（素数べき）。

辞書によると、「冪」は形声文字（意味を表す部分と発音を表す部分を組み合わせた漢字）で、もともとは「幎」（巾 + 冥）と書かれたという。「巾」（きん）は、漢字の意味を表す部分。それ自体は象形文字で、中央の縦棒を覆うように、上に何かをかぶせた様子を表すようだ。「覆いかぶせる物、包み込む布」などを表し、頭巾（ずきん）、巾着（きんちゃく）、三角巾（さんかくきん）などの語で使われる他、「布」という字も「巾」を含む。一方、「冥」（めい）は、漢字の音を表す部分で、現代中国語では míng、福建語（ふっけんご）では bêng と読まれるらしい。

幎はだんだん字形が変わり、結局、冪となった。「かぶせる布」なら、確かに「幕」の方がイメージ的にも分かりやすいかも。日本語での「冪」の漢音 beki は、「幕」の漢音 baku とも関係ありそう。

それはいいとして、何で指数計算が「覆いかぶせる・布」という意味の言葉で表されるのだろうか…？

11⁵ = 11 × 11 × 11 × 11 × 11 のような計算では、11倍が何度も反復され、「11倍」の計算が「かぶさる・積み重なる」からかもしれない。あるいは、掛け算がいっぱい「風呂敷のようなものに包み込まれている」「布を敷いたように広がる」からかもしれない。

【1】　べき（累乗）は基本計算の一つだけど、数論ではべき剰余（べきを何かで割った余り）が重要な意味を持つ。次の表は、b のべきと、それを素数 p = 11 で割った「べき剰余」の例。

bの自然数乗（上段）と、それを11で割った余り（下段）

	b1	b2	b3	b4	b5
b = 1	1	1	1	1	1
	1☆	1☆	1☆	1☆	1☆
b = 2	2	4	8	16	32
	2	4	8	5	10★
b = 3	3	9	27	81	243
	3	9	5	4	1☆
b = 4	4	16	64	256	1024
	4	5	9	3	1☆
b = 5	5	25	125	625	3125
	5	3	4	9	1☆

6乗以降が書いてないけど、これは上の表から簡単に分かる。b = 3 のように b⁵ ≡ 1 (mod 11) の場合、
　　3, 9, 5, 4, 1☆; 3, 9, 5, 4, 1♪
のように、周期5で同じことの繰り返し。なぜなら…
　　3⁶ = (3⁵) × 3¹ ≡ (1) × 3¹ ≡ 3
　　3⁷ = (3⁵) × 3² ≡ (1) × 3² ≡ 9
　　3⁸ = (3⁵) × 3³ ≡ (1) × 3³ ≡ 5
　　3⁹ = (3⁵) × 3⁴ ≡ (1) × 3⁴ ≡ 4
　　3¹⁰ = (3⁵) × 3⁵ ≡ (1) × 3⁵ ≡ 1　　←ここは「小定理」の例
…となるから。一方、b = 2 のように b⁵ ≡ 10 ≡ −1 (mod 11) の場合、
　　2, 4, 8, 5, −1★; −2, −4, −8, −5, 1♪
のように、後半は前半と符号が逆（絶対値は同じ）。なぜなら…
　　2⁶ = (2⁵) × 2¹ ≡ (−1) × 2¹ ≡ −2 (≡ 9)
　　2⁷ = (2⁵) × 2² ≡ (−1) × 2² ≡ −4 (≡ 7)
　　2⁸ = (2⁵) × 2³ ≡ (−1) × 2³ ≡ −8 (≡ 3)
　　2⁹ = (2⁵) × 2⁴ ≡ (−1) × 2⁴ ≡ −5 (≡ 6)
　　2¹⁰ = (2⁵) × 2⁵ ≡ (−1) × 2⁵ ≡ 1　　←ここは「小定理」の例
…となるから。

p−1 乗（つまり「10乗」）では、フェルマーの小定理が発動される。そこへ至る中間地点「5乗」――つまり b^p−1 = b¹⁰ に対する b^(p−1)/2 = b⁵――が、パターンの分かれ目になることに注目。b⁵ ≡ −1 なら10乗して初めて ≡ 1 になるので、b の位数は10（原始根）。上の表では、2 の位数がこれに当たる。一方、b⁵ ≡ 1 なら5乗の段階で既に ≡ 1 なので、b の位数は 5 以下。上の表を見ると、3, 4, 5 はどれも位数が 5 で、1 は位数が 1 になってる。

b = 6 以降も書いてないけど、例えば b = 6 ≡ −5 (mod 11) なので、6ⁿ の代わりに (−5)ⁿ を考えれば、5ⁿ とほとんど同じ――ただし、奇数乗の場合だけ、符号が逆になる。
　　5¹ ≡ 5 なので　6¹ ≡ (−5)¹ ≡ −5 (≡ 6)
　　5² ≡ 3 なので　6² ≡ (−5)² ≡ 3
　　5³ ≡ 4 なので　6³ ≡ (−5)³ ≡ −4 (≡ 7)
　　5⁴ ≡ 9 なので　6⁴ ≡ (−5)⁴ ≡ 9
…以下同様。この場合、b⁵ ≡ 1 なら (−b)⁵ ≡ −1 で、b⁵ ≡ −1 なら (−b)⁵ ≡ 1。そのことから、b = 6 ≡ −5 と b = 7 ≡ −4 と b = 8 ≡ −3 は、どれも位数10（5乗の段階では ≡ −1 なので）。b = 9 = −2 と b = 10 ≡ −1 は位数 5 以下（5乗の段階で既に ≡ 1 なので）: 具体的に、9 の位数は 5 で、10の位数は 2。意味が分かりにくければ、b = 10 まで、1乗から10乗のべき剰余の表を自分で全部書いてみよう。todo ここ不親切。実際にでかい表をリンクしてイメージ的に目で見て分かるようにした方がいい。

【2】　整理すると、次のことを確認できる: mod 11 では、b = 1 の位数は 1、b = 10 の位数は 2、b = 3, 4, 5, 9 はどれも位数 5 で、b = 2, 6, 7, 8 はどれも位数 10。そして、
　　x² ≡ 1 (mod 11)　は2個の解を持ち（x = 1, 10）、
　　x⁵ ≡ 1 (mod 11)　は5個の解を持つ（x = 1, 3, 4, 5, 9）。

「その3」では、mod 7 で次が成り立つことを観察したけど、mod 11 でも同様のことが成り立ってる！

補助定理2　p を素数とする。自然数 d を p−1 の任意の約数とすると、x^d ≡ 1 (mod p) はちょうど d 個の解を持つ。

解の個数については、mod p において合同なものは「同じ1種類の解」と考え、mod p において合同でないものだけを別々の解としてカウントする。

todo 高木の説明の方が分かりやすい?

【3】　補助定理2を証明するには、「xⁿ − yⁿ は x − y で割り切れる」で確かめた式「う」が役立つ:

• xⁿ − yⁿ = (x − y)(xⁿ⁻¹ + xⁿ⁻²y¹ + xⁿ⁻³y² + … + x²yⁿ⁻³ + x¹yⁿ⁻² + yⁿ⁻¹)

このゴチャゴチャした式は、y = 1 の場合、シンプルできれいな式になる:

• x² − 1 = (x − 1)(x + 1)
• x³ − 1 = (x − 1)(x² + x + 1)
• x⁴ − 1 = (x − 1)(x³ + x² + x + 1)
• …
• xⁿ − 1 = (x − 1)(xⁿ⁻¹ + xⁿ⁻² + xⁿ⁻³ + … + x² + x + 1)　　‥‥‥「ア」

todo 上の式自体、面白いので、遊びのおまけメモを追加。

さて、d が p−1 の約数なら、もちろん p−1 は d で割り切れる。その商を q としよう: p−1 = dq。このとき
　　x^p−1 ≡ 1　つまり　x^p−1 − 1 ≡ 0 (mod p)　　‥‥‥「イ」
を、こう書き換えることができる:
　　x^dq − 1 = (x^d)^q − 1 ≡ 0　　‥‥‥「ウ」
(x^d) を w として「ア」を使うと、「ウ」は:
　　w^q − 1 = (w − 1)(w^q−1 + w^q−2 + w^q−3 + … + w² + w + 1) ≡ 0　　‥‥‥「エ」

「エ」が成り立つためには、
　　w − 1 = x^d − 1 ≡ 0　　‥‥‥「オ」
が成り立つか、または
　　w^q−1 + w^q−2 + … + 1 = (x^d)^q−1 + (x^d)^q−2 + … + 1 ≡ 0　　‥‥‥「カ」
が成り立つ必要がある。

なぜ？　AB ≡ 0 (mod p) なら A ≡ 0 または B ≡ 0 だから。「2数の積が0なら、どちらかの数が0」というのは、普通の感覚としては当たり前。とりあえず「当たり前」と流していいけど、mod p でもそうなる（「時計ワールド」付録・命題2）。

「オ」は x についての d 次方程式なので、その解は d 個以内（なぜ？）。同様に「カ」は x についての d(q−1) 次方程式なので、その解は d(q−1) 個以内。だから「エ」を満たす x の合計個数（＝「オ」の解の個数＋「カ」の解の個数）は、最大でも
　　d + d(q−1) = d + dq − d = dq = p−1 個。

ところで、フェルマーの小定理により「イ」には p−1 個の解がある。「エ」は「イ」を変形しただけで、内容的には全く同じ方程式。だから、もちろん「エ」にも同じ数（p−1 個――それは上記の最大合計個数に当たる）の解がある。従って「オ」は、上限いっぱいの d 個の解を持たなければならない。要するに
　　x^d − 1 ≡ 0　つまり　x^d ≡ 1 (mod p)
は、ちょうど d 個の解を持つ。これが証明したいことだった。□

補助定理2とその証明は、William Stein の教科書の命題 2.5.5（PDF版41ページ）に当たる。「エ」が p−1 個の解を持つためには、「オ」も「カ」も、それぞれ上限いっぱいの個数の解を持つしかなく、しかも前者の解と後者の解に重複はない。「1個でも解の種類が減ってしまうと、条件を満たせない（フェルマーの小定理と不整合になる）」というぎりぎりの状態。

todo 証明の内容が具体例でどうなるか別のメモを追加。

2022-01-18　げんしこん（その5）　2数の積の約数は…

原始根の存在の証明は、難しくはないものの、意外と見通しが悪い。なるべくすっきりさせたい。

まずは基礎の復習から…

【1】　例えば、自然数 e = 20 は、3個の素数の積として、2 × 2 × 5 と分解される（もちろん 2² × 5 と書いてもいい）。この e の約数は（自然数の範囲では）、次のように 1 または素因数から構成される:

20 = 2 × 2 × 5 の約数たち
1　（0個の素数から成る）
2 = 2　（1個の素数から成る）
5 = 5　（1個の素数から成る）
4 = 2 × 2　（2個の素数から成る）
10 = 2 × 5　（2個の素数から成る）
20 = 2 × 2 × 5　（3個の素数から成る）

一般に、自然数 e が t 個の素数 p₁, p₂, …, p_t の積に等しいとき、e の約数は、素因数 p_○ たちの幾つか（0 個以上）の積。ここで p_○ はどれも素数だが、必ずしも相異ならない: 全部別々でもいいし、上の例の 2 のように、同じ素因数が複数個あっても構わない。

ここで p_○（ピー・まる） は p₁, p₂ などの総称。○の中には 1 ～ t の何かが入る。

同様に、自然数 f が u 個の素数 q₁, q₂, …, q_u の積に等しいとき、f の約数は、素因数 q_○ たちの幾つか（0 個以上）の積。例えば f = 21 = 3 × 7 の約数は――素因数 3 と 7 を q_○ たちと呼ぶと―― q_○ たちを0個含む 1 と、q_○ たちを1個含む 3 or 7 と、q_○ たちを2個含む 3 × 7 = 21 があり、それ以外の約数はない。

【2】　では e と f の積…
　　ef = (p₁p₂…p_t) × (q₁q₂…q_u)
…の約数は、どんな成分を持つか？

もちろん p_○ たちの幾つかと q_○ たちの幾つかだろう。ここで「幾つか」というのは、本当に幾つでもいい（0個や1個や全部を選んでも構わない）。例えば e = 20, f = 21 の場合、60 は ef = 420 の約数だが、その 60 という数は「3個の p_○ たち 2 × 2 × 5 = 20」と「1個の q_○ たち ３」の積。

このとき、もし e と f が互いに素なら（つまり、e と f の最大公約数が 1 なら）、p_○ たちと q_○ たちの間に、共通の数は一つもない。だって、もし仮に p_○ たちのどれか p_? と、q_○ たちのどれか q_? が等しいとすると、その等しい数 p_? = q_?（この素数を S としよう）は e と f に共通の素因数: e と f が2以上の公約数 S を持つことになって、互いに素という条件に反する。p_○ たちの内部や、q_○ たちの内部には、同じ素因数が複数個あってもいいけれど、p_○ たちと q_○ たちの間に、種族を超えて（？）共通因子が生じることはない―― e と f が互いに素ならね！

ということは…。e と f が互いに素の場合、ef の任意の約数 d について「d の成分として p_○ たちの幾つかと q_○ たちの幾つかを選ぶ方法」は、必ず一定になる。「d の素因数 s については、p_○ から選んでも q_○ から選んでもいい」みたいな状況は、起きない。p_○ たちと q_○ たちは「共通点が一つもない別々のグループ」なので、s は前者に属するか後者に属するかのどっちか。つまり
　　d = (p_○ たちの幾つかの積) × (q_○ たちの幾つかの積)　　‥‥　①
の形で書くことができ、右辺の1個目の丸かっこ内と2個目の丸かっこ内は、（d の値に応じて）決まった値になる。ef = 420 の約数 d = 60 の例で言えば、1個目の丸かっこ内は 20、2個目の丸かっこ内は 3。

「幾つかの」というのは、0個や1個でも構わない。「1個の数の積」とは、その数自身。「0個の数の積」とは、「素数の因子を1個も含まない約数」つまり 1 を意味する。

①右辺の「p_○ たちの幾つかの積」を P として、「q_○ たちの幾つかの積」を Q とすると:

e と f が互いに素のとき、ef の任意の約数 d は、d = PQ の形で表される。ここで P は e の約数、Q は f の約数（【1】参照）。P と Q は（d の値に応じて）一定の値。

再び e = 20, f = 21, ef = 420, d = 60 の例で言うと、「d = 6 × 10 とも書けるから P = 6, Q = 10 とかでも、いいんじゃね？」という主張は通らない。「P は e の約数（e の成分である p_○ たちから成る）、Q は f の約数（f の成分である q_○ たちから成る）、そして e と f は互いに素」という前提なので、P と Q の選び方は P = 20, Q = 3 に限定される。

P は e の約数なので、当然 e は P で割り切れる。その商を U としよう: e = PU。同様に Q は f の約数なので f は Q で割り切れ、その商を V とすれば f = QV。つまり:

e と f が互いに素のとき、ef の任意の約数 d は d = PQ の形で表され、しかも e = PU, f = QV という分解が成り立つ。

【3】　さて、次の補助定理を証明したい。

補助定理3　ある素数を選び、それを法とする。a の位数を e として、b の位数を f とする。もし e と f が互いに素なら、a と b の積 c = ab の位数は、ef に等しい。

解説　これって実は、当たり前！　なぜ？　1乗・2乗・3乗…を考え、○乗ごとに ≡ 1 になるのを「○日おきに仕事が休み」とイメージしてみよう。例えば、3日おきに仕事が休みの a さんと、5日おきに仕事が休みの b さんのカップルが、同時に休日になってデートに行けるのは、15日に1回の周期。3 と 5 は互いに素なので。「休み」の周期が互いに素なら、位数が他の値でも同様。todo これが一目瞭然になるような図解を追加

証明　位数についての仮定から a^e ≡ 1, b^f ≡ 1 (mod p) なので:
　　c^ef = (ab)^ef = a^ef × b^ef = (a^e)^f × (b^f)^e ≡ (1)^f × (1)^e = 1

ここで思い出そう。c^□ ≡ 1 の□に当てはまる数は、必ず c の位数の倍数だ…という事実を（補助定理1）。c の位数を d とすると、ef は d の倍数、言い換えれば d は ef の約数。【2】で確かめたように、こう書ける:
　　d = PQ　　‥‥　②
　　ここで e = PU　　‥‥　③
　　そして f = QV　　‥‥　④

d は c の位数だから当然 c^d ≡ 1。←この式に c = ab と②を代入すると:
　　(ab)^PQ ≡ 1　　‥‥　⑤

⑤の両辺を U 乗すると:
　　[(ab)^PQ]^U ≡ 1^U
　　(ab)^PQU = (ab)^PUQ ≡ 1　　［← 1は何乗しても1なので］
③の e = PU を使うと:
　　(ab)^PUQ = (ab)^eQ = a^eQ × b^eQ ≡ 1　　‥‥　⑥
a の位数は e なので、a^eQ = (a^e)^Q ≡ (1)^Q = 1 となり、⑥は次を意味する:
　　1 × b^eQ = b^eQ ≡ 1

ここで再び思い出そう。b^□ ≡ 1 の□に当てはまる数は、必ず b の位数 f の倍数だ…という事実を（補助定理1）。だから、上記 b^eQ ≡ 1 が成り立つためには、どうしても eQ が f の倍数になる必要がある。

ところが e と f は互いに素。e を素数 p_○ たちの積、f を素数 q_○ たちの積とすると（【1】【2】参照）、
　　eQ が f の倍数　つまり　「q_○ たちの積」の倍数
…になるのなら、eQ は、素因数として q_○ たちを全部含んでいる必要がある。なぜなら、p_○ たちと q_○ たちの間には共通の数が一つもないので、「q_? を含んでなくてもいいよ。代わりに、それと等しい p_? を使える。その因子なら e にも含まれてるから大丈夫」みたいに「代役を立てる」ことができない: e は「f を構成する部品」を1個も含んでないので（＝互いに素）、f の倍数を作る上で「何の協力もできない・全然役立たない」。そうすると、eQ が f の倍数になるためには、Q 自身が（q_○ たちを全て含んで）自力で f の倍数になるしかない。

でも Q って f の約数じゃん（④参照）？　f の約数ってことは、当然 f 以下だよね。それが f の倍数になるなんて、あり得るか…？

あり得るんだよね、唯一の可能性が。それは Q = f というケース。それなら、f は Q で割り切れ（商は1）、Q は f の約数。そして Q は f の1倍なので、f の倍数でもある。…結局、④の f = QV という分解は、Q = f, V = 1, f = f × 1 という単純な話だった！

同様に、⑤の両辺を V 乗して、④の f = VQ を使うと:
　　[(ab)^PQ]^V = (ab)^PQV = (ab)^Pf ≡ 1
　　つまり　a^Pf × b^Pf ≡ 1　　‥‥　⑦

前半とほとんど同じ議論になって、今度は b^Pf = (b^f)^P ≡ 1 が消えちゃうよ。だから、⑦は a^Pf ≡ 1 という意味を持つ。またまた補助定理1によって、Pf は、a の位数 e の倍数。ところが、e と f は互いに素なので、f は e の倍数を作るのには全然役立たず、Pf が e の倍数になるためには P 自身が e の倍数になるしかない…。結局、③の e = PU という分解は、P = e, U = 1, e = e × 1 だと分かる。

結論として、②の d = PQ の実態は、P = e, Q = f, d = PQ = ef であり、c = ab の位数 d は ef に等しい。これが証明したいことだった。□

【4】　補助定理3は、2個の位数が互いに素なら「積の位数は、位数の積」ということを言っている。

《例》　mod 7 で a = 4 の位数 e = 3 と、b = 6 の位数 f = 2 を考えると、3 と 2 は互いに素。だから c = ab = 4 × 3 = 12 ≡ 5 の位数は ef = 6 になるはず。リンク先の表を見ると、確かに 5 の位数は 6 になってる。mod 7 では 12 と 5 は同じ要素の別名なので「12 の位数が 6」と言っても構わない。実際、mod 7（曜日ワールド）では、7の倍数の違いが無視されるので、こんなふうにn乗を計算できる（二項定理を大ざっぱに使用）:
　　12ⁿ = (7 + 5)ⁿ = 7ⁿ + 係数×7ⁿ⁻¹×5¹ + 係数×7ⁿ⁻²×5² + … + 5ⁿ = 7の倍数たち + 5ⁿ ≡ 5ⁿ
もっと露骨に言えば、12⁶ = 2985984 を 7 で割ると 1 余るので、12⁶ ≡ 1 (mod 7)。12の1乗・2乗・3乗・4乗・5乗は ≡ 1 にならない。

数論の命題は、簡単そうに見えて、意外と繊細で奥が深く、分かりにくいことがある。でも補助定理3は、「カップルの休日」の例えのように、イメージをつかめれば当たり前。

書いてある内容を一生懸命「暗記」するんじゃなく、空気のように「当たり前」と思えるまで、全ステップを慎重に（必要なら、自分で具体例を考えながら）、繰り返し検討しよう。【3】の後半は、前半より省略した記述になっているので、とりあえず自力で全ステップを検討してみるのもいいかも…。

ともかく、解の個数についての定理と、補助定理1・2・3によって、「原始根の存在証明」を攻略する準備は整った。…次回はやるぜ！

補助定理3とその証明は、William Stein の教科書の補題 2.5.7（PDF版42ページ）に当たる。原始根の存在については、予定通り Stein の証明を最初に紹介し、次に証明の改善（もっと簡潔な別ルート）を試みたい。

2022-01-22　げんしこん（その6）　存在の証明

予告したように以下は「教科書の方法」。この連載の目標は「もっと分かりやすい方法・面白いやり方」を探ることだが、出発点として、まず普通のやり方でやってみる。

【1】　一例として、素数 p = 17 について、mod p の世界には原始根が存在することを示す。a を任意の数（p の倍数以外）とする。

p − 1 = 16 (= 2⁴)。フェルマーの小定理により a^p−1 = a¹⁶ ≡ 1 (mod 17) なので、この世界では、任意の a の位数は、16の約数。だって、補助定理1から、a^□ ≡ 1 の□に当てはまる数は「a の位数（それを e とする）の倍数」: 16 は□に当てはまるんだから e の倍数、つまり e は 16 の約数。

8 は p − 1 = 16 の約数だから、補助定理2によって、
　　x⁸ ≡ 1 (mod 17)　　‥‥　➊
は、8 個の解を持つ。16 自身も 16 の約数だから、補助定理2によって、
　　x¹⁶ ≡ 1 (mod 17)　　‥‥　➋
は、16 個の解を持つ。➊の両辺を2乗すると➋なので、➊を満たす 8 個の x は全部、➋も満たす。でも逆に、➋の 16 個の解が➊の解にもなるとは、限らない: ➊の解は 8 個しかないのに、➋の解は 16 個もあるんだから、どう考えても「➋を満たすけど➊を満たさない x」が 16 − 8 個（つまり 8 個）あるよね。

重大な観察: そのような 8 種類の x ――➋を満たすが➊を満たさない――の位数は、どれも 16。

なぜ？

だって、どの数の位数も、p−1 = 16 の約数じゃん（復習？）。上記「8 種類の x」の位数も 1, 2, 4, 8, 16 のどれかだけど、➊を満たさないんだから、位数 8 ではない。この状況で、位数 4 とかになり得ると思う？　位数 4 ってことは
　　x⁴ ≡ 1 (mod 17)
だけど、それが本当なら、その両辺を2乗すれば➊になり、この x は➊を成立させてしまう――➊を満たさないことは既に分かってるんだから、これはあり得ない！

イメージの世界　→　「8日おきに仕事が休みでデートに行ける」という周期じゃない x さんは、ましてや「半分の周期の4日おきに仕事が休み」になるわけない（もし4の倍数の日が休日なら、8の倍数の日も休日だが、そうではないと仮定している）。

同様に、位数 2 なら x² ≡ 1 だが、それが成り立つなら、その両辺を4乗すると➊が成り立ってしまい、つじつまが合わない。全く同様に位数 1 もあり得ない。

かくして、p = 17 のとき、mod p の世界には位数 p−1 (=16) の元が（8種類も！）存在する。「原始根」の定義により、これら 8 個の元は、どれも原始根…

概念・用語の再確認　→　aⁿ ≡ 1 (mod p) を満たす最小の正の整数 n が a の位数。位数が p−1 に等しいような a が、原始根。

すなわち、p = 17 について、原始根の存在が証明された！

もちろんこれは p = 17 という特定のケースにすぎず、まだ任意の素数 p に対する証明にはなっていない。けれど、最初の一歩としては、満足すべき成果だろう。

【2】　上の例では、p−1 が 2⁴ という一つの「素数べき」だった（「べき」とは指数乗のこと）。そして、解の個数についての簡単な議論から「位数がその 2⁴ に等しい x が存在すること」が示された。

もし p−1 = u^○v^△ のように複数個の素数べきの積となる場合でも（u, v は相異なる素数）、一つ一つの素数べきについて上と同じ論法を使えば、位数 u^○ の元 x の存在、位数 v^△ の元 y の存在…を示すことができる。詳細は次の節で扱うが、補助定理3（積の位数は位数の積）を使えば、xy の位数は u^○v^△ つまり p−1 となり、xy という原始根の存在が示される。

だから、本質的には【1】の例だけでもう証明は完了している。後は、のんびり仕上げればいい。

けど、mod 17 に8個の原始根があるという【1】の結論は、何となく「多い」気もする。原始根って、そんなにいっぱいあるものなのだろうか…。17は小さい数なので、全数検索で検証してみよう（コピペで手抜き）。

       b^1  b^2  b^3  b^4  n^5  b^6  b^7  b^8
b=1     1    1    1    1    1    1    1    1  位数＝1
b=16   -1    1   -1    1   -1    1   -1    1  位数＝2
// 偶数乗は上をコピペ、奇数乗は符号を変えてコピペ（以下同じ）

b=2     2    4    8   -1   -2   -4   -8   +1  位数＝8
b=15   -2    4   -8   -1   +2   -4   +8   +1  位数＝8
// 計算の省力化のため、16が出現したら-1に置き換える

b=3     3    9   10   13    5   15   11   -1  位数＝16（原始根）
b=14   -3    9  -10   13   -5   15  -11   -1  位数＝16（原始根）
// 位数は16の約数なので、8以下でなければ必然的に16（原始根）。だから8乗まで調べれば十分

b=4     4   -1   -4    1    4   -1   -4   +1  位数＝4
b=13   -4   -1   +4    1   -4   -1   +4   +1  位数＝4

b=5     5    8    6   13   14    2   10   -1  位数＝16（原始根）
b=12   -5    8   -6   13  -14    2  -10   -1  位数＝16（原始根）

b=6     6    2   12    4    7    8   14   -1  位数＝16（原始根）
b=11   -6    2  -12    4   -7    8  -14   -1  位数＝16（原始根）

b=7     7   15    3    4   11    9   12   -1  位数＝16（原始根）
b=10   -7   15   -3    4  -11    9  -12   -1  位数＝16（原始根）

b=8     8   13    2   -1   -8  -13   -2   +1  位数＝8
b=9    -8   13   -2   -1   +8  -13   +2   +1  位数＝8

上記は「見て理解してもらうための表」というより「数値的検証」の例（プログラムでいえば、動作確認・デバッグ）。「証明の内容を頭では理解できるけど、実感が湧かない・何かもやもやする」というとき、数値的に泥くさく試してみると、いろんなことが体感される。実際に計算する場合、例えば次の行は…

       b^1  b^2  b^3  b^4  n^5  b^6  b^7  b^8
b=5     5    8    6   13   14    2   10   -1

正直に 5³ = 125 や 5⁴ = 625 を 17 で割って、それぞれ余り 6 と 13 を得てもいいのだが、直前の余りを再利用して、8 の 5 倍を 17 で割ると余り 6、その 6 の 5 倍を 17 で割ると余り 13 …のように次々と進めれば、1～2桁の掛け算・割り算だけで済む。

ともかく、一覧表にしてみると、本当に原始根が 8 個ある！　x¹ ≡ 1, x² ≡ 1, x⁴ ≡ 1, x⁸ ≡ 1 の解の個数がそれぞれ 1, 2, 4, 8 であることにも注目。補助定理2の通り。それぞれ、位数が1以下、2以下、4以下、8以下の b の個数に当たる。

上のようなゴチャゴチャした表には、往々にして計算ミスやミスタイプが含まれている。書いてあることをうのみにせず、自分で検証してほしい。

【3】　【1】では p = 17 について、p−1 = 2⁴ = 16 と 2³ = 8 を考えた。Q = 2⁴, q = 2³ と書くと、
　　x^Q ≡ 1　と　x^q ≡ 1 (mod p)　の解の個数の違い
が、証明の鍵だった。

それに倣って、今度は素数 p = 19 について、mod p の世界にも原始根が存在することを示す。
　　p−1 = 18 = 2¹ × 3² = QR
　　ここで Q = 2¹ = 2, R = 3² = 9
…としよう。上記同様、指数を 1 減らした素数べきを考え、
　　Q = 2¹ = 2, R = 3² に対して
　　q = 2⁰ = 1, r = 3¹ = 3
と置く（便宜上、素数そのものも「素数の1乗」、素数ではない 1 も「素数の0乗」と見なす）。

r = 3 は p − 1 = 18 の約数だから、補助定理2によって、
　　y^r = y³ ≡ 1 (mod 19)　　‥‥　➌
は、3 個の解を持つ。R = 9 も 18 の約数だから、
　　y^R = y⁹ ≡ 1 (mod 19)　　‥‥　➍
は、9 個の解を持つ。➌の両辺を3乗すると➍なので、➌を満たす 3 個の y は全部、➍も満たす。でも逆に、➍の 9 個の解が➌の解にもなるとは、限らない。【1】と同様の議論により、「➍を満たすが➌を満たさない y」が R − r = 6 個存在し、それらの y の位数は、どれも R = 9 となる。

位数は p−1 = 18 の約数で、しかも考えている y は➍を見たすので、9乗ごとに ≡ 1 になる必要があり、従って ≡ 1 になる周期（つまり位数）は 1, 3, 9 のどれか。➌を満たさないので、位数3は不可能。位数1なら、y¹ ≡ 1 となり、その両辺を3乗すると、➌を満たしてしまうので、それも不可能。

全く同様に、q = 1 は p − 1 = 18 の約数だから、
　　x^q = x¹ ≡ 1 (mod 19)　　‥‥　➎
は、1 個の解を持ち、Q = 2 も 18 の約数だから、
　　x^Q = x² ≡ 1 (mod 19)　　‥‥　➏
は、2 個の解を持つ。「➏を満たすが➎を満たさない x」が Q − q = 1 個存在し、そのような x の位数は Q = 2。

これは「x² ≡ 1 だが x ≡ 1 ではない」という意味なので、要するに x ≡ −1 (≡ 18)。

「➏を満たすが➎を満たさない x」（1種類だけ存在）と、「➍を満たすが➌を満たさない y」（6種類存在）の積 xy を考えると（そのような積は6種類存在）、前者の位数 Q = 2 と後者の位数 R = 9 は互いに素（異なる素数 2 と 3 のべきなので）。従って、補助定理3により xy の位数は QR = 18 = p−1。すなわち、p = 19 を法として（6種類の）原始根の存在が示された。

y⁹ ≡ 1 を満たす y を検索すると {1, 4, 5, 6, 7, 9, 11, 16, 17}。y³ ≡ 1 を満たす y を検索すると {1, 7, 11}。次の6種（前者の要素のうち、後者の要素ではないもの）が、位数9:
　　A = {4, 5, 6, 9, 16, 17}
位数2の元 x ≡ −1 と、A の任意の元 y を掛け算すると、位数 2 × 9 = 18 の元（原始根）が得られる。具体的には、次の6種:
　　{−4, −5, −6, −9, −16, −17} ≡ {2, 3, 10, 13, 14, 15}
ここで −4 ≡ −4 + 19 = 15, −5 ≡ −5 + 19 = 14, etc.

【4】　より一般的に、3 以上の任意の素数 p が与えられたとき、p−1 の素因数分解を
　　p−1 = u^ev^fw^g…
としよう。ここで u, v, w, … は相異なる素数、指数 e, f, g, … は 1 以上の整数。Q = u^e, R = v^f, S = w^g, … と置くと、
　　p−1 = QRS…
のように、p−1 は「1個以上の素数べき（指数は1以上）」の積となる。素数べき Q, R, S, … の指数を 1 減らしたものをそれぞれ q = u^e−1, r = v^f−1, s = w^g−1, … とすると q, r, s, … も素数べき（指数は0以上）。

《例》　p = 541 のとき:
　　p−1 = 540 (= 4 × 27 × 5) を素因数分解すると 2² × 3³ × 5¹
　　Q = 2² = 4, q = 2¹ = 2
　　R = 3³ = 27, r = 3² = 9
　　S = 5¹ = 5, s = 5⁰ = 1
　　細かく言うと　u = 2, e = 2; v = 3, f = 3; w = 5, g = 1

このとき、【3】と同様、mod p において:
　　x^Q ≡ 1 を満たすが x^q ≡ 1 を満たさない x が Q − q 個存在し、位数 Q
　　y^R ≡ 1 を満たすが y^r ≡ 1 を満たさない y が R − r 個存在し、位数 R
　　z^S ≡ 1 を満たすが z^s ≡ 1 を満たさない z が S − s 個存在し、位数 S
　　etc.

上記の条件を満たす x, y について、それらの位数 Q, R は互いに素（両者は、相異なる素数 u, v のべきだから）。従って、補助定理3により xy の位数は QR。同様に、xy と z について、それらの位数 QR, S は互いに素（後者は、u とも v とも異なる素数 w のべきだから）。従って、同じ補助定理3により (xy)z の位数は (QR)S。

もちろん xy という積は何らかの値を持ち、QR という積は何らか値を持つ。xy = c, QR = D とすれば、c の位数 D は、z の位数 S と互いに素なので、cz の位数は DS。文字を元に戻せば、xyz の位数は QRS。

…この議論は何度でも反復できるので、結局 xyz… の位数は QRS… つまり p−1 に等しい。言い換えれば、mod p において、位数 p−1 の元（つまり原始根）が必ず存在する！

4個以上の素数べきの積を考える場合、上の書き方では「z の次の文字」がなくて困るが、文字が不足したら、適当に z の次は z′ とでもして、そのまた次は z″ とでもすればいい。

形式的な一般論は以上の通りだが、現実的には、p が小さい場合、指数 e, f などが 1 であることが多い（p = 7 つまり mod 7 における p−1 = 2¹ × 3¹ のように）。例えば e = 1 の場合、Q = u^e = u¹ とは素数 u 自身のことだし、q = u^e−1 = u⁰ とは 1 のこと。その場合、
　　x^Q ≡ 1 を満たすが x^q ≡ 1 を満たさない x
とは、
　　x^u ≡ 1 を満たすが x¹ ≡ 1 を満たさない x
のことで、
　　x^u ≡ 1 の解のうち x ≡ 1 以外のもの
という単純な意味になる。

【5】　最後に、特別な場合として、素数 p = 2 を法としよう。この場合、p−1 = 1 は、素数でも合成数でもなく、1個以上の素数の積として表現されないため、上記の証明法を適用できない。けれど、原始根の定義を直接使うと、要するに位数 p−1 = 1 の元を見つければいい。a の位数とは aⁿ ≡ 1 (mod p) を満たす最小の正の整数。mod 2 では、単に a = 1 とすれば、その位数は 1 であり、つまり 1 が原始根。…この事実は、自明な（＝つまらない・形式的な）ことにすぎないけど、p = 2 も含めて「任意の素数 p について、mod p の世界には、原始根が存在する」ということになる。□

今回の証明は、William Stein の教科書の定理 2.5.8（PDF版42～43ページ）に当たる。はっきり言って、あまり分かりやすくない。次回以降、いろいろ別の証明法を考えてみたい。

2022-01-26　げんしこん（その7）　おまえはもう矛盾している

原始根の存在証明について。教科書のやり方は、それなりにエレガントだし有益だが、「もうちょっと分かりやすくできないの？」という感じもする。非構成的な存在証明でありながら、原始根のレシピを細かく分析してるところが、回りくどい。

【1】　直線的に、いきなり核心を否定して「もしも原始根がなかったら…」と考えてみよう。つまり p を3以上のとある素数として、mod p における最大の位数が p−1 より小さい…と仮定する。位数は p−1 の約数（補助定理1.1）…それが最大でも p−1 未満ってことは…。その世界では、位数は最大でも (p−1)/2、下手すりゃ (p−1)/3 や (p−1)/4 かもしれない…。こう考えた瞬間、反射的に
　　異議ありっ！　矛盾です！
と思わないだろうか。例えば、もし仮に何でもかんでも (p−1)/2 乗で ≡ 1 になってしまうとすると、それは x = 1, 2, 3, …, p−1 の p−1 種類の元が
　　x^(p−1)/2 ≡ 1
を満たすということ。上記は (p−1)/2 次方程式なので、解の種類は (p−1)/2 個以下のはずであり、「そんなわけない」という強い直観が働く。

要するに、「原始根が存在しない」と仮定すれば、たちまち矛盾が生じるだろう。

【2】　このスピード感・速攻を実際の証明とするための鍵となるのが、次の命題。以下 0 ではない元だけを考える（もちろん 0 と合同な元も除外）。

テクニカル命題　mod p において、全種類の元の位数を調べたとして、一番でかい位数は d だった…とする（位数 d の元の一つを a とする）。この世界において、任意の元 b の位数 e は、d の約数。

解説　実際には、既に d = p−1 であること（＝原始根の存在）を証明済みだし、任意の位数は p−1 の約数であることも、補助定理1.1の段階で分かっている。よって、この命題はもっと具体的な形で証明済みなのだが、そのことを一時的に少し忘れて、d の値がまだ分からないふりをしよう。ひょっとしたら d = (p−1)/2 などかもしれない…。それでも上の命題が成り立つとすれば: 最大位数が d なら任意の位数は d の約数（例えば d/2 や d/3）ということになり、上述の「異議ありっ」の論証が成立する。変数名 d は dekai isū から。

《例》　mod 19 での最大位数 d が、実際の値 18 ではなく、その半分の 9 だったとしよう。この仮想世界において、上のテクニカル命題によれば、任意の元（≢ 0）の位数は 1, 3, 9 のどれか。ある元 a の位数が 9 なら、もちろん a⁹ ≡ 1。別の元 b の位数が 3 なら、b³ ≡ 1 だが、その両辺を3乗すると、やはり b⁹ ≡ 1。位数 1 の場合も同様。結局、0 と不合同な元を 9 乗すれば常に ≡ 1 になるが、それは「mod 19 において、9次方程式 x⁹ ≡ 1 が18種類の解を持つ」というばかげた主張であり、解の個数に関する根本法則に反している。別の角度から言えば「x⁹ ≡ 1 の解はちょうど 9 種類」という補助定理2とも、矛盾する。

このテクニカル命題を証明することによって「原始根が存在しないこともある」という主張は崩壊し、背理法によって、原始根の存在が確定する。

【3】　この秘孔を突くには（つまりテクニカル命題を証明するには）、「b の位数 e が d の約数ではない」ということの不可能性――要するに、「d が e で割り切れない」なんていう状況は、あり得ねぇんだよ！ということ――を示せばいい。

そもそも「d が e で割り切れない」とは、どういう場合か？

例えば d = qrs と、3個の素数の積に分解されるとしよう。e = qr などなら、d/e は（約分が成立して）割り切れる。一方、分母 e の因子として q, r, s のどれとも違う素数 w が含まれていたら、約分は成立せず（分母の w を分子でキャンセルできず）、この分数は割り切れない。

ここで d = qrs などの数は、位数（要するに指数）の計算に関するものであり、普通の整数の世界の話。mod p の世界における 1/w のような計算とは、関係ない。変数名 w は wake no wakaran sosū から。

仮に e = qw としてみる。その想定が実は無理であることは、次のように簡単に示される。
　　仮定により b^e = b^qw = (b^q)^w ≡ 1
　　　だから　(b^q) の位数は w
　　d = qrs と w は互いに素なので、補助定理3により a(b^q) の位数は dw

(b^q) の位数が w より小さい可能性はない（【5】参照）。

位数 dw の元の存在は「a の位数 d が一番でかい」という仮定に反し、不合理。つまり e = qw と考えると、矛盾が生じる。結局、分母が w（分子には含まれていない訳の分からん素因数）を含む…という状況は、論理的に不可能であり、上記のような形で「d が e で割り切れない」という事態が起きることは、ない。

【4】　より一般的に、分子側も素因数 w を含む…という可能性を考慮しよう、d = qrsw² のように。その場合でも、e がさらに多くの個数の w を含んでいれば（例: e = qw³）、d/e は割り切れない。すなわち、ある素数 w について、d の素因数分解に含まれる w のべき（冪）を V = w^j として、e の素因数分解に含まれる w のべきを W = w^k としたとき、j < k であれば（つまり V < W であれば）、d/e は割り切れない。…素数 w のべき以外にも、分母には割り切れない原因が二重・三重にあるかもしれないが、いずれにしても少なくとも一つの素数べきについて「分母側の指数の方が大きい」ということが、「割り切れない」という状況の必要十分条件。【3】では、その特別な場合として、j = 0, k = 1（つまり V = 1, W = w）のケースを考察したのだった。

対応する全部の素数べきについて、分子側の指数が分母側の指数以上なら、その分数は割り切れる。
例えば (p³q¹r⁵) / (p³q⁰r²) = q¹r³ のように。

今、仮に a の位数 d = qrsV が「一番でかい位数」だとしよう（実際には qrs の部分は、因子 w を含んでなければ何でもいい）。そして b の位数 e = qW が「d の約数ではない位数」の例だとしよう（実際には q の部分は、因子 w を含んでなければ何でもいい）。この場合、次のようにして、容易に位数 qrsW の元を構成でき、それは「一番でかい位数は d = qrsV」という前提と矛盾する。
　　仮定により a^d = a^qrsV = (a^V)^qrs ≡ 1
　　　だから　(a^V) の位数は qrs
　　仮定により b^e = b^qW = (b^q)^W ≡ 1
　　　だから　(b^q) の位数は W
　　qrs と W は互いに素なので、(a^V)(b^q) の位数は qrsW　　‥‥「ひでぶ」

結論として、「位数が d の約数ではない元」が存在すると考えると、矛盾が生じる。だから考えを改めて、前記のテクニカル命題を受け入れるしかない。すなわち、原始根の存在が再び示された。□

【5】　次のタイプの議論についての補足。
　　「仮定により b^e = b^qW = (b^q)^W ≡ 1
　　　だから　(b^q) の位数は W」

この場合、(b^q) を W 乗すれば ≡ 1 なのは明白として、もっと小さい指数で ≡ 1 になる可能性はないか？
　　例えば　(b^q)^u ≡ 1, u < W　　‥‥「あべし」
という u が存在すれば、(b^q) の位数は W より小さい。「位数を小さくできる」なら、「一番でかいはずの位数 d = qrsV より、もっと大きい位数 qrsW が発生」という矛盾を回避できる…？

実は「あべし」の場合、b^qu ≡ 1 となるから、b の位数も qu 以下となり、e = qW より小さい。「b の位数は e = qW」が議論の前提であり、その前提に反する「あべし」は、成り立たない。

2022-01-31　げんしこん（その8）　高木先生の証明法

mod p での原始根の存在（p は素数）について、高木貞治（ていじ）
https://ja.wikipedia.org/wiki/%E9%AB%98%E6%9C%A8%E8%B2%9E%E6%B2%BB
『初等整数論講義』による証明を紹介する。

この本は初版が1931年。今となっては古風だが、「このあたりでひとまず馬を返さねばなるまい」といった楽しそうな文章、親切丁寧な著述態度、そして数論の理想を指摘した美しい序言が、多くの読者に強い感銘を与えてきた。「証明できただけでは満足しない。全てが明快になるまで本質を追究し、より高い見地から見渡したい」という姿勢で貫かれている。

時代が時代なだけに（ブルバキ結成以前でもある）、抽象代数的手法についてはためらいが感じられ、題材の配列には見通しが悪い点もある。裏を返せば、抽象的になり過ぎず質実剛健、遊び心と滋味がある。著作権が切れてウェブ上で読めるが（※）、古本などで安く買える機会があったら、入手しておいて損はない。

（※）今回の内容を含む部分（ja.wikisource）:
https://ws-export.wmcloud.org/?format=pdf&lang=ja&page=%E5%88%9D%E7%AD%89%E6%95%B4%E6%95%B0%E8%AB%96%E8%AC%9B%E7%BE%A9/%E7%AC%AC1%E7%AB%A0/%E5%8E%9F%E5%A7%8B%E6%A0%B9%EF%BC%8C%E6%8C%87%E6%95%B0（JS不要）;
https://ja.wikisource.org/wiki/%E5%88%9D%E7%AD%89%E6%95%B4%E6%95%B0%E8%AB%96%E8%AC%9B%E7%BE%A9/%E7%AC%AC1%E7%AB%A0/%E5%8E%9F%E5%A7%8B%E6%A0%B9%EF%BC%8C%E6%8C%87%E6%95%B0">HTML（要JS）;
［少しミスタイプあり］
同じテキストは https://linesegment.web.fc2.com/ にもあるが、こちらはプライバシー侵害度がやや高い（Tor Browser / uBlock推奨）。侵害要素 googlesyndication; google-analytics; fc2.com/counter_img.php を含む。

【1】　高木による原始根の存在証明は、現代の方法と大きく違うわけではない。次の初等的事実を利用して、全てを補助定理に帰着させている。

補助命題（高木、§4・問題11）　任意の正の整数 e, f について、それらの最小公倍数 L を L = EF と書ける。ただし E は e の正の約数、F は f の正の約数で、E と F は互いに素。

《例》　e = 180 = 2²⋅3²⋅5¹ と f = 200 = 2³⋅5² の最小公倍数は L = 1800。これは、e, f の因子である素数べき（指数は 0 以上）のうち、e, f のどちらか一方から「指数が小さくない方」を抜き出して、掛け合わせたもの: f から 2³ と 5² を抜き出し（対応する e 側の素数べきは、それぞれ 2² と 5¹ であり、もっと小さい）、e から 3² を抜き出し（対応する f 側の素数べきは 3⁰ = 1 に当たり、もっと小さい）、それらを掛け合わせると:
　　L = 2³⋅3²⋅5² = 1800
L の因子のうち e から抜き出したものの積を E、f から抜き出したものの積を F とすれば:
　　E = 3², F = 2³⋅5², L = EF

証明　上の例のように構成した E, F は、それぞれ e, f の幾つか（0個以上）の素因数だけから成る積なので、当然 e, f の約数。E と F は全く別々の素数のべきから成り、だから共通の素因数を持たず、従って2以上の公約数を持たないので、互いに素。□

e = 2²⋅3²⋅5¹ と f = 2³⋅3²⋅5² のように、同一素数の同じべき（指数が等しい。この例では 3²）が e, f 両方に含まれる場合、その素数べきは e, f のどちらから抜き出しても構わない（一方だけから抜き出す必要はある）。命題は「条件を満たす E, F が（少なくとも一組は）存在する」というものであり、「E, F の値が一意的（一つに定まる）」とまでは言っていない。

コメント　e = 2⁴⋅3²⋅5³ と f = 2³⋅3²⋅5² のように、どの素数べきについても e 側が f 側以上である場合には、E = e, F = 1 のように、e 側からは「全部の素数べき」が抜き出され、f 側からは「0個の素数べき」が抜き出されることがあり得る（0個の素因数から成る正の約数 F とは 1 のこと）。これは、要するに e が f の倍数である場合であり、そのときには、e と f の最大公約数 L は e 自身に等しい。L が e に等しいのは、e が f の倍数である場合に限られる。

それ以外の場合には、少なくとも一つの素数べきについて f 側の方が e 側より大きいので、e/f は割り切れず、e は f の倍数ではない。

【2】　以下、mod p において、0 と不合同な元だけを考える。そのような任意の元 a を一つ選び、その位数が e だったとしよう。どんな a を選んでも、遅くとも p−1 乗すれば ≡ 1 になる（フェルマーの小定理）、つまり位数 e は p−1 以下。もし e = p−1 なら、その a が原始根であり、原始根の存在について議論の余地はない（実際に原始根 a が、そこにあるのだから）。そこで e < p−1 と仮定して、その場合でも、e より大きな位数の別の元を構成できることを示そう。この…
　　「ある元の位数が p−1 未満である限り、もっと大きい位数の別の元を見つけられる」
…という事実を必要なだけ繰り返し利用すれば、「もっと大きい位数の元」「さらにもっと大きい位数の元」…を次々に見つけて、いつかは位数が p−1 に等しい元が得られる。つまり、原始根が存在することになる。

さて、最初に選んだ元 a は a^e ≡ 1 を満たすのだから、
　　方程式　x^e ≡ 1　　‥‥「あ」
の解。「あ」には、ちょうど e 種類の解があるので（補助定理2）、mod p の（0 と不合同な） p−1 種類の元の中には、「あ」の解ではないものが (p−1)−e 個、存在する（e < p−1 と仮定しているので、この個数は1以上）。その一つを任意に選んで b とし、b の位数を f としよう。もし e と f が互いに素なら、ab の位数は ef であり（補助定理3）、すなわち積 ab を a₂ とすると、a₂ の位数 ef は e より大きい。

もし f = 1 なら ef は e より大きくならないが、その状況は不可能。なぜなら f = 1 とは、b の位数が 1 ということだが、位数 1 の元は、最初から ≡ 1 であり、それを何乗しても ≡ 1 なので、このような b は「あ」を満たす。これは、b が「あ」の解ではないという仮定に反する。

つまり、最初に選んだ元 a の位数 e と、2回目に選んだ元 b の位数 f とが、互いに素な場合には、「e より大きい位数の元を見つけられる」という主張は簡単に確かめられ（a₂ = ab がそのような元）、証明が完了する。

【3】　それ以外の場合――つまり、e と f が互いに素でない場合。【1】の補助命題のように e の約数 E と、f の約数 F を選べば、E は e の正の約数なので、e/E は割り切れて、正の整数になる。
　　a^(e/E) を A とすると、A の位数は E。
実際、A^E = [a^(e/E)]^E = a^e ≡ 1 であり（なぜなら e は a の位数）、もし E より小さい自然数「小」が A^小 ≡ 1 を満たすとすると、
　　1 ≡ A^小 = [a^(e/E)]^小 = a^e小/E
　　ここで e小/E < eE/E = e
…となるから、e より小さい指数 e小/E が a^○ ≡ 1 を満たすことになり、「a の位数は e」という仮定に矛盾。従って E は、A^□ ≡ 1 を満たす最小の正の指数。同様に:
　　b^(f/F) を B とすると、B の位数は F。

E と F は互いに素なので（【1】の補助命題を参照）、AB の位数は EF = L に等しい（補助定理3）。ところが L は e と f の最小公倍数なので、e の倍数。すなわち積 AB を a₂ とすると、a₂ の位数 EF = L は e より大きい。

L は e の倍数だが、もし e の「1倍」なら（つまり L = e なら）、EF = L は e より大きくならない。しかし、その状況が起きるのは、e が f の倍数の場合に限られる（【1】のコメント参照）。e が f の倍数なら e = fk を満たす自然数 k が存在するが、その場合、b^e = b^fk = (b^f)^k ≡ 1^k = 1 となり（なぜなら f は b の位数）、b は方程式「あ」を満たす。これは、b が「あ」の解ではないという仮定に矛盾。

つまり、最初に選んだ元 a の位数 e と、2回目に選んだ元 b の位数 f とが、互いに素でない場合にも、e より大きい位数の元を見つけられる。具体的には、
　　a₂ = AB = a^(e/E)b^(f/F)
がそのような元の一例。□

【4】　この存在証明の一つの利点は、構成的であること。まず a = 2 を選んで、その位数が p−1 か確かめる。位数 e が p−1 より小さい場合、「あ」の解は次の e 種類:
　　S = {a, a², a³, …, a^e}　ここで a^e ≡ 1
または、同じことだが:
　　S = {a⁰, a¹, a², …, a^e−1}　ここで a⁰ = 1
実際、S の元は、どれも「あ」を満たす。例えば a² について:
　　(a²)^e = (a^e)² ≡ 1² = 1　← 指数 2 を任意の指数 z に置き換えても全く同様

3, 4, 5, …, p−1 の中から、S のどの元とも合同でない最小の整数を選び、それを b とする。後は上記のレシピに従って、位数が e より大きい元 a₂ を構成できる。a₂ の位数が依然として p−1 より小さければ、再び同様の手続きを繰り返し、さらに大きい位数の元 a₃, a₄, … を構成でき、これは上限のある上昇列なので、いつかは必ず上限に達する（そのときの a_□ が原始根）。

証明の仕方も（本質的には）平易で分かりやすい。

一方、技術的短所として、【2】と【3】の関係が分かりにくい。論理的に【3】は【2】と排他的な「場合分け」ではなく、【2】を包含・拡張して「より一般的に」と言うべき場面。【3】では「e と f は互いに素ではない」という仮定は使われず、実際には【3】だけで【2】もカバーされる。ではなぜ高木は、論理的には必要ない【2】を記したのか。その目的は【2】の結論それ自体のためではなく、議論の途中で補助定理3を導くことにあった。本当に必要なのは【2】自体ではなく、補助定理3なのだから、それを念頭に題材を配列した方が、すっきりしただろう。さらに、せっかく構成的な存在証明なのに、補助命題における E, F が一意的でないため、このままでは決定論的アルゴリズムを作れない。

高木の本は名著だが、読者としては、深い敬意を払いつつも、常に「もっと工夫できないか・もっと透明にできないか・ギャップはないか」と吟味・検討するべきだろう。ただ内容を受け身に追う読者より、そのような主体的姿勢で取り組む読者こそが、むしろ高木先生にとっても、うれしいものではないだろうか。「げんしこん（その7）」の証明法は直線的で明快だが、アーベル群論をベースにしていて、抽象的・非構成的。高木の証明法は、少し回りくどいが、具体的・構成的。どちらが分かりやすいと感じるかは、人それぞれだろう。

簡易正誤表

誤	正
21− ≡ 40	210 ≡ 40
210	210
220	220
(k, p−1) ならば，p−1 = d とするとき	(k, p−1) ならば，p−1 = ed とするとき

2022-02-05　「商」と「総」　超入門／オイラーのファイ関数

ハイキングの最終目的地が近づいた。ガウス自身による原始根の存在証明。有名な証明なのでご存じの方も多いかもしれないが、アッと驚く景色。

mod p での原始根の存在自体については、既に教科書的な証明、直線的な別証明、含蓄のある高木の証明と3通りも紹介したので、余裕で「分かり切ったこと」と受け止められるだろう。ガウスの証明に取り組む心の準備はオーケーかと…

異次元的なガウスの証明を理解するには「オイラーのファイ関数」を準備する必要があるのだが…この名前を聞いただけで「難しそう」と尻込みし、φ(φ(p)) のような記号が出てくれば「絶対無理」と諦めてしまう人もいるかもしれない…。

そんなあなたのために（？）、このメモでは、難しそうな記号を一切使わず、言葉だけで必要な定理を証明する。ファイ関数をご存じの方は、ご笑覧ください…。

難しそうに感じるときは、うそでもいいから「私はこれを理解する」と心の中でつぶやいてみよう。

【1】　自然数 A が与えられたとする。「1 以上 A 以下の整数のうちで、A と互いに素なもの」の総数を A の総（そう）と呼ぶことにしよう。言い換えると、A の総とは、
　　「A 以下の自然数の中には、A との最大公約数が 1 であるようなものが何個あるか？」
を数えたもの。

6 の総は 2。なぜなら 1, 2, 3, 4, 5, 6 のうちで 6 と互いに素なものは、1 と 5 の 2 個だから。

7 の総は 6。8 の総は 4。9 の総は 6。

この一見何だか分からないような概念が、重大な意味を持つ…。それに気付いたのは、オイラーだった。オイラーはこの数を π という記号（文字）で表したという。たぶん、互いに「素」（πρῶτος）の π だろう。オイラーの次の世代の天才ガウスは、π の代わりに似た発音の φ という記号を使った。ガウスの φ は、オイラーの π と微妙に定義が違うので、混乱を防ぐため文字を変えたのかもしれない。

後に英国の数学者が、この数のことを totient と名付けた。この用語は quotient（商）をもじったもので、total（総数）の tot- に引っ掛けたものだろうから、言葉遊びに付き合うとすれば「商」（ショウ）をもじって「総」（ソウ）と呼ぶのが妥当だろう。意味的には「互いに素（ソ）なものの総数（ソウスウ）」の略。

普通は単に φ(A) と書かれ、φ は「オイラーのファイ関数」と呼ばれる。実際にファイ（φ）の文字を使ったのはガウスなので、正確に言えば「オイラーの関数のガウス版ファイ関数」といったところか…。

A = 1 の総は 1。なぜなら 1 以下の自然数は「1」自身の 1 個だけだが、この「1」という数は、A = 1 との最大公約数が 1 なので、A の総としてカウントされる。

【2】　「約数の総」の和の定理（ガウス、Disquīsītĭōnēs, art. 39）　自然数 A の約数が a, a′, a″, … のとき、
　　(a の総) + (a′ の総) + (a″ の総) + …
という和は A に等しい。「A の約数」とは、1 と A 自身も含む。

解説（定理の意味）　例えば A = 6 とすると、その約数は 1, 2, 3, 6 だが、
　　1 の総は 1
　　2 の総は 1
　　3 の総は 2
　　6 の総は 2
であり、この総たちの和は 1 + 1 + 2 + 2 = 6 となって、A に等しい。また、例えば A = 7 とすると、その約数は 1, 7 だが、
　　1 の総は 1
　　7 の総は 6
であり、この総たちの和は 1 + 6 = 7 となって、やはり A に等しい。

注: 「約数の総の和」は「約数の総和」ではない。例えば A = 7 の約数の和 1 + 7 は A に等しくない。

証明　分子を 1 以上の整数として、分母を A に固定した場合、値が 0 より大きく 1 以下の分数は、ちょうど A 個ある。例えば A = 6 の場合、約分せず機械的に書くと:
　　1/6, 2/6, 3/6, 4/6, 5/6, 6/6　　‥‥①
このうち、既約（きやく）分数――つまり、これ以上約分できない分数――は 1/6 と 5/6 の 2 個だが、この個数は「分子と分母が互いに素な分数の個数」であり、分母 A の総に他ならない。

①のように機械的に分数を並べたものについて、約分できるものは約分して全てを既約分数に変換した場合（ただし整数 1 も、あくまで分数 1/1 として表現する）、約分された分母には A の全ての約数が出現する。実際、A の約数が a, a′, a″, … なら、その一つ一つで A を割った商をそれぞれ b, b′, b″, … として:
　　A = ab = a′b′ = a″b″ = …
　　例えば 6 = 1 × 6 = 2 × 3 = 3 × 2 = …
このとき、
　　1/a (= b/(ab) = b/A)　　例えば 1/1　← 通分すると①の 6/(1×6) = 6/6 に等しい
　　1/a′ (= b′/(a′b′) = b′/A)　　例えば 1/2　← 通分すると①の 3/(2×3) = 3/6 に等しい
　　1/a″ (= b″/(a″b″) = b″/A)　　例えば 1/3　← 通分すると①の 2/(3×2) = 2/6 に等しい
　　…
は既約分数。b, b′, b″, … も A の（正の）約数なので 1 以上 A 以下であり、これらの既約分数の値は、①の形の分数（分母が A で、必ずしも約分されていない）のどれかに等しい。また、その2倍、3倍…なども、値が 1 以下なら①のどれかに等しいことは、言うまでもない（例えば 1/3 の2倍、つまり 2/3 は、4/6 に等しい）。ただし、2倍、3倍…などのうちには、「①のどれかに等しいけど、既約分数ではないもの」も含まれている（例えば 1/3 の3倍、つまり 3/3 は、6/6 に等しいが、既約分数ではない）。

引き続き A = 6 を例として、①を既約分数だけで書き直すと:
　　1/6, 1/3, 1/2, 2/3, 5/6, 1/1　　‥‥②
前記のように、このうち「分母が 6 の既約分数」の個数は 6 の総。同じ原理から、「分母が 3 の既約分数」の個数は 3 の総（分子と分母は互いに素でなければならないので。というのも、分子が分母と互いに素でないなら、もっと約分でき、既約分数にならない: 3/3 がその例）。同様に、「分母が 2 の既約分数」の個数は 2 の総、「分母が 1 の既約分数」の個数は 1 の総。結局、②に記されている既約分数の個数は、「6 の約数（1, 2, 3, 6）の一つ一つの総」の和に等しい。②の分数は①の分数を約分しただけなので、もちろん①の分数の個数と、②の分数の個数は、同じ。

このことは A = 6 に限らず、任意の A について成り立つ。つまり「A の約数一つ一つの総」の和は、②の形の分数の個数に等しく、それは①の形の分数の個数に等しく、結局 A に等しい。□

2022-02-11　げんしこん（その9・最終回）　アッと驚くガウスの証明

ガウス自身による原始根の存在証明。理解できたとたん、あっけにとられる。どうしてこんな発想ができるの…

【1】　mod p において（p は素数）、ある元 b の位数が f だったとする。つまり:
　　とある正の整数 f に対して　b^f ≡ 1　　‥‥①
　　f より小さい指数 n = 1, 2, …, f−1 に対しては　bⁿ ≢ 1

このとき、
　　f 次方程式 x^f ≡ 1　　‥‥②
は、ちょうど f 種類の解を持ち（補助定理2）、解たちの集合をこう書くことができる（その8【4】）:
　　S = {b¹, b², b³, …, b^f}
別の書き方をすると（内容的には全く同じ意味）:
　　S = {b^e | e = 1, 2, 3, …, f}　　‥‥③

ここで b¹ = b の位数は f だし、b^f ≡ 1 の位数はもちろん 1 だが、b² の位数、b³ の位数…、より一般的に b^e の位数は、いくつだろうか？　つまり、ある指数 e を選択した場合:
　　(b^e)^k ≡ 1 を満たす最小の正の整数 k は何か？

【2】　最小かどうかは分からないが、k = f は、上の式を満たす:
　　(b^e)^f = (b^f)^e ≡ 1^e = 1　　（なぜなら①）
さて、(b^e)^k = b^ek ≡ 1 が成り立つのは、指数 ek が、f の倍数である場合に限られるので（補助定理1）、「最小の」という限定を付けるためには、「e の倍数 ek のうち、f の倍数でもあるものの中で、最小のもの」を選ぶ必要がある。そのような ek ――つまり e の倍数でも f の倍数でもある最小の数―― とは、もちろん e と f の最小公倍数:
　　L = lcm(e, f) とすると
　　ek = L　　‥‥④
今、e と f の最大公約数を G = gcd(e, f) として、基本性質 ef = GL つまり L = ef/G を使うと（←これが成り立つ理由については下記【5】参照）、④はこうなる:
　　ek = ef/G
　　両辺を e で割って　k = f/G

結局、この k = f/G が b^e の位数。

《例》　mod 7 の場合、b = 2 の位数は f = 3。e = 3 とすると G = gcd(3, 3) = 3:
　　b^e = 2³ = 8 ≡ 1 の位数は k = f/G = 3/3 = 1

《例》　mod 7 の場合、b = 2 の位数は f = 3。e = 4 とすると G = gcd(4, 3) = 1:
　　b^e = 2⁴ = 16 ≡ 2 の位数は k = f/G = 3/1 = 3

ここまでは、まぁ普通の数学。

【3】　b¹ = b の位数は f だが、③の形の b^e の中に、他にも位数 f のものがあるだろうか？　【2】で見たように b^e の位数は f/G。もし G = 1 なら（そして、そのときに限って）、b^e の位数 f/G は = f になる。G というのは e, f の最大公約数なので、b^e の位数が f ということは、e, f の最大公約数が 1 ということ――すなわち e と f が互いに素ということ――と同じ意味。

では、同じ位数 f を持つ b^e は、合計何種類あるか？　その個数を考えてみよう…。

「互いに素」うんぬんの観察と③を見比べれば簡単に分かることだが、その個数とは、「f 以下の正の整数 e = 1, 2, 3, …, f の中に、f と互いに素なものはいくつあるか？」という総数、つまり f の総 φ(f) に等しい（「総」って何？）。ここでオイラーのファイ関数が絡んでくる。

一方、ある元 x の位数が f になるためには x^f ≡ 1 であること――つまり x が②の解であること――が必要だから（※注）、位数 f の元は③の形を持つことが必要（つまり、集合 S の要素のどれかと合同）。それ以外の種類の「位数 f の元」は、存在しない。従って、「位数 f の元は何種類あるの？」という問いについては、集合 S の要素だけを考えれば十分であり、上記の議論だけで正確な答えが得られる。

※注　この条件が必要な理由は単純: 位数というのは x^□ ≡ 1 の □ に当てはまる最小の正の整数なのだから、もし x^f ≡ 1 でなければ、f が □ に当てはまらず、つまり x の位数は f になり得ない。

f の代わりに文字 n を使い、任意の正の整数を n とすると:

位数 n の元の個数　位数 n の元が存在するとすれば、そのような元は、ちょうど φ(n) 種類、存在する。もし位数 n の元が存在しないなら、そのような元は（存在しないのだから）もちろん 0 種類。

《例》　mod 7 の場合: リンク先の表で確かめられることだが、位数 3 の元が存在する。合計何種類、存在するか。φ(3) = 2 だから、ちょうど2種類、存在する。一方、これもリンク先の表で確かめられることだが、位数 4 の元は存在しない。存在しないのだから、位数 4 の元は 0 種類。この場合、φ(4) = 2 は無関係。

「位数 n の元が全部で何種類あるか？」を ψ(n) で表すことにすると（ψ は「プサイ」、ファイ関数の φ とは別の文字）、上記のことから:
　　ψ(n) = φ(n) または 0　　← この関係を「ψ法則」と呼ぶことにする

《例》 mod 7 の場合、上の例から ψ(3) = 2, ψ(4) = 0。前者は「= φ(n)」の場合に当たり、後者は「または 0」の場合に当たる。…この場合、「または」は「どっちでもOK」という意味ではなく、「そのどっちか一方」という意味。

φ(n) は、n の総（n 以下の自然数のうち n と互いに素なものの総数）だが、どんな自然数 n を考えても、1 は n と互いに素なので、総としてカウントされるものが最低1個はある。つまり、φ(n) は 1 以上。todo: この部分は前回に移動。このことから、ψ(n) は、もし = φ(n) になるとすれば、必ず 1 以上。他方、「または 0」になるとすれば、もちろん ψ(n) = 0 であり、この 0 という数は φ(n) より小さい（当たり前だが）。

【4】　原始根の存在（ガウス、Disquīsītĭōnēs, art. 54）　p−1 の（相異なる全ての）約数を d, d′, d″, … とする。さて、p−1 種類の元 1, 2, 3, …, p−1 のそれぞれについて、その位数は p−1 の約数のどれかに等しい（補助定理1.1）――すなわち、d, d′, d″ のどれか一つ（だけ）に等しい。その内訳は、
　　位数 d の元が ψ(d) 種類
　　位数 d′ の元が ψ(d′) 種類
　　位数 d″ の元が ψ(d″) 種類
　　…
となり、どれが何種類あるのかまだ分からないけれど、とにかく p−1 種類の元 1, 2, 3, …, p−1 の一つ一つが位数に応じて分類されるのだから（そして、どれか一つの ψ によってカウントされている）、全体を考えれば:
　　ψ(d) + ψ(d′) + ψ(d″) + … = p−1　　‥‥⑤

前記の「ψ法則」　ψ(n) = φ(n) または 0　によれば、⑤は次を意味する:
　　[φ(d) または 0] + [φ(d′) または 0] + [φ(d″) または 0] + … = p−1　　‥‥⑥

ところが、「約数の総」の和の定理によれば:
　　φ(d) + φ(d′) + φ(d″) + … = p−1　　‥‥⑦

⑥の左辺と⑦の左辺を項ごとに比較しよう。⑥では
　　[φ(d) または 0]　とか　[φ(d′) または 0]　等々
と言っているものの、実際には、どれか1項でも「または 0」が選択されて 0 になってしまうと、⑥の左辺は⑦の左辺より小さくなってしまう（この観察が鍵となるので、ゆっくり考えてみよう。意味が分かると当たり前のことだが…）。それぞれの右辺から分かるように、⑥の左辺の和も、⑦の左辺の和も、（どちらも p−1 であり）等しいのだから、⑥の左辺が⑦の左辺より小さくなってしまうことは、あり得ない。従って、⑥のどの項でも、実際には「または 0」が選択される可能性はない。⑤に関して言えば:
　　位数 d の元は ψ(d) = φ(d) 種類
　　位数 d′ の元は ψ(d′) = φ(d′) 種類
　　位数 d″ の元は ψ(d″) = φ(d″) 種類
　　…
となる（「ψ法則」の「または 0」の選択肢が消え、ψ と φ が同じ意味に）。

結局、p−1 のどの約数 d, d′, d″, … を考えても、φ(d), φ(d′), φ(d″), … は 1 以上なのだから、位数 d の元、位数 d′ の元、位数 d″ の元、…がそれぞれ最低でも 1 個、存在する――もっと正確に言うと、それぞれ φ(d) 種類、φ(d′) 種類、φ(d″) 種類、…存在する。

特に、p−1 自身も p−1 の約数だから、位数 p−1 の元が φ(p−1) 種類、存在する。

要するに、mod p において、位数 p−1 の元（すなわち原始根）は必ず 1 個以上、存在する。より正確に言えば、ちょうど φ(p−1) 種類の原始根が、存在する。□

すげえ。すげえよ、この証明。ガウスの証明！

原始根に話を限らず、一般に「各位数の元が何個あるのか」。それを統一的に見渡す視点の高さ。そのために、一見無関係にも思えるファイ関数を持ち出す洞察力。そしてシンプルでエレガントな「約数の φ」の和の公式。具体的には何も数えず、何も構成せず、いきなり結論を導く…。ものすごい変化球に見えて、実は核心をストレートに突いている。

位数の大きさは、p−1 の約数 d, d′, d″, … のどれかに限られるが（仮に、その任意の一つを D とする）、位数 D の元が何種類あるか数えること、つまり ψ(D) の値を求めることは、ファイ関数の値 φ(D) を求めること。p−1 の約数に話を限るとき、ψ の正体は φ。原始根が（何種類）存在するか？という問いは、ファイ関数の問題となる。

のみならず、抽象代数学の言葉を使えば、p−1 とは mod p の世界における可逆元の数。それは p と互いに素な元の数であり、すなわち φ(p)。上記 φ(p−1) において、丸かっこ内にある p−1 の正体が φ(p) なのだから、原始根の種類の数 φ(p−1) とは、φ(φ(p))。原始根とファイ関数は、このように深く結び付いている。

技術的な細かい議論をして「これこれだと矛盾が生じる」などとせこい証明をしなくても、正しい方向から眺めるとき、原始根の存在は、より一般的な事実の一例として自然に浮かび上がる。群論的な現代のアプローチも確かに強力だが、ガウスの巧妙さ・鮮やかさには、心に響くものがある。

画像＝ガウスの証明原文。art. 40 は art. 39 の誤植か。

「げんしこん」シリーズ（全9話+番外編3話）は、以上でございます。この景色が、何かの参考になりましたら、幸いです。ご清聴ありがとうございました！

【5】　質疑応答。

Q. 「e と f の最大公約数を G として、e と f の最小公倍数を L とすると、ef = GL」という主張の根拠は？

A. どんな自然数が与えられても、それを素因数分解して、素数べきの積で表すことができるのは、ご承知の通りです。今、何らかの e と f が与えられたとして、それを素数べきで表したとします。例えば、まあ適当に…
　　e = 2⁶⋅3⁵⋅5²⋅7⁰
　　（便宜上これを e = ABCD とする）
　　f = 2³⋅3⁸⋅5¹⋅7³
　　（便宜上これを f = abcd とする）
…としますと、次のように、対応する素数べき（同じ素数のべき）から小さい方を抜き出して掛け合わせれば G になり、大きい方を抜き出して掛け合わせれば L になるわけです（e と f に必ず「対応する素数べき」があるようにしたいので、一方にしか含まれていない素因数については、他方には「その素数の 0 乗」が含まれていると解釈）。
　　G = 2³⋅3⁵⋅5¹⋅7⁰　← eとfの公約数の最大。これ以上どこも1乗も増やせない
　　（G = aBcD です）
　　L = 2⁶⋅3⁸⋅5²⋅7³　← eとfの公倍数の最小。これ以上どこも1乗も削れない
　　（L = AbCd です）
このとき、GL という積は、e に含まれる素数べき・f に含まれる素数べきを全部ちょうど1回ずつ掛け合わせたものです。つまり、
　　GL = (aBcD)(AbCd)
と
　　ef = (ABCD)(abcd)
は、等しい。なぜなら、A, a の一方が G に入って他方が L に入り、B, b の一方が G に入って他方が L に入り、C, c の一方が G に入って L に入り…等々となるため、GL という積には、A, a, B, b, C, c, … が過不足なく、全部ちょうど1個ずつ含まれるからです。

もし仮に C = c のように対応する素数べきに大小の差がない場合（同じ素数の「同じ数」乗の場合）、どちらが G に入ってどちらが L に入るのか曖昧ですが、その場合、どっちがどっちに入っても数値に差はないので、どっちでもいいわけです。C = c = X と置くと、G にも L にも、因子として X が1個ずつ入ります。…今適当に書いた具体例は出任せなので、誤字や計算ミスがあったら、修正して読んでください。

Q. 肝心の「フェルマーの小定理」が証明されていないのでは…？

A. ご指摘の通り、このシリーズ単体だとその点が重大なギャップになってしまうのですが、小定理の説明・証明については、同じような調子の記事「フェルマーの小定理」が既にあるので、今回は省略しました。気が向いたら、そのうちそっちも更新するかも…です。（追記・ほぼ小学生の算数だけで証明してみた→フェルマーの小定理で遊んじゃえっ！）

2021-12-31　xⁿ − yⁿ は x − y で割り切れる　n次方程式の解の個数

10² − 3² = 100 − 9 = 91 は 10 − 3 = 7 で割り切れる。91 = 7 × 13。

10³ − 3³ = 1000 − 27 = 973 も 10 − 3 = 7 で割り切れる。973 = 7 × 139。

10⁴ − 3⁴ は、どうだろうか？

…このような一見たわいもないことから、冒険が始まる！

【1】　n = 2 の場合: x² − y² = (x + y)(x − y) が x − y で割り切れ、商が x + y になることは、言うまでもない。だって、この値は (x + y) と (x − y) の積だもん。

x² − y² = (x + y)(x − y) という計算自体が分からないという方は、展開の仕方を見てネ♪

《例》　10² − 3² = 100 − 9 = 91 は (10 + 3)(10 − 3) = 13 × 7 = 91 に等しい。そして 10 − 3 = 7 で割り切れる。商は 10 + 3 = 13。

n = 3 の場合。結論から言うと:

• x³ − y³ = (x − y)(x² + xy + y²)　　‥‥‥「あ」

分配法則を使って右辺を好きな順序で展開すれば、「あ」が成り立つことを確かめられる。実際の計算例は後述（【3】参照）。

「あ」右辺後半の x² + xy + y² つまり
　　x²y⁰ + x¹y¹ + x⁰y¹
は、x^ay^b の形の項の和: x の指数 a は順に 2→1→0、y の指数 b は順に 0→1→2、そして指数の和 a + b はどの項でも 3 で、等しい（もちろん、普通は y⁰ = 1 などをわざわざ書く必要ないし、x¹ も単に x と書けばいい）。

「何で 0 乗が 1 なの？」　→　「0 乗」の意味

n = 4 の場合:

• x⁴ − y⁴ = (x − y)(x³ + x²y + xy² + y³)　　‥‥‥「い」

詳細については後述するが、「い」右辺後半の4項は x^ay^b の形の項の和。a は順に 3→2→1→0、b は順に 0→1→2→3、指数の和 a + b はどの項でも 4。

【2】　具体的な数値で確かめてみましょ。x = 10, y = 3 とすると、「あ」左辺は:
　　10³ − 3³ = 1000 − 27 = 973
この数は 10 − 3 = 7 で割り切れる。「あ」右辺は:
　　(10 − 3)(100 + 30 + 9) = 7 × 139
この数は上記 973 に等しい。

「い」左辺は:
　　10⁴ − 3⁴ = 10000 − 81 = 9919
この数は 10 − 3 = 7 で割り切れる。「い」右辺は:
　　(10 − 3)(1000 + 300 + 90 + 27) = 7 × 1417 (= 7 × 13 × 109)
この数は上記 9919 に等しい！

【3】　「あ」「い」からだいたい予想がつくかもしれないが、一般に、2以上の整数 n に対して、こうなる:

• xⁿ − yⁿ = (x − y)(xⁿ⁻¹ + xⁿ⁻²y¹ + xⁿ⁻³y² + … + x²yⁿ⁻³ + x¹yⁿ⁻² + yⁿ⁻¹)　　‥‥‥「う」

この式は複雑そうで、ちょっと怖い感じがするかもしれない…。まぁ「こんなもんかね？」くらいの感じで、気楽に眺めておこう☆

要するに「う」右辺は、(x − y) と「x の (n−1) 次式」の積。この (n−1) 次式は x^ay^b の形の項の和で、a は n−1 から 0 まで一つずつ小さくなり、b は 0 から n−1 まで一つずつ大きくなる。どの項でも、指数の和 a + b は一定の値 n−1。

《例》　5⁵ − 2⁵ = 3125 − 32 = 3093 は、確かに 5 − 2 = 3 で割り切れる。3093 ÷ 3 = 1031 は簡単に暗算できるけど、「う」の検証のためその右辺を使うと:
　　5⁴ + 5³ × 2¹ + 5² × 2² + 5¹ × 2³ + 2⁴
　　= 625 + 125 × 2 + 25 × 4 + 5 × 8 + 16
　　= 625 + 250 + 100 + 40 + 16 = 1031　　ご名算！

「う」が成り立つ理由は…。

こーゆー計算が得意な人は、正式な証明をBAN²どーぞ。
あんま得意じゃない人も、1項ずつ、じっくり見ればDAIJO-BU↓

最初に「あ」の x³ − y³ = (x − y)(x² + xy + y²)　について考えてみよう。

右辺後半の　x² + xy + y²　を　① + ② + ③　とする。つまり
　　x² を ①、xy を ②、y² を ③
として、それぞれ第1項、第2項、第3項と呼ぶことにしよう。
　　(x − y)(① + ② + ③) = x① − y① + x② − y② + x③ − y③
の順で計算すると:

• (x¹ − y¹) × (x² + x¹y¹ + y²)
• = x³ − x²y¹ + x²y¹ − x¹y² + x¹y² − y³

★　このとき、第2項 x¹y¹ の x 倍　x²y¹　は、
直前の　− x²y¹　つまり「第1項 x² の −y 倍」と、打ち消し合う。

「打ち消し合う」とは、「絶対値が同じで符号が反対なので、和が 0 になって消えてしまう」という意味。

★　同様に、第3項 y² の x 倍　x¹y²　は、
直前の　− x¹y²　つまり「第2項 x¹y¹ の −y 倍」と、打ち消し合う。

この結果、「第1項の x 倍」と「第3項の −y 倍」だけが残り、
　　(x − y)(x² + xy + y²) = x³ − y³
となる。

次に「い」の x⁴ − y⁴ = (x − y)(x³ + x²y + xy² + y³)　について。

さっきと同様に右辺を展開すると:

• (x¹ − y¹) × (x³ + x²y¹ + x¹y² + y³)
• = x⁴ − x³y¹ + x³y¹ − x²y² + x²y² − x¹y³ + x¹y³ − y⁴

★　第2項 x²y¹ の x 倍　x³y¹　は、
直前の　− x³y¹　つまり「第1項 x³ の −y 倍」と、打ち消し合う。

★　第3項 x¹y² の x 倍　x²y²　は、
直前の　− x²y²　つまり「第2項 x²y¹ の −y 倍」と、打ち消し合う。

★　第4項 y³ の x 倍　x¹y³　は、
直前の　− x¹y³　つまり「第3項 x¹y² の −y 倍」と、打ち消し合う。

この結果、「第1項の x 倍」と「第4項の −y 倍」だけが残って、
　　(x − y)(x³ + x²y + xy² + y³) = x⁴ − y⁴
となる。

これらの計算から分かるように、「う」の右辺…
　　(x − y)(xⁿ⁻¹ + xⁿ⁻²y¹ + xⁿ⁻³y² + … + x²yⁿ⁻³ + x¹yⁿ⁻² + yⁿ⁻¹)
…において、後半の丸かっこ内が展開されるとき、ほとんどの項の x 倍は、直前の項の −y 倍と打ち消し合う。

結果として、ほとんどの積は打ち消し合ってなくなり、第1項の x 倍と、最終項の −y 倍の、2個だけが残る（打ち消し合う相手がいないので）。

具体的に、残るのは xⁿ⁻¹ の x 倍と、yⁿ⁻¹ の −y 倍。つまり xⁿ と − yⁿ。これらは「ピュア」な項（x と y の両方が交ざっていない）: つまり x^□y^□ の形（因子 x と因子 y をそれぞれ1個以上含む）ではない。強いて x^ay^b の形で書けば、a = 0 または b = 0 の項だけが、打ち消し合わずに残る。

ここで重要なのは、ごちゃごちゃした細かい計算ではなく、「う」の右辺が
　　(x − y) と [ x の (n−1) 次式 ] の積
になる…という事実。言い換えれば、「う」の両辺は x − y で割り切れる。

文字が x, y だと2個の未知数のようだが、以下では x が変数、y が定数の場合を考える。イメージしやすくするため、y の代わりに文字 α（アルファ）を使って、上記の事実を整理し直すと（便宜上、指数 n も m に改名）:

1. m が 2 以上の整数のとき、
2. x の m次式 x^m − α^m は x − α で割り切れて、
3. 商は (m − 1) 次式 になる！

【4】　さて、1次式・2次式・3次式…や、1次関数・2次関数・3次関数…、1次方程式・2次方程式・3次方程式…については、多分誰でも聞いたことがあるよね。例えば、2次式は、A, B, C を定数として
　　Ax² + Bx + C
という形を持つ。ここで x は変数。x に何か具体的な数を入れると、それを入力として出力――つまり式の値（それを y としよう）――が定まる。そのことを
　　y = Ax² + Bx + C
　　あるいは同じ意味で　y = f(x)
と書く。ここで f(x) は f と (x) の掛け算ではなく、x を変数とする式:
　　Ax² + Bx + C
を表す。f は上記の式に付けた名前。そうしたければ g(x) や h(x) など、別の名前を付けても構わない。

記号 f(x) は、式を表すこともあるし、その式に x を入れたときの値を表すこともあるが、本来的には「変数 x にその式の値 f(x) を対応させる関数」を表す。○次式と○次関数というのは同義語のようなものだが、小難しい区別をするなら、「式」は要するに「数式」、「関数」は「変数から式の値への写像」。

f(x) は式 f に x を入れたときの出力なので、x の値が変われば、いろいろな値を取り得る。たまたま出力が 0 になることもあるかもしれない。つまり…
　　f(x) = 0
　　言い換えれば　Ax² + Bx + C = 0
…を満たす x が存在するかもしれない。そのような特別な x の値のことを f(x) の――つまり Ax² + Bx + C の――根（こん）という。ほとんど同じ意味で、方程式 f(x) = 0 の――つまり Ax² + Bx + C = 0 の――解ともいう。この場合、2次式 f を使って定義される関数なので y = f(x) は2次関数と呼ばれ、f(x) = 0 は2次方程式と呼ばれる。

2次以外も、全く同様。例えば A, B, C, D, E を定数として、
　　g(x) = Ax⁴ + Bx³ + Cx² + Dx¹ + E
は4次関数、g(x) = 0 は4次方程式。

1次方程式・2次方程式・3次方程式…などを一般化して、n次方程式を考えてみたい。

メインディッシュは…

定理　n次方程式 f(x) = 0 の解は n 個以下。

シンプルだけど、これを証明しとくと、いろんな遊びや探検ができる！

数の世界も「実数」や「複素数」に限定せず、少し緩い観点で考えたい。一見、学校の数学みたいで退屈な「方程式」の話だが、実は原始根について考える下準備。目標としては、「原始根の存在証明」という丘にいろんなルートから登って、景色を楽しみたい。

【5】　1次方程式 f(x) = 0 の場合、A, B を定数として f(x) = Ax + B = 0 と書ける。
　　Ax + B = 0 の両辺に −B を足すと:
　　Ax = −B
もし考えている世界に A の逆数 A⁻¹ = 1/A があるなら、上の式の両辺にそれを掛けると:
　　x = −B/A
つまり、もし解があるとすれば、解は上記の1個に定まる。もし解がないとすれば、もちろん解は0個。――1個か0個なのだから、「1次方程式の解は1個以下」ということが証明された！

同様に、2次方程式の場合、
　　f(x) = Ax² + Bx + C = 0　　‥‥‥「お」
と書ける。もしこの方程式に解がないなら、定理は正しい（「解が0個」は「2次方程式の解は2個以下」という主張に合致）。そこで、この f(x) = 0 に最低1個は解があると仮定して、その場合でも最大2個しか解がないことを示そう。f(x) = 0 の一つの解を x = α とすると:
　　f(α) = Aα² + Bα + C = 0　　‥‥‥「か」
ちょっとトリッキーだが、ここで f(x) からあえて 0 を引くと、こうなる:
　　f(x) = f(x) − 0 = f(x) − f(α)　←　なぜなら「か」から 0 = f(α)
　　= (Ax² + Bx + C) − (Aα² + Bα + C)　←　「お」「か」から
　　= (Ax² − Aα²) + (Bx − Bα) + (C − C)　←　A, B, Cを含む項をそれぞれまとめた
　　= A(x² − α²) + B(x − α)
　　= A(x + α)(x − α) + B(x − α)　←　前半も後半も因子 (x − α) を含む
　　= (x − α)[A(x + α) − B]　←　(x − α) をくくり出した
　　= (x − α)[Ax + (Aα − B)]

要約すると:
　　f(x) = (x − α)[Ax + (Aα − B)] = 0　　‥‥‥「き」
もし考えている世界が整域（せいいき）なら――つまり、その世界の任意の2要素 U, V について、UV = 0 なら必ず U = 0 または V = 0 が成り立つ、とすれば――、「き」によって (x − α) = 0 または [Ax + (Aα − B)] = 0。

「UV = 0 なら U = 0 または V = 0」という性質を、U = (x − α), V = [Ax + (Aα − B)] に当てはめれば、そうなる。

「または」の前の (x − α) = 0 は x = α ということで、これが f(x) の解であることは、もともとの仮定。問題は「または」の後ろの
　　Ax + (Aα − B) = 0　　‥‥‥「く」
なんだけど、これって x を未知数とする1次方程式だよね？　だって (Aα − B) は、1個目の解 α によって決まる定数だもん。「く」に解があるかどうかは不明だし、解があるとしても、ひょっとすると、1個目の解と同じ x = α になるかもしれない。運よく x = α 以外の新しい解が見つかるとしても、先ほど証明したように「1次方程式の解の個数は1個以下」。だから新しい解は、あったとしても、あと1個だけ。従って、2次方程式「か」には、最高でも合計2個しか解がない。「2次方程式の解の個数は2個以下」ということが証明された！

【6】　一般の n 次方程式 f(x) = 0 についても同様（n は2以上の整数とする）。解が1個でもあれば、その解を x = α として、
　　f(x) = (x − α) [ (n−1) 次式 ] = 0　　‥‥‥「け」
と変形できる。この変形については、次の【7】で確かめる。難しいのは式変形より、証明のロジック…

x = α が「け」を満たすことは、直接確認できる: f(x) の x に α を代入すると、(x − α) の部分が 0 になり、確かに「け」の値は 0。では「け」に、x = α 以外の解があるとしたら…？

その別の解を x = β とすると、その値は α と等しくないのだから、「け」の f(x) に x = β を代入した場合、(x − α) の部分、つまり (β − α) は = 0 にならない。すると、整域という前提から、f(β) = 0 が成り立つためには、どうしても [ (n−1) 次式 ] の部分が = 0 になるしかない。

で、ちょっと突拍子もない話だけど、ここでもし、
　　[ (n−1) 次式 ] = 0 の解の個数は n−1 個以下である　　‥‥‥「？」
と主張できるとしたら、どういう結論を導けるだろうか？

もし「？」が正しいのなら、「1個目の解 x = α」以外の解 x = β の値の可能性は、最大でも n−1 種類しかない。なぜなら β は
　　[ (n−1) 次式 ] = 0
の解で、「？」によれば、そのような解の個数は n−1 個以下。…ということは、要するに、一般の n に対して定理が証明されたことになる。だって、1個目の解があるとして残りの解が (n−1) 個以下なら、解の合計個数は 1 + (n−1) = n 個以下！

でも、この証明（？）、何か変じゃね？　だってさぁ、(n−1) 次方程式の解の個数は (n−1) 個以下、っていう「？」の主張は、証明しようとしてる定理の内容そのもの。定理を証明するのに、その定理自体を根拠とするっていうのは、論理的に駄目じゃん（循環論法）！

《循環論法の例》
定理X　素数は無限個ある。
定理Xの「証明」　定理Xにより、素数は無限個ある。ゆえに、素数は無限個ある。証明終わり。
こんなの証明といえない。「おれがそう言うんだから、それが証明だよ」というオレオレ証明。

もっとも「？」の主張は、完全な循環論法ではなく、n次方程式についての主張を、少しだけ簡単な (n−1) 次方程式についての命題に帰着させてる: 5次方程式についての主張は4次方程式についての主張に帰着され、それは3次方程式についての主張に帰着され…というように、だんだん次数が下がるので、最終的には1次方程式についての主張に帰着される。そして「1次方程式の解は1個以下」ということは、既に【5】で直接証明してある！

「？」を必要なだけ繰り返し使うことで、2次以上の方程式についての主張は、1次方程式についての主張に帰着される。もちろん帰着されるだけでは、証明にならない――「？」は、それ単体では有効な証明とはいえない。けれど、この場合、行き着く先の1次方程式についての主張は、別途証明済み。つまり、「証明したい内容」を「証明済みの事実」に帰着されられるわけで、組み合わせ技として、有効な証明を構成できる。単に同じ場所をぐるぐる歩くだけの「循環論法・堂々巡り」ではなく、「らせん階段」を一段ずつ下りてくみたいな感じ…。その「らせん階段」には、きちんとした終点がある。

例えば n = 3 の3次方程式の場合、[ (n−1) 次式 ] = 0 というのは、要するに2次方程式。「2次方程式が最高でも2個しか解を持たないこと」は、既に証明した。だから…

1. 3次方程式の場合、もし1個目の解 x = α があるとしても、
2. 残りの解は、[ 2次式 ] = 0 の解、つまり2個以下。
3. 合計すると、3次方程式の解は3個以下！

同様に、4次方程式の場合、1個目の解があるとしても、残りの解は3次方程式の問題に帰着され、たった今証明したように、3次方程式の解は3個以下。だから4次方程式の解は、合計4個以下。同様のことを必要なだけ繰り返せば、5次・6次・7次…の方程式についても（従って、一般のn次方程式についても）、定理が証明可能。いつでも証明可能と分かってる、ってことは、実質的に、証明されてるのと同じこと。

【7】　ロジックは以上の通り。感覚的に分かりにくい面もあるかもしれないけど、この論法は帰納法（きのうほう）と呼ばれ、数学ではよく使われる。

証明の外形が一応分かったので、あとは中身を完成させよう。要（かなめ）となる事実は「け」だった。つまり、2以上の任意の整数 n について:

1. n次方程式 f(x) = 0 が1個以上の解を持つ場合、
2. 1個目の解を x = α とすると、
3. f(x) は x − α で割り切れ、商は (n−1) 次式になる。

これを示す方法は、【5】の「お」「か」と同様。与えられた n 次関数を
　　f(x) = Axⁿ + Bxⁿ⁻¹ + Cxⁿ⁻² + … + Px² + Qx¹ + R　　‥‥‥「こ」
としよう。この右辺は n+1 項あって、定数 A, B, C, … が何文字（何種類）あるかは n の値次第だけど、便宜上 …, P, Q, R で終わるとする: 例えば、7次関数なら、7次から3次の項の係数が A, B, C, D, E、2次の項の係数が P、1次の項の係数が Q、定数項が R。100次関数とかだと文字が足りなくなるけど、係数名は便宜上のもの。A, B, C, … で足りなければ A₁, A₂, A₃, … とでもすればいい。

さて x = α は f(x) = 0 を成立させる解だから、f(α) = 0。「こ」から、こうなる:
　　f(α) = Aαⁿ + Bαⁿ⁻¹ + Cαⁿ⁻² + … + Pα² + Qα¹ + R = 0　　‥‥‥「さ」

ここで再び「0 を引き算」というトリックを…。「こ」「さ」から:
　　f(x) = f(x) − 0 = f(x) − f(α)
　　= (Axⁿ + Bxⁿ⁻¹ + Cxⁿ⁻² + … + Px² + Qx¹ + R) − (Aαⁿ + Bαⁿ⁻¹ + Cαⁿ⁻² + … + Pα² + Qα¹ + R)
　　= A(xⁿ − αⁿ) + B(xⁿ⁻¹ − αⁿ⁻¹) + C(xⁿ⁻² − αⁿ⁻²) + … + P(x² − α²) + Q(x¹ − α¹)　　‥‥‥「し」
2個の定数項 R は、打ち消し合ってなくなる！

x^m − α^m の形の m 次式は、必ず x − α で割り切れて
　　x^m − α^m = (x − α)[x の m−1 次式]　　‥‥‥「す」
になるのだった（【3】参照）。従って「し」の第1項は、
　　A(xⁿ − αⁿ) = A(x − α)[x の n−1 次式]　♥
となる。「し」の第2項は（「す」で m = n−1 とすれば）、
　　B(xⁿ⁻¹ − αⁿ⁻¹) = B(x − α)[x の n−2 次式]　♥
となる。「し」の第3項は（m = n−2 とすれば）、
　　C(xⁿ⁻² − αⁿ⁻²) = C(x − α)[x の n−3 次式]　♥
となる。以下同様…。「し」の（最後から2番目の）係数 P の項は、直接計算すると:
　　P(x² − α²) = P(x − α)(x + α)　♥
係数 Q の最後の項は、普通にこう書ける:
　　Q(x¹ − α¹) = Q(x − α)　♥

結局「し」右辺は♥の形の項の和で、こうなる（見やすいように、掛け算の順序を微妙に変更）:
　　(x − α)A[x の n−1 次式] + (x − α)B[x の n−2 次式] + (x − α)C[x の n−3 次式] + …
　　 + (x − α)P(x + α) + (x − α)Q　　‥‥‥「せ」

ここで A, B, C, … は定数。○次式を定数倍しても、依然として○次式（例えば、2次式 x² + 5x − 1 の3倍 3x² + 15x − 3 は、依然として2次式）。例外は、掛け算する定数が 0 の場合で、0倍すれば、結果はもちろん 0。そうすると、上記の
　　A[x の n−1 次式]
という積は、[x の n−1 次式 または 0] となる。実際には、A = 0 なら、もともとの「こ」で n 次の項が消えてしまい、常識的には f(x) を n 次関数とは呼べなくなるが、一応「それもあり」としておく。あと、「x の n−1 次式 または 0」みたいな表現は長ったらしいので、単に「n−1 次式」のように簡略表記する（「または 0」などは暗黙の了解）。

この「n−1 次式」の意味は、「n−1」次の式（x の指数のうち最大のものが、n−1）。n引く「1次式」という意味ではない。

「せ」の各項に上記の簡略表記を適用し、共通因子 (x − α) をくくり出すと:
　　(x − α)[n−1 次式] + (x − α)[n−2 次式] + (x − α)[n−3 次式] + … + (x − α)P(x + α) + (x − α)Q
　　= (x − α){[n−1 次式] + [n−2 次式] + [n−3 次式] + … P(x + α) + Q}　　‥‥‥「そ」

「そ」の { } の中身は、n−1 次式以下。

なぜなら n−1 次式に、n−1 次式以下を足しても、依然として n−1 次式より高い次数にはならない（例えば、3次式 x³ + x² + 2x + 3 に2次式などを足しても、結果が4次式以上になることはあり得ない――どこにも x⁴ の発生源がないので）。「そ」末尾の P(x + α) + Q = Px + (Pα + Q) は x の1次式なので（そして n は2以上という仮定から、n−1 次式とは「1次式以上」なので）、P(x + α) + Q のせいで次数が上がることもない。

具体的に { } の中身がどういう式なのかはともかく、x の値を決めれば { } 内の値が決まるのだから、{ } の中身については、x を変数とする関数 g(x) と見なせる。上述のように、g(x) は n−1 次式。「そ」を簡潔にこう書ける:
　　(x − α)g(x)　　‥‥‥「そ」と同じ意味
「そ」は「せ」を整理したもの。その「せ」は「し」の右辺に等しいのだから、結局 f(x) に等しい:
　　f(x) = (x − α)g(x)　　‥‥‥「た」

「た」右辺は、(x − α) と g(x) の積なので、(x − α) で割り切れる。すなわち、f(x) は x − α で割り切れ、商 g(x) は n−1 次式。これが確かめるべきことだった！

これで証明完了♪　この定理が、冒険のためのベースキャンプとなる。

一般論として、1次方程式の解が1個、2次方程式の解が（複素数の範囲では）2個であることは、よく知られている（重解の場合は例外）。それらと比べると、3次方程式の解については、話題になることが少ない。今回証明した定理によれば、3次方程式の解は最大でも3個。具体的には、重解がある場合を別にすると、複素数の範囲では、実数解が3個あるか、または、実数解が1個・実数以外の複素数解が2個ある（「覚えやすさを重視した3次方程式の解法」）。

今回の証明では、分配法則を使いまくった。最低でも環（かん）の上で考える必要がある。それだけでなく、考えている世界が整域であることも、キーポイントだった。実際上、「解が常に0個」では考えても仕方ないので、逆数の存在（＝割り算ができること）も重要そう（【5】参照）。だから体（たい）の上で多項式を考えるのが自然だけど、それ以上の条件は必要なく、実数や複素数の世界に限る必要もない。この定理は、mod p の世界（素数位数の有限体）でも成立し、原始根の存在証明で役に立つ。mod p が整域であることについては、「時計ワールド」の付録を参照。

2022-01-01　10ⁿ − 3ⁿ が109で割り切れるとき　ちょっとお遊び

1以上の整数 n について、10ⁿ − 3ⁿ は、いつでも 7 で割り切れる（「xⁿ − yⁿ は x − y で割り切れる」参照）。

それだけでなく、「東京素数」 139 や「渋谷素数」 109 で割り切れることもある。

• 10¹ − 3¹ = 7
• 10² − 3² = 91 = 7 × 13
• 10³ − 3³ = 973 = 7 × 139
• 10⁴ − 3⁴ = 9919 = 7 × 13 × 109
• 10⁵ − 3⁵ = 99757 = 7 × 14251
• 10⁶ − 3⁶ = 999271 = 7 × 13 × 79 × 139
• 10⁷ − 3⁷ = 9997813 = 7² × 211 × 967
• 10⁸ − 3⁸ = 99993439 = 7 × 13 × 17 × 109 × 593

どうやら n が3の倍数だと 139 が現れ、n が4の倍数だと 109 が現れるようだ。n が偶数（2の倍数）のとき、13 で割り切れることも予想される。

この予想は、簡単に証明可能。基本となる性質「xⁿ − yⁿ は x − y で割り切れる」を再利用して、x = (10²), y = (3²) とすると:
　　(10²)ⁿ − (3²)ⁿ　つまり　10²ⁿ − 3²ⁿ
…は、(10²) − (3²) = 91 = 7 × 13 で割り切れる。

ある数 A が 91 で割り切れる、ってことは、つまり A は 91 の倍数。で、91 は 7 と 13 の積なんだから、要するに A って 7 と 13 の公倍数じゃん。公倍数ってことは「7 の倍数でもあり、13 の倍数でもある」。13 の倍数でもあるんだから、13 で割り切れるのは当然だよね。

同様に x = 10³, y = 3³ とすれば、周期3で因子 139 が現れる理由も分かる。つまり 10³ⁿ − 3³ⁿ は 10³ − 3³ = 973 で割り切れるんだから、973 の倍数。10^□ − 3^□ の形の数は、どれも 7 の倍数なんだから、973 の倍数というのも「7と何かの公倍数」のはず。何かって何？　上と同様に考えれば 973÷7 = 139 がその何か。

973 という数がどこから来たのかも含めて式で書くと:　(10³ − 3³) / 7 = 139

x = 10⁴, y = 3⁴ とすれば、周期4で因子 109 が現れる理由も、だいたい同じ。10⁴ − 3⁴ は 7 で割り切れ、そして（指数が偶数なので）13 でも割り切れる。だから、上記同様に考えれば、
　　(10⁴ − 3⁴) / (7 × 13) = 109
で割り切れる。要するに 10⁴ⁿ − 3⁴ⁿ は 9919 の倍数だから（そして 9919 = 7 × 13 × 109 だから）、それは「7 と 13 と 109 の公倍数」。

---