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

チラ裏 > 数論 > メモ5

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

***

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

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

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

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

b = 3 は、6乗して初めて「余り1♪」になる(1乗~5乗では「余り1」にならない)。一方、b = 2 は、6乗して「余り1♪」になるだけでなく、中間の b3 でも「余り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 未満の任意の整数とするとき、必ず
  bp−1 ≡ 1 (mod p)
が成り立つ。これは「フェルマーの小定理」と呼ばれる(以下「小定理」)。

《例1》 p = 7, b =2 とする。27−1 = 26 = 64 を7で割ると 1 余る。つまり:
  27−1 ≡ 1 (mod 7)

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

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

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

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

⁂

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

b1, b2, b3, … を素数 p で割った余りの表(前回)はランダムっぽいが、単純なパターンになってる部分もある。

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

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

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

【例】 21 = 2 ≡ 2, 22 = 4 ≡ 4, 23 = 8 ≡ 1  [7 で割った余りを考えてる]
24 = 16 ≡ 2, 25 = 32 ≡ 4, 26 = 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 において、31 = 3 ≡ 3, 32 = 9 ≡ 2, 33 = 27 ≡ 6 ≡ −1 なので、【1】の計算結果を再利用すると 34 = 33 × 31 ≡ (−1) × 3 = −3, 35 = 33 × 32 ≡ (−1) × 2 = −2, 36 = 33 × 33 ≡ (−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) なので、51, 52, 53, … は (−2)1, (−2)2, (−2)3, … と合同。ということは、21, 22, 23, … を再利用できる。つまり
  51 ≡ (−2)1 = (−1 × 2)1 = (−1)1 × 21 ≡ −2 (≡ 5)
  52 ≡ (−2)2 = (−1 × 2)3 = (−1)2 × 22 ≡ 4
  53 ≡ (−2)3 = (−1 × 2)4 = (−1)3 × 23 ≡ −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 とすると、定理の内容は「36 を 7 で割ると 1 余る」。実際、36 = 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 とも)。簡略に Z7 と表記されることもあるが、この簡略表記については、なぜか一部の数学者から毛嫌いされている。いわく、Zp は p進体の整数を表す記号でもあるから、紛らわしいと。一理あるが、それを言うなら、円周率を表す記号でもある π で二次体の素数を表したり、あるいは素数をカウントする関数を表したりするのは、もっと紛らわしい。一方、小定理の話の途中でp進体が出てくるわけないのだから、誤解が生じる余地はなく、Zp 表記には何の問題もないと思われる…。まぁ、記号なんて、意味が分かれば何でもいいわけで、好みの問題だろう。

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

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

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

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

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

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

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

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

何となく、d が 6 の約数なら pd ≡ 1 (mod 7) は上限ぴったりの 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) 冪(べき)という漢字

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

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

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

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

115 = 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 のように b51 (mod 11) の場合、
  3, 9, 5, 4, 1☆; 3, 9, 5, 4, 1♪
のように、周期5で同じことの繰り返し。なぜなら…
  36 = (35) × 31 ≡ (1) × 31 ≡ 3
  37 = (35) × 32 ≡ (1) × 32 ≡ 9
  38 = (35) × 33 ≡ (1) × 33 ≡ 5
  39 = (35) × 34 ≡ (1) × 34 ≡ 4
  310 = (35) × 35 ≡ (1) × 35 ≡ 1  ←ここは「小定理」の例
…となるから。一方、b = 2 のように b5 ≡ 10 ≡ −1 (mod 11) の場合、
  2, 4, 8, 5, −1★; −2, −4, −8, −5, 1♪
のように、後半は前半と符号が逆(絶対値は同じ)。なぜなら…
  26 = (25) × 21 ≡ (−1) × 21 ≡ −2 (≡ 9)
  27 = (25) × 22 ≡ (−1) × 22 ≡ −4 (≡ 7)
  28 = (25) × 23 ≡ (−1) × 23 ≡ −8 (≡ 3)
  29 = (25) × 24 ≡ (−1) × 24 ≡ −5 (≡ 6)
  210 = (25) × 25 ≡ (−1) × 25 ≡ 1  ←ここは「小定理」の例
…となるから。

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

b = 6 以降も書いてないけど、例えば b = 6 ≡ −5 (mod 11) なので、6n の代わりに (−5)n を考えれば、5n とほとんど同じ――ただし、奇数乗の場合だけ、符号が逆になる。
  515 なので 61 ≡ (−5)1−5 (≡ 6)
  523 なので 62 ≡ (−5)23
  534 なので 63 ≡ (−5)3−4 (≡ 7)
  549 なので 64 ≡ (−5)49
…以下同様。この場合、b5 ≡ 1 なら (−b)5 ≡ −1 で、b5 ≡ −1 なら (−b)5 ≡ 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。そして、
  x2 ≡ 1 (mod 11) は2個の解を持ち(x = 1, 10)、
  x5 ≡ 1 (mod 11) は5個の解を持つ(x = 1, 3, 4, 5, 9)。

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

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

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

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

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

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

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

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

」が成り立つためには、
  w − 1 = xd − 1 ≡ 0  ‥‥‥「
が成り立つか、または
  wq−1 + wq−2 + … + 1 = (xd)q−1 + (xd)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 個の解を持たなければならない。要するに
  xd − 1 ≡ 0 つまり xd ≡ 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 と分解される(もちろん 22 × 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 個の素数 p1, p2, …, pt の積に等しいとき、e の約数は、素因数 p たちの幾つか(0 個以上)の積。ここで p はどれも素数だが、必ずしも相異ならない: 全部別々でもいいし、上の例の 2 のように、同じ素因数が複数個あっても構わない。

ここで p(ピー・まる) は p1, p2 などの総称。○の中には 1 ~ t の何かが入る。

同様に、自然数 f が u 個の素数 q1, q2, …, qu の積に等しいとき、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 = (p1p2…pt) × (q1q2…qu)
…の約数は、どんな成分を持つか?

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

このとき、もし 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 これが一目瞭然になるような図解を追加

証明 位数についての仮定から ae ≡ 1, bf ≡ 1 (mod p) なので:
  cef = (ab)ef = aef × bef = (ae)f × (bf)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 の位数だから当然 cd ≡ 1。←この式に c = ab と②を代入すると:
  (ab)PQ ≡ 1  ‥‥ ⑤

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

ここで再び思い出そう。b ≡ 1 の□に当てはまる数は、必ず b の位数 f の倍数だ…という事実を(補助定理1)。だから、上記 beQ ≡ 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
  つまり aPf × bPf ≡ 1  ‥‥ ⑦

前半とほとんど同じ議論になって、今度は bPf = (bf)P ≡ 1 が消えちゃうよ。だから、⑦は aPf ≡ 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乗を計算できる(二項定理を大ざっぱに使用):
  12n = (7 + 5)n = 7n + 係数×7n−1×51 + 係数×7n−2×52 + … + 5n = 7の倍数たち + 5n ≡ 5n
もっと露骨に言えば、126 = 2985984 を 7 で割ると 1 余るので、126 ≡ 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 (= 24)。フェルマーの小定理により ap−1 = a16 ≡ 1 (mod 17) なので、この世界では、任意の a の位数は、16の約数。だって、補助定理1から、a ≡ 1 の□に当てはまる数は「a の位数(それを e とする)の倍数」: 16 は□に当てはまるんだから e の倍数、つまり e は 16 の約数。

8 は p − 1 = 16 の約数だから、補助定理2によって、
  x8 ≡ 1 (mod 17)  ‥‥ ➊
は、8 個の解を持つ。16 自身も 16 の約数だから、補助定理2によって、
  x16 ≡ 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 ってことは
  x4 ≡ 1 (mod 17)
だけど、それが本当なら、その両辺を2乗すれば➊になり、この x は➊を成立させてしまう――➊を満たさないことは既に分かってるんだから、これはあり得ない!

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

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

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

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

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

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

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

もし p−1 = uv のように複数個の素数べきの積となる場合でも(u, v は相異なる素数)、一つ一つの素数べきについて上と同じ論法を使えば、位数 u の元 x の存在、位数 v の元 y の存在…を示すことができる。詳細は次の節で扱うが、補助定理3(積の位数は位数の積)を使えば、xy の位数は uv つまり 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

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

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

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

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

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

r = 3 は p − 1 = 18 の約数だから、補助定理2によって、
  yr = y3 ≡ 1 (mod 19)  ‥‥ ➌
は、3 個の解を持つ。R = 9 も 18 の約数だから、
  yR = y9 ≡ 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なら、y1 ≡ 1 となり、その両辺を3乗すると、➌を満たしてしまうので、それも不可能。

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

これは「x2 ≡ 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種類の)原始根の存在が示された。

y9 ≡ 1 を満たす y を検索すると {1, 4, 5, 6, 7, 9, 11, 16, 17}。y3 ≡ 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 = uevfwg
としよう。ここで u, v, w, … は相異なる素数、指数 e, f, g, … は 1 以上の整数。Q = ue, R = vf, S = wg, … と置くと、
  p−1 = QRS…
のように、p−1 は「1個以上の素数べき(指数は1以上)」の積となる。素数べき Q, R, S, … の指数を 1 減らしたものをそれぞれ q = ue−1, r = vf−1, s = wg−1, … とすると q, r, s, … も素数べき(指数は0以上)。

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

このとき、【3】と同様、mod p において:
  xQ ≡ 1 を満たすが xq ≡ 1 を満たさない x が Q − q 個存在し、位数 Q
  yR ≡ 1 を満たすが yr ≡ 1 を満たさない y が R − r 個存在し、位数 R
  zS ≡ 1 を満たすが zs ≡ 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 = 21 × 31 のように)。例えば e = 1 の場合、Q = ue = u1 とは素数 u 自身のことだし、q = ue−1 = u0 とは 1 のこと。その場合、
  xQ ≡ 1 を満たすが xq ≡ 1 を満たさない x
とは、
  xu ≡ 1 を満たすが x1 ≡ 1 を満たさない x
のことで、
  xu ≡ 1 の解のうち x ≡ 1 以外のもの
という単純な意味になる。

【5】 最後に、特別な場合として、素数 p = 2 を法としよう。この場合、p−1 = 1 は、素数でも合成数でもなく、1個以上の素数の積として表現されないため、上記の証明法を適用できない。けれど、原始根の定義を直接使うと、要するに位数 p−1 = 1 の元を見つければいい。a の位数とは an ≡ 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 なら、もちろん a9 ≡ 1。別の元 b の位数が 3 なら、b3 ≡ 1 だが、その両辺を3乗すると、やはり b9 ≡ 1。位数 1 の場合も同様。結局、0 と不合同な元を 9 乗すれば常に ≡ 1 になるが、それは「mod 19 において、9次方程式 x9 ≡ 1 が18種類の解を持つ」というばかげた主張であり、解の個数に関する根本法則に反している。別の角度から言えば「x9 ≡ 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 としてみる。その想定が実は無理であることは、次のように簡単に示される。
  仮定により be = bqw = (bq)w ≡ 1
   だから (bq) の位数は w
  d = qrs と w は互いに素なので、補助定理3により a(bq) の位数は dw

(bq) の位数が w より小さい可能性はない(【5】参照)。

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

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

対応する全部の素数べきについて、分子側の指数が分母側の指数以上なら、その分数は割り切れる。
例えば (p3q1r5) / (p3q0r2) = q1r3 のように。

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

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

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

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

実は「あべし」の場合、bqu ≡ 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 = 22⋅32⋅51 と f = 200 = 23⋅52 の最小公倍数は L = 1800。これは、e, f の因子である素数べき(指数は 0 以上)のうち、e, f のどちらか一方から「指数が小さくない方」を抜き出して、掛け合わせたもの: f から 23 と 52 を抜き出し(対応する e 側の素数べきは、それぞれ 22 と 51 であり、もっと小さい)、e から 32 を抜き出し(対応する f 側の素数べきは 30 = 1 に当たり、もっと小さい)、それらを掛け合わせると:
  L = 23⋅32⋅52 = 1800
L の因子のうち e から抜き出したものの積を E、f から抜き出したものの積を F とすれば:
  E = 32, F = 23⋅52, L = EF

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

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

コメント e = 24⋅32⋅53 と f = 23⋅32⋅52 のように、どの素数べきについても 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 は ae ≡ 1 を満たすのだから、
  方程式 xe ≡ 1  ‥‥「あ」
の解。「あ」には、ちょうど e 種類の解があるので(補助定理2)、mod p の(0 と不合同な) p−1 種類の元の中には、「あ」の解ではないものが (p−1)−e 個、存在する(e < p−1 と仮定しているので、この個数は1以上)。その一つを任意に選んで b とし、b の位数を f としよう。もし e と f が互いに素なら、ab の位数は ef であり(補助定理3)、すなわち積 ab を a2 とすると、a2 の位数 ef は e より大きい。

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

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

【3】 それ以外の場合――つまり、e と f が互いに素でない場合。【1】の補助命題のように e の約数 E と、f の約数 F を選べば、E は e の正の約数なので、e/E は割り切れて、正の整数になる。
  a(e/E) を A とすると、A の位数は E。
実際、AE = [a(e/E)]E = ae ≡ 1 であり(なぜなら e は a の位数)、もし E より小さい自然数「」が A ≡ 1 を満たすとすると、
  1 ≡ A = [a(e/E)] = ae/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 を a2 とすると、a2 の位数 EF = L は e より大きい。

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

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

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

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

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

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

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

簡易正誤表
21− ≡ 40210 ≡ 40
210210
220220
(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 に対して bf ≡ 1  ‥‥①
  f より小さい指数 n = 1, 2, …, f−1 に対しては bn ≢ 1

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

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

【2】 最小かどうかは分からないが、k = f は、上の式を満たす:
  (be)f = (bf)e ≡ 1e = 1  (なぜなら①)
さて、(be)k = bek ≡ 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 が be の位数。

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

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

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

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

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

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

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

※注 この条件が必要な理由は単純: 位数というのは x ≡ 1 の □ に当てはまる最小の正の整数なのだから、もし xf ≡ 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) は、nn 以下の自然数のうち 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))。原始根とファイ関数は、このように深く結び付いている。

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

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

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

【5】 質疑応答。

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

A. どんな自然数が与えられても、それを素因数分解して、素数べきの積で表すことができるのは、ご承知の通りです。今、何らかの e と f が与えられたとして、それを素数べきで表したとします。例えば、まあ適当に…
  e = 26⋅35⋅52⋅70
  (便宜上これを e = ABCD とする)
  f = 23⋅38⋅51⋅73
  (便宜上これを f = abcd とする)
…としますと、次のように、対応する素数べき(同じ素数のべき)から小さい方を抜き出して掛け合わせれば G になり、大きい方を抜き出して掛け合わせれば L になるわけです(e と f に必ず「対応する素数べき」があるようにしたいので、一方にしか含まれていない素因数については、他方には「その素数の 0 乗」が含まれていると解釈)。
  G = 23⋅35⋅51⋅70 ← eとfの公約数の最大。これ以上どこも1乗も増やせない
  (G = aBcD です)
  L = 26⋅38⋅52⋅73 ← 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次方程式の解の個数

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

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

104 − 34 は、どうだろうか?

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

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

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

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

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

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

」右辺後半の x2 + xy + y2 つまり
  x2y0 + x1y1 + x0y1
は、xayb の形の項の和: x の指数 a は順に 2→1→0、y の指数 b は順に 0→1→2、そして指数の和 a + b はどの項でも 3 で、等しい(もちろん、普通は y0 = 1 などをわざわざ書く必要ないし、x1 も単に x と書けばいい)。

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

n = 4 の場合:

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

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

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

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

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

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

《例》 55 − 25 = 3125 − 32 = 3093 は、確かに 5 − 2 = 3 で割り切れる。3093 ÷ 3 = 1031 は簡単に暗算できるけど、「」の検証のためその右辺を使うと:
  54 + 53 × 21 + 52 × 22 + 51 × 23 + 24
  = 625 + 125 × 2 + 25 × 4 + 5 × 8 + 16
  = 625 + 250 + 100 + 40 + 16 = 1031  ご名算!

」が成り立つ理由は…。

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

最初に「」の x3 − y3 = (x − y)(x2 + xy + y2) について考えてみよう。

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

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

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

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

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

次に「」の x4 − y4 = (x − y)(x3 + x2y + xy2 + y3) について。

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

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

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

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

この結果、「第1項の x 倍」と「第4項の −y 倍」だけが残って、
  (x − y)(x3 + x2y + xy2 + y3) = x4 − y4
となる。

これらの計算から分かるように、「」の右辺…
  (x − y)(xn−1 + xn−2y1 + xn−3y2 + … + x2yn−3 + x1yn−2 + yn−1)
…において、後半の丸かっこ内が展開されるとき、ほとんどの項の x 倍は、直前の項の −y 倍と打ち消し合う。

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

具体的に、残るのは xn−1 の x 倍と、yn−1 の −y 倍。つまり xn と − yn。これらは「ピュア」な項(x と y の両方が交ざっていない): つまり xy の形(因子 x と因子 y をそれぞれ1個以上含む)ではない。強いて xayb の形で書けば、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次式 xm − αm は x − α で割り切れて、
  3. 商は (m − 1) 次式 になる!

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

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

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

2次以外も、全く同様。例えば A, B, C, D, E を定数として、
  g(x) = Ax4 + Bx3 + Cx2 + Dx1 + 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 = 1/A があるなら、上の式の両辺にそれを掛けると:
  x = −B/A
つまり、もし解があるとすれば、解は上記の1個に定まる。もし解がないとすれば、もちろん解は0個。――1個か0個なのだから、「1次方程式の解は1個以下」ということが証明された!

同様に、2次方程式の場合、
  f(x) = Ax2 + Bx + C = 0  ‥‥‥「
と書ける。もしこの方程式に解がないなら、定理は正しい(「解が0個」は「2次方程式の解は2個以下」という主張に合致)。そこで、この f(x) = 0 に最低1個は解があると仮定して、その場合でも最大2個しか解がないことを示そう。f(x) = 0 の一つの解を x = α とすると:
  f(α) = Aα2 + Bα + C = 0  ‥‥‥「
ちょっとトリッキーだが、ここで f(x) からあえて 0 を引くと、こうなる:
  f(x) = f(x) − 0 = f(x) − f(α) ← なぜなら「」から 0 = f(α)
  = (Ax2 + Bx + C) − (Aα2 + Bα + C) ← 「」「」から
  = (Ax2 − Aα2) + (Bx − Bα) + (C − C) ← A, B, Cを含む項をそれぞれまとめた
  = A(x2 − α2) + 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) = Axn + Bxn−1 + Cxn−2 + … + Px2 + Qx1 + 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, … で足りなければ A1, A2, A3, … とでもすればいい。

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

ここで再び「0 を引き算」というトリックを…。「」「」から:
  f(x) = f(x) − 0 = f(x) − f(α)
  = (Axn + Bxn−1 + Cxn−2 + … + Px2 + Qx1 + R) − (Aαn + Bαn−1 + Cαn−2 + … + Pα2 + Qα1 + R)
  = A(xn − αn) + B(xn−1 − αn−1) + C(xn−2 − αn−2) + … + P(x2 − α2) + Q(x1 − α1)  ‥‥‥「
2個の定数項 R は、打ち消し合ってなくなる!

xm − αm の形の m 次式は、必ず x − α で割り切れて
  xm − αm = (x − α)[x の m−1 次式]  ‥‥‥「
になるのだった(【3】参照)。従って「」の第1項は、
  A(xn − αn) = A(x − α)[x の n−1 次式] ♥
となる。「」の第2項は(」で m = n−1 とすれば)、
  B(xn−1 − αn−1) = B(x − α)[x の n−2 次式] ♥
となる。「」の第3項は(m = n−2 とすれば)、
  C(xn−2 − αn−2) = C(x − α)[x の n−3 次式] ♥
となる。以下同様…。「」の(最後から2番目の)係数 P の項は、直接計算すると:
  P(x2 − α2) = P(x − α)(x + α) ♥
係数 Q の最後の項は、普通にこう書ける:
  Q(x1 − α1) = 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次式 x2 + 5x − 1 の3倍 3x2 + 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次式 x3 + x2 + 2x + 3 に2次式などを足しても、結果が4次式以上になることはあり得ない――どこにも x4 の発生源がないので)。「」末尾の 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 が整域であることについては、「時計ワールド」の付録を参照。

(参考)「」の正式な証明  帰納法でBAN2

【1】 次の4個の式が成り立つことは、どれも右辺を展開して直接確認できる。

x1 − y1 = (x − y)(1)  ← 当たり前

x2 − y2 = (x − y)(x + y)  ← よくある計算(掛け算の順序が普通と逆だけど)

x3 − y3 = (x − y)(x2 + xy + y2)  ← ちょいむずい?

x4 − y4 = (x − y)(x3 + x2y + xy2 + y3)  ← ゴチャゴチャしてきた…

さて、2番目~4番目の式で、それぞれの右辺の第2因子(2番目の丸かっこ内の和)は、最後の項を無視すると、一つ前の式の右辺第2因子の x 倍に等しい。例えば、4番目の式について:
  (x3 + x2y + xy2 + y3) の y3 を無視した x3 + x2y + xy2 は…
  (x2 + xy + y2)x に等しい。

右辺の第1因子は共通なので、第2因子の最終項を無視するなら、2番目~4番目の各恒等式は、直前の恒等式の両辺を x 倍したものに当たる:
  例えば x3 − y3 = (x − y)(x2 + xy + y2) の両辺を x 倍すると
  x4 − xy3 = (x − y)(x3 + x2y + xy2)  ‥‥①

上記で無視されている最終項 y は(○は最終項の指数)、第1因子 (x − y) の存在を考慮すると (x − y)y に当たる。再び4番目の恒等式を例にすると、第2因子の最終項は y3 だから、その影響は:
  (x − y)y3 = xy3 − y4 左辺と右辺を入れ替えると
  xy3 − y4 = (x − y)y3  ‥‥②

①と②を辺々足し合わせれば、4番目の恒等式になる:
  x4 − y4 = (x − y)(x3 + x2y + xy2 + y3)

要するに、3番目の恒等式
  x3 − y3 = (x − y)(x2 + xy + y2)
が与えられたとき、両辺を x 倍してから、その両辺に (x − y)y3 を足せば、4番目の恒等式になる!

一般に、xn − yn についての公式が与えられたとき、両辺を x 倍してから、その両辺に (x − y)yn を足せば、xn+1 − yn+1 についての公式が得られるのでは…

【2】 今、とある正の整数 n について、次が成り立ったとする:
  xn − yn = (x − y)[k=1nxn−kyk−1]  ‥‥③
総和記号では k は 1 から n までの整数を動くものとする。例えば n = 4 の場合:
  [k=14xn−kyk−1] = x4−1y1−1 + x4−2y2−1 + x4−3y3−1 + x4−4y4−1
  = x3y0 + x2y1 + x1y2 + x0y3

「0乗」が 1 を表すという規約の下で(x0 = 1, y0 = 1)、上の計算が正しいこと――つまり③が n = 4 に対して正しいこと――を簡単に確認できる(冒頭の公式と見比べてみよう)。③は n = 1 や n = 2 や n = 3 に対しても正しい。従って、③を仮定た上で、③の n を n+1 に置き換えた次の式が成り立つことを示せば、数学的帰納法により、③は任意の正の整数 n に対して成り立つことになる。
  xn+1 − yn+1 = (x − y)[k=1n+1xn+1−kyk−1]  ‥‥④
  (総和記号の範囲は k = 1 から n+1 まで)

【3】 それを実現するためには、最初にやったように、③の両辺を x 倍して、その両辺に (x − y)yn を足せばいーんじゃね? ③の両辺を x 倍すると:
  xn+1 − xyn = (x − y)[k=1nxn+1−kyk−1]  ‥‥⑤
  (総和記号の範囲は k = 1 から n まで)
右辺の x 倍については、[] 内を x 倍した――その結果、総和記号で足し合わされる各項の x の指数が 1 増えて、③の「xn−kyk−1」の部分が「xn+1−kyk−1」に変わった。

次に⑤の両辺に (x − y)yn を足そう。左辺については「それを展開した xyn − yn+1 を足す」と考えた方が分かりやすい。結果は:
  xn+1 − xyn + xyn − yn+1 = (x − y)[k=1nxn+1−kyk−1] + (x − y)yn
  整理すると xn+1 − yn+1 = (x − y){[k=1nxn+1−kyk−1] + yn}  ‥‥⑥
  (総和記号の範囲は k = 1 から n まで)

⑥が④と同じであることを示せば、証明が完了する。⑥と④の左辺同士は、既に等しい。問題は…。⑥で総和記号の [] の外側にある yn を総和記号の [] 内にうまく取り入れられるのか。しかもそのとき、総和記号の範囲が「n まで」から「n+1 まで」に拡大する形になるのか?

総和記号で足し算される [] 内の表現は xn+1−kyk−1 なのだから、k の範囲が「n まで」から「n+1 まで」拡大するのなら、k = (n+1) に対する下記の項が追加されることになる:
  xn+1−(n+1)y(n+1)−1
  つまり x0yn 要するに yn
都合がいいことに、これはちょうど総和記号の中に入れたかった yn と一致する。だから⑥の yn を消して、その代わり、総和記号の範囲を広げて「k = 1 から n+1 まで」とすれば、同じことになる。言い換えると、③を仮定して導かれる⑥は、示したかった④と完全に一致。これで帰納法による証明が完成した!

【4】 やれやれ、ちょいめんどかったけど、何とかなったっぽい…。誤字とかあったらごめんよ。

ごーちゃごちゃーした記号 k=1n だけど
遊んじゃえばイチバン 自由
どんな和でも どんどん解決だよ …ホイ!

無限が絡んだら 任せてね 再帰の魔法でね
バンバンバンバン 片付けちゃう
ビン ビンビンビンビン ビンビンビン カンタンだよ …ヘイ!

これでも魔女だもんね …ハイ! (本文に戻る

⁂

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

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

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

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

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

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

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

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

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

⁂


メールアドレス(画像)