チラ裏バッファ: 数学5

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

数学 / 2 / 3 / 4 / 5 / 6 / Curios / 野蛮

***

2021-11-21 【150法】コンウェイの秘技【3~4桁の数を暗算で因数分解】

2の倍数・3の倍数・5の倍数は明らか。7の倍数以降の判別法もあるにはあるけど(それ自体としては面白いけど)、実用上は「実際に割ってみた方が手っ取り早い」という感じがする。ところが…

Conway は、7の倍数~19の倍数を一気に検出するすごい裏技を編み出していた!

ただし、合成数倍については、個別に考えない。例えば、15で割り切れるかどうかを判定するには「5の倍数かどうか」を考え、イエスなら「3の倍数かどうか」と考えればいい。

【1】 説明のための例として、x = 209 を分解してみよう。

まず150のN倍で x を近似する。この場合、N=1、つまり150自体で近似すると、誤差は59。

手のひらを広げて「1回引いたら深呼吸」と言いながら、59からNを引く。手のひらの上に58をイメージする。

「親、行く」と言いながら、親指を見て、またNを引いた57をイメージする。親指を折り曲げる。

「ひどいな」と言いながら、人差し指を見て、またNを引いた56をイメージする。

「仲いいな」と言いながら、中指を見て、またNを引いた55をイメージする。中指を半分折り曲げる。

「くっさい」と言いながら、薬指を見て、またNを引いた54をイメージする。

最後に「恋さ」と言いながら、小指を見て、またNを引いた53をイメージする。

親指が曲がって、中指が半分曲がっている。これで 209 が 19 と 11 で割れることが判明。実際 209 = 19 × 11。

何をやってるのかというと…。「親、行く」は「親指イク=19」。57が19で割れるか考える。商3で割り切れるので、イエス。記録として、親指を折り曲げておく。

「ひどいな」は「人差し指イナ=17」。このステップでは、56が17で割れるか考える。ノー。

「仲いいな」は「中指イイ・ナ=11と7」。このステップでは、55が11または7で割れるか考える。イエス、11で割れる。記録として、中指を半分折り曲げておく。

「くっさい」は「薬指サイ=31」。このステップでは、54が31で割れるかチェック。ノー。

「恋さ」は「小指イサ=13」。このステップでは、53が13で割れるかチェック。ノー。

この方法で、7~19の素因数は、漏れなく検出される(31も検出される)。

【2】 別の例、x = 533。

N=3 とする。450を引いて83。以下、繰り返しNを引く。

1回引いたら深呼吸 → 手のひらの上に80がある。

親指  親)いく → 77÷19。割り切れない。

人差し指  ひど)いな → 74÷17。割り切れない。

中指  仲)いいな → 71÷11 と 71÷7 を考える。割り切れない。

薬指  くっ)さい → 68÷31。割り切れない。

小指  こ)いさ → 65÷13。商5で割り切れる。小指を曲げておく。

結論として 533 は 13 で割り切れる。13 の 2 倍は 26、そのまた 2 倍は 52 なので、13 の 40 倍は 520。それに留意しつつ暗算で割り算すると、商41。この商は素数なので、533 = 13 × 41 は素因数分解。

【3】 逆方向に、足しながらやってもいい。x = 1023。N=7 として、1050 に切り上げた方が誤差が小さい。差は27。(この x は一目で3の倍数だが、説明の例として、構わず進める。)

1回足したら深呼吸 → 手のひらの上に34がある。今度はNを繰り返し足す。

親)いく → 41÷19。割り切れない。

ひど)いな → 48÷17。割り切れない。

仲)いいな → 55÷11 と 55÷7 を考える。11で割り切れるので、中指を半分曲げておく。

くっ)さい → 62÷31。これも割り切れるので、薬指を曲げておく。

こ)いさ → 69÷13。割り切れない。

結論として x = 1023 は 11 と 31 で割り切れる。31 × 11 = 310 + 31 = 341。x が 3 で割れることは最初から分かってるので 1023 = 3 × 11 × 31 となる。

参考として、最初と同じ引き算方向でやると N = 6。900を引いて差は123。

1回引いたら深呼吸 → 117。

親)いく → 111÷19。割り切れない。

ひど)いな → 105÷17。割り切れない。

仲)いいな → 99÷11 と 99÷7 を考える。11で割り切れるので、中指を半分曲げておく。

くっ)さい → 93÷31。これも割り切れるので、薬指を曲げておく。

こ)いさ → 87÷13。割り切れない。

ちゃんと同じ結論になった!

【4】 この方法でなぜうまくいくのかの説明、さらに拡張する方法については、次の文献をごらんください。
Arthur T. Benjamin: Factoring Numbers with Conway’s 150 Method (PDF)

参考リンク:
Quick Divisibility Test for Primes up to 67
https://numbertheoryguy.com/2020/05/23/quick-divisibility-test-for-primes-up-to-67/

この方法の注意点として、因数が見つからないことの方が多いです。例題では、説明のため因数があるケースを取り上げましたが、整数が7で割れる確率は単純計算で1/7、11で割れる確率は1/11等々なので、各因数が見つかる確率は比較的小さく、3回に2回くらいは7~19の因数が一つも出ないでしょう。ヒットしなくてもがっかりせず、「それで当たり前」「その範囲の因数がないことを確定判定できた!」と肯定的に考える心構えが重要かと。順次引き算または足し算する数 N は、状況によって変わるので、単純な計算ミスに注意すること。指との「同期」がずれると正しく判定できないので、落ち着いて「1回引いたら(足したら)深呼吸」をやること。中指は 7 と 11 の2種類の因数に対応するので、混乱しないように、7 だったら軽く曲げ、11 だったら半分曲げ、7 × 11 だったら思い切り曲げるといいかも。

この方法は、Conway が1996年にイベントで披露したものだそうです。Benjamin は直接それを見聞きして、2018年に上記の記事を書いたようです。The author thanks the referee for many helpful suggestions, and especially wishes to thank John Conway for his permission to share his algorithm... までは普通の結びですが、続けて ...and for being such a large prime factor in the mathematics community. とうまいことを…。Benjamin の書いた文章のことは、インドの RESONANCE 2021年5月号で知りました。Arvind Ayyer と B. Sury の「John Horton Conway: The Magical Genius Who Loved Games」(PDF)の末尾でチラッと言及されていたのです。雰囲気的には、楕円曲線法で分解を試みるときの Baby Steps に似てる。こういうことを知るたび、世の中にはすごいことを考える人がいるもんだな~とびっくり!

理解できないような難しい研究をする学者がいるのは普通に分かるけど、簡単な算数みたいなことでも、すごいことができるんだなぁ…

(コメント) 検索エンジンで「素因数分解の技法」のようなキーワードを使っても、ベンジャミンの論文は出てこないだろう。巨大検索エンジンからは見えないことが、小さな趣味のサイトからはピンポイントでリンクできる。この現象は、脱中心の重要性を示唆しているのではないか?

⁂

2021-12-11 11で割り切れるかの判定法

【1】 3桁の数(例: ‌143)について、左端の数と右端の数の和(例: 1 + 3)が真ん中の数(例: 4)に等しい場合、その3桁の数は 11 で割り切れる。
  実際、143 = 110 + 33 = 11 × 10 + 11 × 3 = 11 × 13

この判定法を使うと、121 も 187 も 253 も、一瞬で 11 の倍数と分かる。11 の倍数だと分かれば、簡単に暗算で分解できる:
  121 = 110 + 11 とか 187 = 110 + 77 とか 253 = 220 + 33 と考えればいい…

このうち、平方数 121 = 112 は、よく登場するので、見覚えがあるかもしれない。

【2】 【1】のパターンについては、「両端の数の和、マイナス、真ん中の数」がゼロと言い換えることができる。
  例: 187 両端の数の和は 1 + 7 = 8 で、真ん中の数は 8 → 8 − 8 = 0 → 187 は 11 の倍数
  例: 253 両端の数の和は 2 + 3 = 5 で、真ん中の数は 5 → 5 − 5 = 0 → 253 は 11 の倍数

「両端の数の和、マイナス、真ん中の数」が 11 の場合にも、その3桁の数は 11 で割り切れる。
  例: 319 両端の数の和は 3 + 9 = 12 で、真ん中の数は 1 → 12 − 1 = 11 → 319 は 11 の倍数
  例: 209 両端の数の和は 2 + 9 = 11 で、真ん中の数は 0 → 11 − 0 = 11 → 209 は 11 の倍数

実際に 11 で割ってみなくても、100の位の数字と1の位の数字を足して、10の位の数字と比較するだけで、11の倍数かどうか分かる。何の役に立つかはともかく、ちょっと面白い。

このことから、407 や 517 や 539 も一瞬で 11 の倍数と分かる。このパターンについても【1】と同様、筆算の割り算と同様のことを暗算でできる。
  319 = 220 + 99 = 11 × 20 + 11 × 9 = 11 × 29
急いでる場合、末尾が 9 なら 11 を足した方が簡単に計算できることがある:
  319 + 11 = 330 = 11 × 30 だから 319 = 11 × 29
  (前半で 11 を 1 個、貸したので、後半で 11 を 1 個、返してもらう)

同様に、末尾が 7 なら 33 を足してもいい:
  407 + 33 = 440 = 11 × 40 だから 407 = 11 × 37
  (前半で 11 を 3 個、貸したので、後半で 11 を 3 個、返してもらう)

【3】 2の倍数と5の倍数は、一目で分かる。桁数が少なければ、各桁の数字を足してみることで、3の倍数も一瞬で分かる。それ以外の場合(つまり3 でも 5 でも割り切れない奇数の場合)、一般には、素数か合成数かの判定は難しい。

けれど、3桁の数については、11で割れるか割れないかは、「両端の数を足して、真ん中の数を引く」という簡単な計算で確認できる。

偶数と5の倍数を除外すると、3桁の 11 の倍数は、次の4系列、各8個に整理される:
  11 × 11 + 110k 型 121, 231*, 341, 451, 561*, 671, 781, 891*
  11 × 13 + 110k 型 143, 253, 363*, 473, 583, 693*, 803, 913
  11 × 17 + 110k 型 187, 297*, 407, 517, 627*, 737, 847, 957*
  11 × 19 + 110k 型 209, 319, 429*, 539, 649, 759*, 869, 979

(各行は、110 ずつ増える等差数列。初項は、それぞれ 121 = 112, 143 = 121 + 22, 187 = 143 + 44, 209 = 187 + 22。)

このうち*印の10個は、一目で3の倍数(3の倍数かの判定では、正直に各桁の数字を全部足さず 3, 6, 9 を無視するといい…例えば 957* については 9 + 5 + 7 ではなく 5 + 7 で判定): 素数かどうか判定したいだけなら、11で割れるかを考える以前に予選落ち。残り22個は、3の倍数ではない。3 で割り切れるかどうかはともかく、【1】【2】によって 11 の倍数を判別できる。

【4】 2桁の数が11の倍数の場合は、ぞろ目なのですぐ分かる(11, 22, 33, 44, 55, 66, 77, 88, 99)。では、4桁以上の数は?

「両端の数を足して、真ん中の数を引く」という3桁の計算を拡張すると、「奇数桁目の数の和から、偶数桁目の数の和を引く」となる:
  例: 1463 奇数桁目の数の和は 4 + 3 = 7 で、偶数桁目の数の和は 1 + 6 = 7 → 7 − 7 = 0 → 1463 は 11 の倍数
  例: 12345 奇数桁目の数の和は 1 + 3 + 5 = 9 で、偶数桁目の数の和は 2 + 4 = 6 → 9 − 6 = 3 → 12345 を 11 で割ると 3 余る

これが成り立つ訳は次の通り。左から a, b, c という3個の数字(0~9のいずれか)を並べた3桁の数は 100a + 10b + c に当たる。
  例: 253 = 100 × 2 + 10 × 5 + 3 つまり a = 2, b = 5, c = 3
ところで 99 は 11 の倍数なので、99a は 11 で割り切れる。だから 100a を 11 で割った余りは、100a − 99a = a を 11 で割った余りに等しい。
  例: 200 を 11 で割った余りは、2 を 11 で割った余り(つまり 2)に等しい。
一方、11b は 11 で割り切れるので、10b を 11 で割った余りは 10b − 11b = −b を 11 で割った余りに等しい。
  例: 50 を 11 で割った余りは、−5 を 11 で割った余りに等しい。−5 を 11 で割ると、商が 0 で余りが −5 とも言えるし、商が −1 で余りが 6 とも言える。
最後に、1桁の数 c を 11 で割った余りは、当然 c 自身。以上を総合すると、100a + 10b + c を 11 で割った余りは、a − b + c に等しい。これは、もともとの3桁の数の両端の桁 a と c を足し合わせて、真ん中の桁 b を引き算することに当たる。

より一般的に、10 ≡ −1 (mod 11) なので、n が偶数のとき、10n ≡ 1。従って、1の位、100の位、1万の位…など(奇数桁目)の数が x だったとすると、10nx を 11 で割った余りは、x を 11 で割った余りに等しい。一方、n が奇数のとき、10n ≡ −1。従って、10の位、1000の位、10万の位…など(偶数桁目)の数が x だったとすると、10nx を 11 で割った余りは、−x を 11 で割った余りに等しい。各桁ごとに発生する余りを全部かき集めると、全体を11で割ったときの余りとなる。最初と逆に、1の位を A、10の位を B、100の位を C…と書くと:
  A + 10B + 102C + 103D + … を 11 で割った余りは
  A − B + C − D + … を 11 で割った余りに等しい。

⁂

2021-12-15 11の倍数の秘密

1で終わる3桁の数は、上位桁に 1→2, 2→3, 3→4 のような「1個上がるパターン」があれば11の倍数:

2で終わる3桁の数は、上位桁に 1→3, 2→4, 3→5 のような「2個上がるパターン」があれば11の倍数:

3で終わる3桁の数は、上位桁に 1→4, 2→5, 3→6 のような「3個上がるパターン」があれば11の倍数:

…以下同様に進めて、7で終わる3桁の数は、上位桁に 1→8, 2→9 という「7個上がるパターン」があれば11の倍数だが、10進法の性質上、真ん中の桁は9より大きくなれない。この場合、その限界に達した後では 4→0, 5→1 のような「4個下がるパターン」に切り替わる:

+7 ≡ −4 (mod 11) なので、2種類のパターンは本質的に同じ。このような切り替わりは、どのパターンでも起こり得る。

8で終わる3桁の数は、上位桁に 1→9 という「8個上がるパターン」があれば11の倍数だが、その先では「3個下がるパターン」に切り替わる:

9で終わる3桁の数については、「9個上がるパターン」はもともと無理なので、もし11の倍数なら、上位桁に 2→0, 3→1, 4→2 のような「2個下がるパターン」が現れる:

一般に、最下位桁が N のとき、上位桁が「N 個上がる」か「11−N 個下がる」なら、それは11の倍数。

この性質は部分的には、4桁の数にも拡張可能。

11の倍数の判定法自体は簡単だけど、こういうパターンがあるんだなぁ…ということを心の片隅にとどめておくと、11の倍数の「におい」が何となく感じられるかもしれない。

⁂

2021-12-12 7で割り切れるかの判定法

7の倍数の判定法はいろいろあって、どれも面白い。今回はその一つを検討したい。この方法が最善かどうかはケースバイケースだが、やり方は単純明快。

【1】 基礎となる操作は、与えられた自然数を「右端」(末尾の桁)と「残り」(末尾の桁以外の部分)に切り分けること。例えば:
  203 → 「右端」は 3 で「残り」は 20
  456 → 「右端」は 6 で「残り」は 45
  91 → 「右端」は 1 で「残り」は 9

計算としては、「右端」の2倍を「残り」から引く。例えば:
  203 → 20 − 6 = 14
  456 → 45 − 12 = 33
  91 → 9 − 2 = 7

結果が7の倍数になったら、もともとの数も7の倍数; 結果が7の倍数にならなければ、もともとの数も7の倍数ではない。上の例では:
  203 と 91 は7の倍数;
  456 は7の倍数ではない。

【2】 必要ならこの方法を反復適用すると、通常1回ごとに1桁短くなり、やがて容易に判定できる小さな数にたどり着く。例えば 1234 は 7 で割り切れるだろうか?
  1234 → 「右端」が 4、「残り」が 123 → 123 − 8 = 115
この数 115 が7で割り切れるかどうか、直接割り算してもいいのだが、115 に再び同じ判定法を適用すると:
  115 → 「右端」が 5、「残り」が 11 → 11 − 10 = 1 → 7の倍数でない

実は、この方法にはいろいろと高速化の余地がある。以下、文献には載っていないようなショートカットを紹介するが、全部オプション。「計算を省力化するためには、場合分けの手間が発生する」というトレードオフがある。複雑なことを考えたくない場合、基本モードだけを使う方がいいだろう。
☆ 基本モード 右端が何であれ、その2倍を残りから引く。

【3】 ショートカット1 右端が 0 または 7 のときは、問答無用でその数を消していい。例えば:
  427 → 基本モードでは 42 − 14 = 28 → 7の倍数
  427 → 右端を消して 42 → 7の倍数
  3907 → 右端を消して 390 → 右端を消して 39 → 7の倍数でない

ショートカット1が成り立つ理由: 10A + 0 または 10A + 7 が 7 で割り切れるかどうかは、A が 7 で割り切れるかどうかと同じ。ここで 0 または 7 は「右端」に当たり、A は「残り」に当たる。

同様の理由から、下2桁・下3桁などが7の倍数だったら、その部分を問答無用で消していい。例えば「21 は7の倍数」「43 は7の倍数でない」ということが一目で分かるなら、「4321 は7で割り切れない」ということも一目で分かる。4321 の 21 を消して、43 で判定できるから。

左端の1桁・2桁・3桁などが7の倍数だったら、その部分も問答無用で消していい。例えば…
  219 → 21 は7の倍数なので消す → 9 は7の倍数ではない
  766 → 7 は7の倍数なので消す → 66 は7の倍数ではない
  3591 → 35 は7の倍数なので消す → 91 は7の倍数

【4】 ショートカット2 右端が 8 以上のときは、7 を引いてから判定した方が楽。例えば:
  508 → 基本モードでは 50 − 16 = 34 → 7の倍数でない
  508 → 501 → 50 − 2 = 48 → 7の倍数でない
  119 → 基本モードでは 11 − 18 = −7 → 7の倍数
  119 → 112 → 11 − 4 = 7 → 7の倍数

ショートカット2が成り立つ理由: ある数 n が 7 で割り切れるなら n ± 7 も 7 で割り切れる; n が 7 で割り切れないなら n ± 7 も 7 で割り切れない。…この性質は、以下でも活用される。

【5】 右端が9の場合。基本モードでは 18 を引くことになるが、ショートカット2を使うと、代わりに 4 を引けばいい(上記)。実際には、代わりに 3 を足すとさらに少し楽ができる。例えば:
  119 → 11 − 4 = 7 → 7の倍数
  119 → 11 + 3 = 14 → 7の倍数 この方が少し楽

注目点: 末尾9の数が7の倍数になるためには、「残り」が7の倍数マイナス3であることが必要。言い換えると、「残り」が7の倍数 ± 2の範囲にあるなら、もともとの数は決して7の倍数ではない。感覚がつかめると、多くのケースで、計算自体を全部省略できる。例えば…
  209 → 20 は7の倍数に近いので、209 は7の倍数ではない(判定するまでもない)
  219 → 21 は7の倍数なので、219 は7の倍数ではない(判定するまでもない)
  229 → 22 は7の倍数に近いので、229 は7の倍数ではない(判定するまでもない)

「9で終わる7の倍数」は、次の例のように、右端の 9 を消した「残り」に3を足すと、7の倍数になる:
  49, 119, 189, 259, 329, 399
☆ 高速モード(オプション) 右端が9のときは、それを消して残りに3を足す。

【6】 右端が3の場合。基本モードでは 6 を引くことになるが、ほとんどの場合、代わりに 1 を足した方が楽:
  133 → 13 − 6 = 7 → 7の倍数
  133 → 13 + 1 = 14 → 7の倍数 少し楽
  393 → 39 − 6 = 33 → 7の倍数でない
  393 → 39 + 1 = 40 → 7の倍数でない 少し楽

注目点: 末尾3の数が7の倍数になるためには、「残り」が7の倍数マイナス1であることが必要。言い換えると「残り」が7の倍数と2以上ずれているとき、もともとの数は決して7の倍数ではない。例えば…
  173 → 17 は7の倍数から遠いので、173 は7の倍数ではない(判定するまでもない)
  183 → 18 は7の倍数から遠いので、183 は7の倍数ではない(判定するまでもない)
  193 → 19 は7の倍数から遠いので、193 は7の倍数ではない(判定するまでもない)

「3で終わる7の倍数」は、次の例のように、末尾の 3 を消した「残り」が7の倍数に近い:
  63, 133, 203, 273, 343, 413
☆ 高速モード(オプション) 右端が3のときは、それを消して残りに1を足す。

末尾1の数末尾7の数も重要だが、後者はショートカット1のおかげで、1桁分、易しい。前者も「残り」から2を引くだけなので、判定法の計算は易しい。

とはいえ、計算自体を省略できれば、一番いい。

末尾3の数が7の倍数になるのは「その数プラス7が70の倍数になるとき」に限られる。同様に、末尾7の数が7の倍数になるのは「その数マイナス7が70の倍数になるとき」に限られる。つまり、末尾が3か7の数については、70の倍数のすぐそばでだけ、7で割り切れる可能性を気にすればいい(70の倍数±7)。例えば、210 は 70 の倍数なので 203 と 217 は7の倍数だが、223, 227, 233, 237, 243, 247 などは、判定するまでもなく、7の倍数ではない。

一方、末尾が1か9の数については、7の倍数の出現パターンが比較的分かりにくい(70の倍数±21)。けれど、70の倍数±20の範囲に、このタイプの7の倍数はない。例えば 210 近辺の 199, 201, 209, 211, 219, 221 などは、判定するまでもなく、7の倍数ではない。

【7】 基本モードは「7 × 7 = 49 が10の5倍(つまり50)に近い」という事実を利用したもの。与えられた自然数を n = 10A + B とする(B は右端、A は残り)。もし n が7で割り切れれば 5n も7で割り切れる; n が7で割り切れなければ 5n も7で割り切れない。要するに、n が7で割り切れるかどうかは…
  5n = 50A + 5B
…が7で割り切れるかどうかと一致。ある数が7で割り切れるかどうかという性質は、その数に7の倍数を加減しても変わらない。そこで上記 5n から、7の倍数…
  7(7A + B) = 49A + 7B
…を引き算すると:
  (50A + 5B) − (49A + 7B) = A − 2B
これは「右端」の2倍を「残り」から引いたもの。

この判定法で分かるのは「7で割り切れるかどうか」だけ。割り切れない場合、余りが何なのか、直接知ることはできない(内部的に 5n を7で割った余りを考えている。余りが 0 でないなら、n を7で割った余りとは異なる)。比較として、11の倍数の判定法では、もともとの数を11で割ったときの余りが計算される。

⁂

2021-12-13 7の倍数の形

【1】 前回、「右端の桁を2倍して、残りから引く」という判定法を紹介した:
  例 581 → 58 − 2 = 56 → 7の倍数

上の方法は、シンプルで汎用性が高く、覚えやすい。けれど、逆方向(左端)からの判定法を使った方が便利なことがある。この方法だと、前回の方法と違い、7で割った余りを正しく検出できる。参考までに…

例題1 今日が日曜なら、1000日後は何曜日?
  暗算 1000 → 20 ≡ 6 (mod 7) → 土曜日

例題2 1239 は 7 で割り切れるか?
  暗算 1239 → 239 + 20 = 259 → 59 + 4 = 63 → 7の倍数

やり方は、次の通り。3桁の数を “ABC” とする(A は 100の位、B は 10の位、C は 1の位)。最上位桁 A を 2 倍して “BC” に足す。結果が 7 で割り切れるなら、もともとの数も 7 で割り切れる。結果が 7 で割って r 余るなら、もともとの数もそうなる。

例 329 → 3 を 2 倍して 29 に足す → 29 + 6 = 35 → 7 の倍数

4桁の数を “ABCD” とする。この場合も、最上位桁 A を 2 倍して “BC” に足す。D は計算に関係しないが、結果的に A の 20 倍を “BCD” に足すことに当たる。上の「例題2」参照。

【2】 さて、7の倍数を感覚的に認識するため、よく使う小さい積について、「こんな数だな…」とイメージがあると役立つ。丸暗記する必要はないが、毎回、判定計算をするのも面倒なので…。
  7 × 10 = 70 ← これをベースに…
  7 × 11 = 70 + 7 = 77
  7 × 12 = 70 + 14 = 84
  7 × 13 = 70 + 21 = 91
  7 × 14 = 70 + 28 = 98
  7 × 15 = 70 + 35 = 105
  7 × 16 = 70 + 42 = 112
  7 × 17 = 70 + 49 = 119

91 と 119 は、素数と勘違いされることがある。

豆知識 1と9から成る2~3桁の数のうち、19, 191, 199, 919, 991 は全部素数だが、91 と 119 は合成数。

【3】 重要なのは、7の倍数のうち、末尾が 1, 3, 7, 9 のもの。

それ以外の末尾(偶数や5)、例えば 455 なら、先に2または5で割った方が考えやすい: 例えば 455 ÷ 5 は上記 91 に帰着。

4系統の7の倍数は、次のパターンを持つ。一番易しいのは末尾 7 のケース(70k + 7型)。これは70の倍数プラス7に当たり、筆算方式の暗算でも、7 で割り切れることがすぐ分かる:
  77 = 70 + 7 = 7 × 11
  147* = 140 + 7 = 7 × 21*
  217 = 210* + 7 = 7 × 31
  287 = 280 + 7 = 7 × 41
  357* = 350 + 7 = 7 × 51*
  etc. (*は3の倍数)

同様に、末尾 3 のケース(70k − 7型)は、70の倍数マイナス7に当たる:
  63* = 70 − 7 = 7 × 9*
  133 = 140 − 7 = 7 × 19  チェック 13 − 6 = 7
  203 = 210* − 7 = 7 × 29  チェック 20 − 6 = 14
  273* = 280 − 7 = 7 × 39*  チェック 27 − 6 = 21
  343 = 350 − 7 = 7 × 49 (= 73)  チェック 34 − 6 = 28
  etc.

70k + 7型70k − 7型については、70の倍数±7であることに気付けば、7の倍数であることは分かりやすい。7で割った商も、末尾が1または9に固定され、パターンが明確。

【4】 末尾 1 のケース(21型)は、少し分かりにくい。70の倍数プラス21に当たる:
  21* = 0 + 21* = 7 × 3
  91 = 70 + 21* = 7 × 13  チェック 9 − 2 = 7
  161 = 140 + 21* = 7 × 23  チェック 16 − 2 = 14
  231* = 210* + 21* = 7 × 33*  チェック 23 − 2 = 21
  301 = 280 + 21* = 7 × 43  チェック 30 − 2 = 28
  etc. 7で割った商は末尾3

末尾 9 のケース(49型)は、一番「見えにくい」。70の倍数プラス49(言い換えると、70の倍数マイナス21)に当たる:
  49 = 0 + 49 = 7 × 7
  119 = 70 + 49 = 7 × 17  チェック 11 − 18 = −7
  189* = 140 + 49 = 7 × 27*  チェック 18 − 18 = 0
  259 = 210* + 49 = 7 × 37  チェック 25 − 18 = 7
  329 = 280 + 49 = 7 × 47  チェック 32 − 18 = 14
  etc. 7で割った商は末尾7

3桁の7の倍数は100個以上あって、一つずつ丸暗記するのは実用的でない。でも、鍵となるのは、上記4系統。3の倍数を無視した場合、整数210個につき各2個、トータルでも整数210個につき8個。このくらいのレアさだったら、心の片隅にとどめておいても大した負担にならない。

能動的に記憶するわけではないけど、受動的に「見たら何となくレーダーに反応する」みたいな感じで…

⁂

2021-12-14 200以下の素数は46個 暗算で素数表

7の倍数11の倍数の判定法を使うと、220までの数については、だいたい暗算で素数判定できる。220以下の素数は47個(200以下の素数は46個)。

【0】 12, 14, 16, 18 のように、末尾が偶数の数は2の倍数。10, 15, 20, 25 のように、末尾が0 か 5の数は、5の倍数。だから、10以上の素数を探すとき、末尾が 1, 3, 7, 9 の数だけを考えればいい。

11   13   17   19
21*  23   27*  29
31   33*  37   39*

このうち、*を付けた 21, 27, 33, 39 は3の倍数なので、素数ではない。それらを除外すると:

11   13   17   19
     23        29
31        37      

このように、10~40 の幅30の範囲で、末尾 1, 3, 7, 9; 3, 9; 1, 7 の形の8個(語呂合わせ「意味なくサンキュー人質」)を考えれば、自動的に2の倍数・3の倍数・5の倍数はふるい落とされる。上記8個の数は3で割り切れないので、それらに30の倍数 30, 60, 90 などを足しても、依然として3で割り切れない。逆に、3の倍数に30の倍数を足しても、依然として3の倍数: 突然、素数になる可能性はない。

このことから、「意味なくサンキュー人質」のパターンは、素数候補(2, 3, 5 のどれでも割り切れない)を素早く抜き出すフィルターとして、30周期で繰り返し使える(「車輪」とも呼ばれる)。車輪は、10台(「意味なく」=11, 13, 17, 19)からスタートさせることもできるし、それに30の倍数を加えた任意の数(30の倍数+10: 例えば100 や 250)からスタートさせることもできる。

素数表を作るには、車輪の素数候補から、7の倍数・11の倍数・13の倍数…などの合成数を除外する必要がある。7の倍数といっても 21 = 3 × 7 は、3の倍数として既に除去されているし、35 = 5 × 7 は、5の倍数として既に除去されている。問題になるのは、7 が最小の素因数となる合成数: 49 = 7 × 7, 77 = 7 × 11, 91 = 7 × 13 など。同様に 121 = 11 × 11 以上では、11の倍数もふるう必要があり、169 = 13 × 13 以上では、13の倍数もふるう必要がある。

【1】 1桁の素数は、2, 3, 5, 7 の 4 個

10~40の幅30の領域にある素数は、次の8個:

11  13  17  19  意味なく
    23      29  サンキュー
31      37      人質

40~70の幅30の領域にある素数は、次の8個 −1個。49 = 72 は合成数なので除外される:

41  43  47  49@ 意味なく
    53      59  サンキュー
61      67      人質

70~100の幅30の領域にある素数は、次の8個 −2個。77 = 7 × 11 と 91 = 7 × 13 は除外される:

71  73  77@ 79  意味なく
    83      89  サンキュー
91@     97      人質

100以下の素数は、4 + 8 × 3 − 1 − 2 = 25個。

最下位桁「意味なくサンキュー人質」のパターンは、10以降の整数を30個ずつに区切って、各区間から8個の素数候補を選出するフィルター。このように周期的に使える「ふるい」は「車輪ふるい」と呼ばれる。この車輪ふるいは、偶数・3の倍数・5の倍数を自動的に予選落ちさせてくれる。だから3の倍数などについては一切考える必要なく、当面7の倍数だけに気を付ければいい(49, 77, 91)。

【2】 100~130の幅30の領域にある素数候補8個のうち、除外されるのは何個だろうか?

101  103  107  109  意味なく
     113       119  サンキュー
121       127       人質

121 = 112 は一目で分かるだろう(あるいは11の倍数の判別法=両端の2桁の和が真ん中の桁に等しい)。121 を超えると、最小因子11の合成数が含まれるので、7の倍数と11の倍数を手動でふるう必要がある。

7の倍数のうち、末尾3, 7のものは、70の倍数の近くにしかないし、21型も 70 + 21 = 91 の次は 140 + 21 = 161 なので、この範囲にはないが、49型が怪しい。果たして 70 + 49 = 119 = 7 × 17 は合成数!

覚え方 119番・週七日 (119は緊急用電話番号なので何曜日でも受け付け)

100~130の素数 101, 103, 107, 109; 113; 127

除外された数(2個) 119 = 70 + 49 と 121 = 112

さて、130~160の幅30の領域にある素数候補8個のうち、除外されるのは何個だろうか?

131  133  137  139  意味なく
     143       149  サンキュー
151       157       人質

140の近くなので、140 ± 7 = 133, 147 を警戒し、合成数 133 = 7 × 19 を除外。(147 は 3 の倍数: 予選落ちして候補に入ってない。)

覚え方 瞳さん(131)・週七日 (瞳つまり目には休みの曜日がない=働き者の瞳さんに感謝)

11の倍数は? 両端の和が真ん中の数に等しい 143 は、11の倍数(11 × 13)。これも除外。

130~160の素数 131, 137, 139; 149; 151, 157

除外された数(2個) 133 = 140 − 7 と 143 = 110 + 33

まとめると、100~160には(16候補中、計4個が除外されて)12個の素数がある!

【3】 160より先を考える場合、13の倍数が絡んでくる。とりあえず必要なのは、132 = 169 ということ:
  13 × 13 = 13 × 10 + 13 × 3 = 130 + 39 = 169

13 が最小因子となる次の合成数は 13 × 17 = 130 + 91 = 221 なので、220までの範囲では、169 だけに気を付ければいい。

では、160~190の幅30の領域にある素数候補8個のうち、除外されるのは何個だろうか?

161  163  167  169  意味なく
     173       179  サンキュー
181       187       人質

上述のように 169 = 132 は除外される。

7の倍数は? 70の倍数から遠い領域なので末尾3, 7の数はセーフだが、21型・49型は怪しい。果たして 140 + 21 = 161 = 7 × 23 が除外される。(140 + 49 = 189 は予選落ち。)

覚え方 イロい(161=エロい)人・週七日 (エロい人は毎日元気)

11の倍数は? 両端の和が真ん中の数に等しい 187 = 11 × 17 を除外。

160~190の素数 163, 167; 173, 179; 181

除外された数(3個) 161 = 140 + 21 と 169 = 132187 = 110 + 77

最後に、190~220の幅30の領域にある素数候補8個を考えてみたい。

191  193  197  199  意味なく
     203       209  サンキュー
211       217       人質

210 に近いので、210 − 7 = 203 = 7 × 29 と 210 + 7 = 217 = 7 × 31 を除外。

覚え方 はたちさん(203)・週七日(はたちの若者は毎日元気)
     二人でいな(217)・週七日(元気なカップルは毎日二人きりにしてあげよう)

両端の和マイナス真ん中(2 + 9 − 0)が11になる 209 も、11の倍数なので除外(209 = 11 × 19)。

200台は全滅、210台も一つしか残らない。

倍数の分布の形から(あるいは個別に直接判定法を適用すると)、190台の4候補は全員セーフ(7の倍数・11の倍数を含まない)。

190~220の素数 191, 193, 197, 199; 211

除外された数(3個) 203 = 210 − 7 と 217 = 210 + 7、そして 209 = 110 + 99

まとめると、160~220には(16候補中、計6個が除外されて)10個の素数がある。そのうち、200~220の範囲には1個の素数しかない。

【4】 素数の数。

1桁の素数、10台の素数は、それぞれ4個あるが、20より先では、10ずつ区切った範囲に素数が4個あるのは、珍しい(四つ子素数と呼ばれる)。可能性があるのは「意味なく」の行だけ(「サンキュー」行と「人質」行では、最大でも2個しか素数がない)。

10□型は「意味なく」が4個とも素数になる例(101, 103, 107, 109)。反動で、周辺の9□型、11□型、12□型の素数は、どれも1個ずつしかない。

19□型も「意味なく」が4個とも素数。反動で、20□型の素数は1個もない。

ともあれ、これで220までの素数表を暗算できた! せっかくなので、220で止まらず、もうちょっと範囲を広げてみたい…。

221 = 13 × 17 であり、220より先を扱うには、13の倍数が問題。13の倍数は、7の倍数と同様の方法で判定可能。右端と残りに分けて、右端の4倍を残りに足せばいい:
  例 221 → 右端は1、残りは22 → 22 + 4 = 26 → 13の倍数

けれど一つ一つの数に対して、この計算をそのままするのは面倒。何か工夫できないだろうか?

⁂

2021-12-17 日本にゆかりのある素数 渋谷素数109、ポケモン素数151…

100~160の範囲の素数12個は、どれも面白い。日本にゆかりのある数も多い。

           97
101  103  107  109
     113
          127
131       137  139
               149
151       157

まず 101 は記念すべき初の3桁素数だが、10□型の素数は4個もある(101, 103, 107, 109)。このようなパターンを四つ子素数という。四つ子はかなりレアな存在で、20以下の素数密集地域を除くと、1000以下に3種類しかない。

それだけでなく、この四つ子、直前・直後の素数候補 97 と 113 も素数なので、それらを含めると六つ子素数。素数の六つ子は、1万に一つといった超レアな存在!

「意味なくサンキュー人質」の車輪ふるいでは、出だしの部分を除いて、六つ子で打ち止め。七つ子は発生しない(七つ子素数の概念はあるが、定義は複雑)。つまり 97 の直前の候補 91 = 7 × 13 と、113 の直後の候補 119 = 7 × 17 は、合成数。このうち 91 は、1クールの日数に当たる(1クールが13話、1話=1週間と仮定)。

さて、113は、どのように桁を並び替えても素数になる極めて珍しい数であり(131 と 311 も素数)、絶対的素数と呼ばれることがある。
 ※ 詳しく知りたい方は → Absolute Primes https://arxiv.org/abs/1811.08613
113 が絶対的素数なので、当然 131 と 311 も絶対的素数。

そればかりか、113 という数の桁を「変形合体」させることで、多数の素数を作ることができる: 自分自身を含めて 3, 11, 13, 31, 113, 131, 311 の7個の素数を「内包」。その数未満のどの数よりも「内包」素数が多いような数を「変形合体ロボ」と呼ぶことにすると、113 は「変形合体ロボ素数」。

この記録はすぐに 137 によって破られる。137 は、自分自身も含めて、11個もの素数を「内包」している: 3, 7, 13, 17, 31, 37, 71, 73, 137, 173, 317。すごい変形合体ぶり。この記録は、3桁の範囲では破られない。137 は、記録的な11面相・変形合体素数

143 = 11 × 13 は素数でない(両端の桁の和が真ん中の桁に等しい3桁の数は、必ず11で割り切れる)。けれど下2桁の43は素数であり、ガンダム素数と呼ぶことができる(またはガンダム・ようこ素数)。ファースト・ガンダムは52話くらいの予定だったが、43話で打ち切られてしまった。

139 は、東京素数。東京は東経139°台にある。天文計算者にはおなじみの数字かも…。一方、四つ子素数の 109 は、渋谷のランドマーク。

151 は、ポケモン素数(またはミュウ素数)。

これは初代ポケモンの数に基づく。バグポケモン(けつばん、アネデパミ、ィゃゾ…)はカウントしない。

⁂

127 = 27 − 1 は、メルセンヌ素数。M127 = 2127 − 1 もメルセンヌ素数。コンピューター関係で 127 = 0x7F は、いろいろとなじみ深い数。

けれど139を東京素数と呼ぶなら、127はソウル素数だろう。韓国の首都は、ちょうど東経127°くらいにある。歴史的には…黒歴史かもしれないが…韓国は大日本帝国の一部だったので、日本と無縁ではない。今でも日本時間の正式名称は「中央標準時」。「中央」というのは、日本国内に複数のタイムゾーンがあった時代の名残だろう。この場合の「中央」は東京の139°台ではなく、明石の 135° を基準としている(日本時間が UTC+9 なのは、天球上では 15° が1時間に当たり、135 = 15 × 9 だから)。

さて、残ったのは 149 と 157。

157 といえば、食中毒の O(オー)157。O157 は、大腸菌の型の一つだが、赤痢菌の毒素 Shiga toxin と同じタイプの毒素を持つそうだ(ほとんどの大腸菌は無害だったりむしろ有益だったりするが、これはヤバイらしい)。Shiga toxin (志賀毒素)の名は、日本の細菌学者・志賀潔(きよし)にちなむ。志賀は批判される面もあり、本国の日本では知名度が低いかもしれないけど、赤痢菌を発見した世界的大学者。赤痢菌の属名は、志賀にちなんで Shigella となっている。志賀の没年1957は、くしくも(9を取り除くと)157を含む。これはもう、157を志賀素数と呼ぶしかあるまい。

注: 大腸菌は、赤痢菌と同じ科の別の属の種であり、Shigella ではない。大腸菌の血清型O157:H7が単離されたのは、志賀の死後。けれど、どちらの病原菌も毒素が同種。腸管出血性大腸菌の毒素は Stx (=Shiga toxin) Type 1 と Type 2 に分類されるらしい。

最後に、149。それは、メルセンヌ・ファンにとって特別な数。憧れ、畏怖、あるいは青春…。M199 以下で、唯一 M149 だけが、古典技(試行除算やP−1法)では分解困難: 2149 − 1 のどの素因数 P についても、P−1 が巨大な素因子を含んでいるから。どのくらい巨大かというと、14桁(ざっと40兆。P 自体は20桁で、それが45桁の M149 の最小素因数)。「頑張ればギリギリ何とかなるかも」というレベルの100倍を超える。「楕円曲線で因数分解」は、M149 を分解する冒険だった。

12個の素数たち
101  103  107  109  四つ子・公園通り
     113       119@ 絶対的素数
121#      127       ソウル
131  133@ 137  139  絶対的素数・変形合体ロボ・東京
     143#      149  メルセンヌ最初のボス 怒首領蜂(どどんぱち)のヒバチ的存在
151       157       ポケモン(光過敏性)・志賀潔(腸管出血性)

@ = 合成数(7の倍数) 119番と瞳さん
# = 合成数(11の倍数) 両端の桁の和、イコール、真ん中の桁

⁂

2022-02-22 「日本にゆかりの素数」追加 テネシー大学 長崎の諏訪神社

PrimePages は、素数マニアの間では有名なウェブサイトだが(UTM[テネシー大学マーティン校]にホストされている)、その中に「素数の珍品たち」というトリビアのコーナーがある。これまた一部のマニアの間では大人気のページ…。以前「日本にゆかりのある素数」というメモを書いたが、一部、上記の珍品コーナーも参考にした。さすがに「ガンダム素数」はないが「ポケモン素数」は、本当にテネシー大学の珍品コーナーに収録されている。他にもアニメの話数ネタが1個くらいはあったと思う…。半分遊びのコーナーで、誰でもネタを送れるので(送っても収録されるとは限らないが)、数学的に深いネタもあれば、ばかばかしいようなネタもある。

で、先日、コーナー担当者 Honaker, Jr. と別のことでメールのやり取りをした際、「日本の長崎の諏訪神社のネタを加えたよ!」みたいな連絡が、ちょっと得意そうに書かれていた。当初のネタは「諏訪神社には、277段の長い石の階段がある」というものだった。277 は素数なので、事実なら、素数ネタのトリビアということになる。けれど…ネタを振られたので調べてみると、「277段」というのは、どうも出典がハッキリしない。確かに少数のウェブページ(特に英語版ウィキペディア)にはそう書かれているのだが、長崎青年協会広報誌2020年2月号には、こうある。「諏訪神社の階段は1番下からてっぺんまでは、小さな階段もいれると194段あります」…地元で書かれた情報だし、ウォーキングの記事なので、正確にカウントされている可能性が高い。さらに obisan @tobisan50 という方も「諏訪神社の階段は194段だったんやな!」と書いている。194説の方が有力で、277という数は(間違いとも言い切れないが)疑わしい。

そこで「諏訪神社のことを書きたいなら、73段の長坂の話の方が良いかと…。もっとも、たまたま73段ある階段なんて、いくらでもあるだろうから Curio と言えるのか疑問だが…」と返信。Honaker は、どうしても諏訪神社のことを書きたいらしく(訳の分からない人である。お互いさまだがw)、結局「諏訪神社の73段の長坂は、長崎くんちの観覧席になる」みたいな Curio が追加された。マニアックというか、もはや素数ネタと言えるのか謎だが、73が素数であることには変わりない。

というわけで、くんちを誇りにしている長崎のお祭り好きの人々は、米国の大学でも紹介されたので喜んでください(?)。「長崎の文化を紹介してくれるのはありがたいけど、何で素数のページで紹介するの?」という疑問はもっともですが、妖精のやることは、ちょっと変てこなのです(笑)。

「長崎が米国に感謝? 何か忘れてませんか?」というご批判も、ごもっともですが、国としての米国とは関係なく、単にそこにある大学の「素数好き」のページ、ってことで。

どこまで本気なのか、このトリビアの内容については「今年の10月7日になったら、また考える」そうです(10月7日=くんちの日)。

話は変わって、自走する石! 自然には謎がいっぱいある。
 https://en.wikipedia.org/wiki/Sailing_stones

さらに話は変わって、このツール。実際に役立つか不明で、安全かどうかも分からないが、技術的には面白そう。
https://github.com/ValdikSS/GoodbyeDPI

Deep Packet Inspection(パケットレベルの通信盗聴・監視・ブロッキング)から、あの手この手で逃れることを目指している。もちろん通信の秘密が守られ、こんなツールが必要にならないことが理想なのだが…

国・地域によっては、Great Firewall に代表されるような、厳しいアクセス制限があるのは周知の事実。一番分かりやすいパターンは「権力者にとって不都合な情報へのアクセスを妨害して、隠す」という思想統制だが、実際にはもっと複雑で「安全な通信路を提供する」と称して、逆にその通信路がひそかに監視されているというパターンもある。「これをインストールすれば安全になる」と称して、変なものをインストールさせたり…

ともかく、ロシアあたりは、政府の検閲が厳しくて、ウェブも自由に見られないらしい。中国よりはましかもしれないが…。

⁂

2021-12-18 13の倍数の見分け方 104 = 13 × 8 と 105 = 15 × 7 の謎

【1】 13で割り切れるかどうかの判定法は、7で割り切れるかどうかの第一判定法と似ている。右端の数字を4倍して、残りに足せばいい:
  例 312 → 右端は2、残りは31 → 31 + 2 × 4 = 39 → 13 で割り切れる
  例 183 → 右端は3、残りは18 → 18 + 3 × 4 = 30 → 13 で割り切れない

原理は簡単だが、末尾の数が大きいとき、正直にやるとちょっと面倒。例えば末尾が 9 のとき、36 を足す代わりに 3 を引いた方が楽:
  例 689 → 右端は9、残りは68 → 正直にやると 68 + 36 = 104 → 13 で割り切れる
  例 689 → 右端は9、残りは68 → 代わりに 68 − 3 = 65 → 13 で割り切れる
+36 ≡ −3 (mod 13) なので、13で割り切れるかどうかに関する限り、どちらでも同じこと。

同様に、例えば末尾 3 なら、12 を足す代わりに 1 を引き、末尾 7 なら、28 を足す代わりに 2 を足せばいい。

もちろん、小さい 13 の倍数を認識できる必要がある。
  13 × 1 = 13
  13 × 2 = 26
  13 × 3 = 39
  13 × 4 = 52 = 26 × 2
  13 × 5 = 65 = 13 × 10 ÷ 2 = 130 / 2
…くらいは常識で分かるとして、
  13 × 6 = 78 = 13 × 3 × 2 = 39 × 2 = (40 − 1) × 2 = 80 − 2
  13 × 7 = 91 = 70 + 21
  13 × 8 = 104 = 13 × 4 × 2 = 52 × 2
…などが必要になることも。もっとも、104 が 13 で割り切れるかどうか迷ったら、その末尾の4倍(つまり16)と、残りの10の和(つまり26)で判定すればいい。

【2】 【1】の判定法の証明。10 × 4 = 40 は 13 × 3 = 39 より 1 大きいので:
  40 ≡ 1 (mod 13)  … ①  [40を13で割ると1余る]
与えられた数を n = 10A + B とすると、それが13で割り切れるかどうかは、次が13で割り切れるかどうかと同値:
  4n = 40A + 4B ≡ A + 4B (なぜなら①)

4倍するのは①を使うための便宜上の操作。13の倍数は4倍しても13の倍数だし、13の倍数でないものを4倍しても13の倍数にはならない。だから、n が13の倍数かどうか調べる代わりに 4n を調べても同じこと。4倍すると数がでかくなって判定が面倒になりそうだが、実際に4倍するのは右端の1桁だけ。結果的には、大抵もともとの数より簡単になる(1桁小さくなることが多い)。

【3】 いくつもの数について素数か合成数かだけ判断したい場合、一つ一つ13で割れるか試すのは効率が悪い。平方数 132 = 169 を別にすれば、221未満の数の分解において、13が最小素因子になることはない。「13で割り切れること」の判定が不可欠になる最小の整数は:
  13 × 17 = (15 − 2)(15 + 2) = 152 − 22 = 225 − 4 = 221

221 以上の数についても、130 の倍数(260, 390 など)の近辺でだけ、
  判定したい数が 130k ± 13 型または 130k ± 39 型ではないか?
ということを気にすれば十分。400程度までの範囲では、具体的に
  260 − 39 = 221 = 13 × 17
  260 − 13 = 247 = 13 × 19
  260 + 13 = 273* = 13 × 21* = 3 × 7 × 13
  260 + 39 = 299 = 13 × 23

  390 − 39 = 351* = 13 × 27* = 33 × 13
  390 − 13 = 377 = 13 × 29
  390 + 13 = 403 = 13 × 31
  390 + 39 = 429* = 13 × 33* = 3 × 11 × 13
…の5つを合成数と見誤らなければOK(*印は3の倍数なので、明らかに合成数)。

末尾を4倍して残りに足す方法も、ダブルチェック(検算)や確認に使うことができる。
  221 → 22 + 1 × 4 = 22 + 4 = 26
  247 → 24 + 28 = 52 または 24 + 28 ≡ 24 + 2 = 26
  299 → 29 + 36 = 65 または 29 + 36 ≡ 29 − 3 = 26
  377 → 37 + 28 = 65 または 37 + 28 ≡ 37 + 2 = 39
  403 → 40 + 12 = 52 または 40 + 12 ≡ 40 − 1 = 39

(参考) k = 1 の場合の 130k ± 13 と 130k ± 39:
  130 − 39 = 91 = 13 × 7 = 7 × 13
  130 − 13 = 117* = 13 × 9* = 32 × 13
  130 + 13 = 143 = 13 × 11 = 11 × 13
  130 + 39 = 169 = 13 × 13 = 132

【4】 素朴な疑問。気になる4個の数。
  (☆) 90 = 15 × 6 と 91 = 13 × 7 は 1 違い。
      104 = 13 × 8 と 105 = 15 × 7 も 1 違い。
なぜ 13 の倍数と 15 の倍数が、こんな形で接近するのだろうか?

上記の関係は、いわゆる Théorème de Bézout(ベズの定理)と関係ある。…本当は定理を最初に記述したのは、「余白が狭過ぎる本」の著者 Bachet(バシェ)。ベズが生まれる100年以上前のことだが、ベズには定理を拡張した功績がある。…ともあれ、バシェ/ベズの定理によると、整数 a, b が互いに素なら
  ax + by = 1  … ②
は、整数解 (x, y) を持つ。a = 15, b = 13 は互いに素なので、ユークリッドの互除法を使って ② の一つの解を求められる:
  15 = 1 × 13 + 2 (従って 2 = 15 − 1 × 13
  13 = 6 × 2 + 1
従って:
  1 = 13 − 6 × 2 = 13 − 6 × (15 − 1 × 13)
  整理すると −6 × 15 + 7 × 13 = −90 + 91 = 1  … ③
③左辺において、第1項に ab = 15 × 13 を足し、第2項から同じ ab を引いても、値は変わらず、引き続き等号成立:
  (−6 × 15 + 15 × 13) + (7 × 13 − 15 × 13) = 1
  分配法則から (−6 + 13) × 15 + (7 − 15) × 13 = 1
  整理すると 7 × 15 − 8 × 13 = 105 − 104 = 1  … ④

a と b が互いに素のとき、②に解があることは定理からの帰結だが、この例の場合、a, b がほぼ等しく、絶対値において最小の解 x, y がちょうど a, b の半分くらいなので、③④を眺めたとき(☆)のような「ちょっと面白い感じ?」がする。

【5】 b を b で割るともちろん(商は 1 で)余りは 0 なので、b ≡ 0 (mod b)。同様に by ≡ 0 (mod b) でもある。②の等号を、mod b の合同記号に置き換えると:
  ax + by ≡ ax + 0 ≡ 1 (mod b)  [なぜなら by ≡ 0]
…要するに「a が法 b と互いに素の場合、ax ≡ 1 (mod b) を満たす x が存在」。7 の倍数の判定法で「右端」の −2 倍、13の倍数の判定法で「右端」の 4 倍を考えることは、それぞれ、10x ≡ 1 (mod 7) の解 x ≡ −2 と、10x ≡ 1 (mod 13) の解 x ≡ 4 を利用したもの。「ax ≡ 1 が解を持つ」ということは、「a が逆数 a−1 = x を持つ」ことに他ならない。一般に、b で割り切れるかどうかの判定法では、法 b における 10 の逆数を利用できる。

例えば 10x ≡ 1 (mod 19) の解は x = 2 なので(なぜなら 10 の 2 倍を 19 で割ると 1 余る)、19 の倍数の判定法はシンプル: 右端の2倍を残りに足せばいい。

⁂

2021-12-21 17²は繰り上がりなしで暗算可能 どうやって?!

トリビア 172 と 182 は、繰り上がりなしの足し算で暗算できる!

えーっ、どうやって??? 

単純に考えれば (10 + 7)2 = 102 + 2 × 7 × 10 + 72 = 100 + 140 + 49 = 289 だが、いろいろ遊んでみよう!

182 は易しい:
  182 = (2 × 9)2 = 22 × 92 = 4 × 81 = 324
9 × 9 = 81, 4 × 8 = 32, 4 × 1 = 4 という掛け算の九九だけを使って、繰り上がりがどこにも生じていない。

一方、64 の2倍が 128、そのまた2倍が 256 ということは、よく知られている。つまり 64 × 4 = 256。これを使うと、182 と同様にして:
  162 = (2 × 8)2 = 22 × 82 = 4 × 64 = 256

172 は、上記 162 = 256 と 182 = 324 の間にあるので、だいたい300だろう。

トリビア2  112 = 121 だが、172 は、16進数の 112 = 121 に当たる(便宜上☆で16進数を表す):
  16 = 10, 17 = 10 + 1 なので
  172 = (10 + 1)2
  = 102 + 2 × 10 × 1 + 12
  = 100 + 20 + 1 = 121

トリビア2をもっと普通に書くと:
  172 = (16 + 1)2 = 162 + 2 × 16 × 1 + 12 = 256 + 32 + 1 = 289
  → 172 も繰り上がりなしの足し算になる!

ただし、162 = 256 と 16 × 2 = 32 を知ってれば…。そのような条件を付けず、「絶対に繰り上がりしない」という縛りプレーでやってみよう:
  122 = (10 + 2)2 = 102 + 2 × 10 × 2 + 22 = 100 + 40 + 4 = 144
1グロス=12ダース=144は常識かもしれないが、念のため計算した。さて:
  172 = (5 + 12)2 = 52 + 2 × 5 × 12 + 122
  = 25 + 10 × 12 + 144
  = 25 + 120 + 144
  = 145 + 144 = 289
…要するに、17の2乗は「2グロス1」に当たる!

PNG画像

⁂

2021-12-22 300以下の素数は62個 暗算で素数表(2)

200以下の素数は46個」――「車輪」を7回転させ、10~220の範囲の素数表を得た。今回は、車輪をあと3回転させ、310まで素数表を広げる。

【1】 220からというのは実用上、中途半端なので、復習も兼ねて200くらいから。車輪の性質上、30の倍数プラス10の190からスタート。

191   193   197   199
      203@        209#
211         217@     

210 = 7 × 30 は7の倍数なので、それ ±7 も7の倍数:
  7 × 31 = 7 × (30 + 1) = 7 × 30 + 7 × 1 = 210 + 7 = 217
  7 × 29 = 7 × (30 − 1) = 7 × 30 − 7 × 1 = 210 − 7 = 203

209 のように、「両端の桁の和マイナス真ん中の桁」が 0 or 11 になる3桁の数は11の倍数――素数ではない:
  11 × 19 = 11 × (20 − 1) = 11 × 20 − 11 × 1 = 220 − 11 = 209
結局、20□型の素数はなく、200~220の範囲には、素数が1個しかない。その分、190台には素数がいっぱいあり、(191, 193, 197, 199) は四つ子素数。3桁の四つ子素数は3組しかないが、100~200は、四つ子に始まり、四つ子に終わる。

【2】 本題。220からの3回転は、次の9行4列:

221   223   227   229  意味なく
      233         239  サンキュー
241         247        人質

251   253   257   259  意味なく
      263         269  サンキュー
271         277        人質

281   283   287   289  意味なく
      293         299  サンキュー
301         307        人質

11の倍数は易しい。2□1の両端の数を足すと3。だから 2□1型の11の倍数は 231*(ここで*は「3の倍数」であることを強調)。つまり、左端の列に11の倍数はない。同様に、2□3の両端の和は5なので、253 は11の倍数。これが第2列から除外される。第3列に11の倍数はなく、第4列にもない(209が11の倍数だが、範囲外)。

上記候補内に、11の倍数は1個だけ。253 = 11 × 23 がふるわれた。

【3】 7の倍数。候補一つ一つに7の倍数の判定法を素直に適用するのは面倒。ここでは70の倍数(70, 140, 210, 280など)を基準に、それ ±7, ±21 をふるい落とそう。220~310の範囲では、次の3個が該当:
  [210 + 7 = 217 = (30 + 1) × 7 = 7 × 31] ←範囲外
  210 + 21 = 231* = (30 + 3) × 7 = 7 × 33*
  ① 280 − 21 = 259 = (40 − 3) × 7 = 7 × 37
  280 − 7 = 273* = (40 − 1) × 7 = 7 × 39*
  ② 280 + 7 = 287 = (40 + 1) × 7 = 7 × 41
  ③ 280 + 21 = 301 = (40 + 3) × 7 = 7 × 43

231* と 273* は、3の倍数なので予選落ち。それぞれ 33* 倍、39* 倍(つまり「3の倍数」倍)だから、当然そうなる。

この方法が成り立つ根拠。「7 × (7以上の素数)」の形の合成数をふるいたい: 7以上の素数は 11, 13, 17, 19, 23, etc. のように必ず1の位が 1, 3, 7, 9 だから、次の数を検討すれば十分:
  A群 7 × 11, 7 × 13, 7 × 21*, 7 × 23, 7 × 31, 7 × 33*, etc.
  B群 7 × 17, 7 × 19, 7 × 27*, 7 × 29, 7 × 37, 7 × 39*, etc.
このうちA群は 7 × [10の倍数 + (1 or 3)] なので、分配法則から
  70の倍数 + (7 or 21)
となる。B群は 7 × [10の倍数 − (1 or 3)] なので、分配法則から
  70の倍数 − (7 or 21)
となる。

この方法は13の倍数・17の倍数などにも応用が利く: 一般に、7以上の素数 p の倍数をふるうとき「10p の倍数 ± p」と「10p の倍数 ± 3p」だけをふるえば十分

p = 11 では、この方法を使うより、桁パターンを見た方が楽。7の倍数に関しては、ショートカットもある(【7】参照)。

付記 20p + p = 21p, 30p − 3p = 27p, 30p + 3p = 33p などは、どれも3の倍数。既に予選落ちしているので、それらをチェックするのは無駄。でも、無駄な計算を省略するには「省略できるかの判定」が必要。慣れてないと、かえってややこしくなる。最初は、無駄を承知で「10p の倍数 ±p, ±3p」を機械的に全部チェックする方が得策かもしれない。

【4】 220~310の範囲にある13の倍数。同様に考えると、260 ± 13 と 260 ± 39 は合成数:
  ① 260 − 39 = 221 = (20 − 3) × 13 = 13 × 17
  ② 260 − 13 = 247 = (20 − 1) × 13 = 13 × 19
  260 + 13 = 273* = (20 + 1) × 13 = 13 × 21*
  ③ 260 + 39 = 299 = (20 + 3) × 13 = 13 × 23

220~250の候補には、13の倍数が2個も含まれていた!

221†  223   227   229
      233         239
241         247†      

251   253#  257   259@
      263         269
271         277      

281   283   287@  289
      293         299†
301@        307      

@ = 7の倍数 【3】参照
# = 11の倍数 【2】参照
† = 13の倍数

【5】 これで、220~310の範囲の7の倍数・11の倍数・13の倍数は全部ふるい落とされた。けれど、あと一つだけ、合成数が残っている。それは
  172 = 17 × 17 = 289
という平方数。

300 までの素数表の暗算で、一つの鍵となるのは、172 がその範囲に含まれるのでは?と気付くこと(一般に、N までの素数表を作るためには √N 以下の素数でふるう必要がある)。√3 = 1.732… を使うと:
  √300 = √3 × √100 = 1.732… × 10 = 17.32…
  つまり、(17.32…)2 = 300 だから、172 は 300 より小さい。

トリビア」で紹介したように、172 = 289 は、2グロス(=288)プラス1に当たる(グロスは12ダース)。

他方、
  17 × 19 = (18 − 1)(18 + 1) = 182 − 12 = 324 − 1 = 323
なので、17 × 17 = 289 の次の「ふるう必要がある17の倍数」は320台、今回の範囲外。

【6】 結局、220~310の幅90では、24個の素数候補のうち8個がふるい落とされ、16個の素数が残る。ふるい落とされた内訳は、7の倍数3個(259, 287, 301)、11の倍数1個(253)、13の倍数3個(221, 247, 299)、17の倍数1個(289)。

220以下の素数は47個だったので、310以下の素数はそれプラス16で63個。300~310の素数は1個だけ(307)なので、300以下の素数は62個となる:
  pi(100) = 25, pi(200) = 46, pi(300) = 62
  ここで pi(N) は、N以下の素数の数。

次の事実に注目し、心の片隅にとどめておくと、記憶の整理に役立つ: 220~310の幅90を、幅30ずつ三つのエリアに分けて考える(車輪の3回転に当たる)。最初と中間の幅30には、それぞれ素数が半ダース(6個)ずつ含まれるが、最後の幅30には素数が4個しか含まれていない。言い換えると、車輪の素数候補から、合成数が順に2個・2個・4個ふるわれる。最初の2個は、どちらも13の倍数(非常に特徴的)。残りの6個のうち、7の倍数・11の倍数(計4個)は、慣れればまず見落とさない。289 = 172 と 299 = 260 + 39 だけ軽く意識しておこう。ティーンの平方数 289 はピンポイントで覚えておくべきなのだが、意外と盲点になって、素数と勘違いすることがある。91 は素数と間違われやすいことで有名だが、289 も要注意。

190台の後は、820台まで四つ子素数はない。200~800の範囲では「意味なく」の4整数の中に、最低1個は合成数が紛れ込んでいる。それを見抜いて、ふるう必要がある。

  1. 220までの素数47個を確実に分かるようにする。100までの素数25個は常識として、100~220の素数22個を追加しよう。100~160の前半1ダースと、それ以降の後半10個に分けて覚えると楽。「100台は四つ子に始まり、四つ子に終わる」ということから、実質8個と6個。
  2. 220~310の素数16個を「心の素数表」に追加。63番素数307に到達(今回)。
  3. 310~430の素数19個にチャレンジ。82番素数421に到達。気持ちの上では100番素数541に手が届きそうになるので、100個覚えることを第一目標とする。
  4. 430~520の素数15個にチャレンジ。97番素数509に到達。100番まであと一歩に思えるが、その区間は結構険しい(だから面白い)。500くらいまでの数なら、何でも暗算で素早く素因数分解できるようになる。
  5. 100個覚えられたら、今度は1000以下の素数168個を目指そう! 3桁までの数なら何でも暗算で素早く分解できるようになる。

素数表それ自体を丸暗記しても大して役立たないが、7の倍数・13の倍数・17の倍数などを識別するアルゴリズムや、299のような数の素因数分解に慣れておくと「底力」になるし、何の役に立つかと無関係に、それ自体が面白い。人生、遊びだぜ。

【7】 (参考) 10~220の候補中、7の倍数に特別な印を付けておき(下記では@)、以下210単位で、同じ位置をマークすると、7の倍数は機械的に除去される(「2, 3, 5で割り切れない7の倍数」プラス210は、再び「2, 3, 5で割り切れない7の倍数」なので)。

 11   13   17   19        221† 223  227  229
      23        29             233       239
 31        37             241       247†    

 41   43   47   49@       251  253# 257  259@
      53        59             263       269
 61        67             271       277     

 71   73   77@  79        281  283  287@ 289ṡ
      83        89             293       299†
 91@       97             301@      307     

合成数の最小素因数  @=7 / #=11 / †=13 / ṡ=17

10~100の範囲では 49, 77, 91 の3個が該当。従って、それらに210を足した 259, 287, 301 の3個が220~310から除外される。この考え方で7の倍数をふるうと【3】の方法より速い。30周期の車輪を7個束ねた「大車輪ふるい」(210周期)。このテクニックを使うには、7が最小因子となる220未満の合成数 49, 77, 91, 119, 133, 161, 203, 217 を熟知している必要がある(119番・瞳さん・イロい・はたちさん・二人でいな)。周期が210なので、300や400くらいでは、あまりありがたみが感じられないが、それより上では結構役に立つ。

⁂

2022-02-03 400以下の素数は78個 暗算で素数表(3)

200以下に素数は46個あり、日本にゆかりのある素数も多い。300以下の素数は62個。実際には、310までの素数63個を探索した。

引き続き310以降の素数を考え、トリビアや、17の倍数の判定法・19の倍数の判定法を紹介したい。7の倍数・11の倍数・13の倍数についての詳細や、車輪の原理については、過去のメモ参照。ミスタイプや計算ミスがあったら、適宜、修正して読んでください。

【1】 310~340の幅30。次の8個の数の中には、合成数が3個ある。どれか?

311  313  317  319
     323       329
331       337

① 3桁の数は「両端の桁の和 = 真ん中の桁」の場合、または「両端の桁の和 = 真ん中の桁 + 11」の場合に、11で割り切れる。319 は、このパターンなので、11の倍数。

百の位を下2桁に足してもいい: 3 + 19 = 22 は 11 の倍数なので、319 は11の倍数。

別の発想: 319 = 400 − 81 = 202 − 92 = (20 + 9)(20 − 9) = 29 × 11。

② 7の倍数については、最寄りの70の倍数 350 からアプローチ。±7 と ±21 を考えると、350 − 21 = 329 = 7 × 50 − 7 × 3 = 7 × 47 が見える(357*, 343, 371 が7の倍数であることも同時に検出される)。検算として、右端の2倍を残りから引く: 32 − 9 × 2 = 14 は 7 の倍数なのでOK。

百の位を2倍を下2桁に足してもいい: 3 × 2 + 29 = 35 は 7 の倍数なので、329 は7の倍数。

③ これで2個見つかったが、3個目が少し難しい。11と7が駄目なら、順序としてはまず13の倍数を疑うが、最寄りの130の倍数 260 or 390 は ±13 でも ±39 でも遠過ぎる。つまり、上記の範囲に「13が最小因子の数」はない。172 = 289 以上には「17が最小因子の数」があるので、17の倍数を検討しよう。最寄りの170の倍数 340 = 17 × 20 を基点に ±17 を考えると、果たして 323 = 17 × 19 が見つかる(357* = 17 × 21* も見つかる)。192 = 361 未満には「19以上が最小因子の数」はないので、残った5個は素数!

【2】 この 323 = 17 × 19 を例に、17の倍数・19の倍数の判定法を導入する。7の倍数の判定法は「右端の2倍を残りから引く」だった。19の倍数は、逆に「右端の2倍を残りに足す」ことで、判定可能:
  323 → 右端は3、残りは32 → 32 + 3 × 2 = 38
  → 38 は 19の倍数だから、もともとの 323 も 19 の倍数

この判定法は、実際に19で割り算するよりいくらか速いので、検算などで活用できる(素数表を暗算生成するとき、一つ一つの素数候補にそのまま適用するのは、効率が悪い)。

さて、13の倍数の判定法は「右端の4倍を残りに足す」だった。例えば 91 は 13 の倍数(なぜなら 9 + 1 × 4 = 13 は 13の倍数)。

一方、17の倍数の判定法は「右端の5倍を残りから引く」。例えば 323 は 17 の倍数(なぜなら 32 − 3 × 5 = 17 は 17の倍数)。7の倍数と19の倍数については、判定法が正反対なのでペアにして覚えやすいが、13の倍数と17の倍数については、判定法の符号が逆で倍率も違う。4種類のことをまとめて丸暗記しようとすると必ずごちゃごちゃになるので、じっくり一つずつ覚えよう…。

数学は頭脳ではなく実技。「やり方を頭で覚える」のではなく、実際にやって体得。

17の倍数の判定法は、あまり効率が良くないが(下手すると、普通に筆算方式で割り算した方が速い)、検算に利用できる。

【3】 もう一つの注目点として、323 は平方数 182 = 324 より 1 小さい。まず平方数自体は:
  182 = (9 × 2)2 = 92 × 22 = 81 × 4 = 324
…と繰り上がりなしに計算できる。そして、
  n2 − 1 = (n + 1)(n − 1)
なので、「平方数から1を引いた数」は、必ず「差が2の2数」の積になる。324 が 182 であることと、その1個手前の 323 が 17 × 19 であることは、そういう関係。例えば、
  18 × 20 = 360
は、それだけだと「当たり前の計算」かもしれないが、上記の性質を逆向きに使うと:
  192 = 361
…ちょっとした数の遊び?

19 の平方 361 は、1年の日数に近い(9 × 9 = 81 なので末尾は1)。
それは 360 = 18 × 20 とも関係ある。
歴史的に円周が360°なのは1年の日数と関係あるらしいから、192 が1年の日数に近いのは必然?

10台の平方:
  102 = 100, 112 = 121, 122 = 144
  132 = 169, 142 = 196 ← どちらも桁は「1, 6, 9」
  152 = 225, 162 = 256
  172 = 289 ← 2グロス1
  182 = 324 ← 81の4倍
  192 = 361 ← 1年の日数に近い

【4】 続いて340~370の幅30。次の8個の中にも合成数が3個。どれでしょ?

341  343  347  349
     353       359
361       367

① 341 は、両端の和が真ん中なので、11の倍数。

百の位を下2桁に足してもいい: 3 + 41 = 44 は 11 の倍数。

② 343 = 350 − 7 = 7 × 50 − 7 × 1 = 7 × 49 は【1】でチェック済み。= 7 × 72 = 73 と立方数。一桁の数の立方数のうち、
  1, 8, 27, 64, 125 までは、それなりに日常的な数だが、
  216, 343, 512, 729 の中には、ちょっとエキゾチックな数も…

③ 361 = 192 は【3】の通り。残りの5個は、素数!

検算: 36 + 1 × 2 = 38 は19の倍数。

351* = 390 − 39 = 13 × 27* は13の倍数だが、3の倍数なので予選落ち。357* = 340 + 17 = 17 × 21* は17の倍数だが、予選落ち。

【5】 さらに、370~400の幅30。次の8個の中にも合成数が3個。どれ?

371  373  377  379
     383       389
391       397

① 11の倍数はない。7の倍数として、371 = 350 + 21 = 7 × 50 + 7 × 3 = 7 × 53 が見つかる。

検算: 37 − 1 × 2 = 35 は7の倍数。

② 390 = 13 × 30 前後には 13 の倍数 390 ± 13 がある: 377 = 13 × 29 と 403 = 13 × 31 だが、前者が上の範囲内。

③ 17の倍数。17 × 3 = 51 を心に刻みつつ、17 × 20 = 340 を基点とすると:
  17 × (20 − 3) = 172 = 340 − 51 = 289 ← 2グロス1(平方数)
  17 × (20 + 3) = 17 × 23 = 340 + 51 = 391
後者が範囲内。【2】による検算: 39 − 1 × 5 = 34 は 17 の倍数なのでOK。

別の発想: 391 = 400 − 9 = 202 − 32 = (20 + 3)(20 − 3) = 23 × 17。…391の下2桁を入れ替えた319についても、同様の分解法が成立: 319 = 400 − 81 = 202 − 92 = (20 + 9)(20 − 9) = 29 × 11。

192 = 361 の次の「19が最小因子の数」は 19 × 23 = 437 なので、430くらいまでの範囲では、19の倍数を積極的にふるう必要はない。361 を例外として、後は17の倍数までをふるえば素数が残る。

【6】 今回は、幅30の範囲を連続3個調べた(310~400)。それぞれ素数候補を8個含むが、どれも3個が合成数としてふるい落とされたので、結局、各範囲から5個ずつ、計 5 × 3 = 15 個の素数が残った。310までの素数は63個なので、400までの素数は合計78個

ちょうど400で切りがいいので、今回はここまで。本当は400で止まらず430まで一気に進めた方がいいのだが、続きはまたいつか…。

⁂

2022-02-27 82番素数421 暗算で素数表 (4)

400以下の素数は78個だが、アルゴリズムとしては、そこで止まらず「430以下の素数は82個」まで進めた方がいい。

【1】 ほとんどの人は、2の倍数(=偶数)、5の倍数(=末尾が0か5)を一目で認識できるだろう。3の倍数も「桁の和が3の倍数か?」で判別でき、3桁程度の数ならほぼ瞬時に分かる。

「2の倍数、3の倍数、5の倍数」に対する感覚は、日常的にも数学的にも、役に立つ。さらに進めて「7の倍数、11の倍数」などは、どうだろうか…。7が最小素因数となる整数は、210単位の一定パターンで分布。10を起点にすると、10~220が1周目、220~430が2周目となる。

その2周目末尾の幅30の区間には、次の8個の素数候補(5以下の約数を持たない)がある。

401    403    407    409
       413           419
421           427

407 は一目で11の倍数(下2桁 07 に百の位の 4 を足した 11 が11の倍数だから)。「30の倍数プラス10」を起点とする幅30の8候補内に、11の倍数はあっても1個なので、1個見つかったら、それ以上11の倍数を探す必要はない。

対照的に、13の倍数については、ごくまれに8個中に2個含まれる場合がある。最初の1個が13の倍数の場合、それプラス26が末尾の1個なので、末尾も13の倍数。2周目冒頭の220~250で起きた

420 = 7 × 60 なので、それ ±7 の 427, 413 はそれぞれ 7 × 61, 7 × 59 であり、7の倍数。このように、7の倍数は、8個中に2個含まれることが普通にある。この場合で言えば、「210の倍数 ± 7」は、どちらも「7が最小素因数の合成数」。

【2】 11の倍数が1個、7の倍数が2個、ふるわれた。考えている数の範囲400~430は、192 = 361 を超えているが、232 = 529 より下なので、13の倍数・17の倍数・19の倍数の3種類も(もしあるなら)ふるう必要があり、そこまでふるえば十分。

13の倍数 最寄りの130の倍数 390 = 13 × 30 からアプローチ。可能性として ±13 と ±39 があるが、390 + 13 = 403 = 13 × 31 に気付くことは難しくない。

検算 403 の末尾桁 3 の4倍を上位2桁に足すと52。このチェックサムは13の倍数なので、もともとの数403も13の倍数。

17の倍数 最寄りの170の倍数は 340 と 510 だが、それらを基準にすると、±17 でも ±51 でも、400~430 には届かない。つまり、この範囲に17の倍数はない。

510 ± 51 は、計算するまでもなく 3 で割り切れることが見え見え(510 + 51 = 561 は、11でも割り切れる)。こういう数については、暗算素数表では、最初から無視して構わない。これを「スナイパー方式」という(合成数だと分かり切った数については、ふるい自体を省略)。

19の倍数 最寄りの190の倍数は 380 = 19 × 20。それを基準に ±19 と ±57 を考えると、437 = 380 + 57 = 19 × 23 が見つかるが、400~430の範囲より少し上。この範囲の8候補の中に、19の倍数はない。

380 + 19 = 19 × 21 = 399 も上記範囲にギリギリ届かない(21倍という時点で3の倍数と分かるので、スナイパー方式では最初から無視される)。437 は、今回の範囲外だが、ふるう必要のあるターゲットには変わりない。「次の幅30には、19が最小素因数の合成数437がある…」ということを心の片隅にキャッシュしておこう。

【3】 まとめると、次のように4個ふるわれ、4個残る。

401    403†   407#   409
       413@          419
421           427@

合成数の最小素因数 @=7, #=11, †=13

400までの素数が78個なので、401 が79番素数、この区間の最後の素数421 は、82番素数

421 は、桁が上位から下位へ次々と半分になっていく特徴的な数であり、大車輪2周目の最終素数。82番という番号(語呂合わせ「ハニー」)も覚えやすいため、暗算素数表では「過不足なく素数をカウントできているか」のチェックポイントとして使える。「95番素数499」の方が印象的に思えるが、アルゴリズム的には「ハニー」も重要な目印。ちなみに「ハニイ」の 821 も素数で、珍しい「四つ子素数」の先頭に当たる(こちらは素数番号ではなく、素数そのもの)。

たまたまというか何というか、421 という数は「一桁の素数は4個、二桁の素数は21個」という 4 & 21 というカウントとも対応している(Gyados)。

【4】 話の便宜上、ここでは「7を最小素因数とする合成数」を単に「7の倍数」と呼ぶことにする。10~220について、幅30ずつの七つの区間に区切って、順に日曜・月曜・火曜…と呼ぶことにすると、日曜には「7の倍数」が全くなく、火曜と土曜には「7の倍数」が2個あり、それ以外の曜日には「7の倍数」が1個だけある。

「7の倍数」の表(1周目)
日曜 (10~40) なし
月曜 (40~70) 49
火曜 (70~100) 77と91の二個
水曜 (100~130) 119
木曜 (130~160) 133
金曜 (160~190) 161
土曜 (190~220) 203と217の二個

このうち、49 = 72 と 77 = 7 × 11 は、一目瞭然。91 = 7 × 13 も、素数表を考えるとき、最初に認識することの一つだろう(これを認識できないと、100以下の25個の素数さえあやふやになり、13の倍数の判定でも困る)。

残りの5個は、意識して覚える必要がある。語呂合わせは、119番、瞳さん、イロい、はたちさん、二人でいな。

2周目の220~430における「7の倍数」は、上記の8個に単に 210 を足したもの。

「7の倍数」の表(2周目)
日曜 (220~250) なし
月曜 (250~280) 259
火曜 (280~310) 287と301の二個
水曜 (310~340) 329
木曜 (340~370) 343
金曜 (370~400) 371
土曜 (400~430) 413と427の二個

この表を丸暗記する必要はなく、必ずしも、この方法でふるうのが最適とも限らない。火曜日の287は、28と7が7の倍数なので一目で7の倍数と分かり、210 + 77 と考えるまでもないし、木曜の 343 = 73 なども、直接認識できる方が役立つ。細部についてはケースバイケースで、自分にとって分かりやすい方法を使えばいい。けれど、210を周期とするこのパターンの存在を知っていると、全体の見通しが良くなる。例えば日曜日の幅30をふるうとき、そこに「7の倍数」がないことは分かり切っているので、「7の倍数」をふるう手間が省ける。

素数はある意味ランダムに分布しているようだけど、実際には、日曜ゾーンは素数の密度が高くなり、火曜・土曜は素数の密度が薄くなる傾向がある! 前者では「7の倍数」が一個もふるわれないが、後者では「7の倍数」が二個ふるわれ、8候補が直ちに6候補に減るから。この「7の倍数」のパターンは、3周目以降でも全く同様。

【5】 このパターン性のため、全体像を把握するには、中途半端な400で止まらずに、430までをまとめて考える必要がある。のみならず、400までの素数は78個だが、430までの素数は82個(ハニー)。82番まで来ると、気持ちの上では100番素数に手が届きそう。もうちょっとで95番素数499に到達でき、そうなると、100番素数まであとひと息。「最初の100個の素数」は、自然な第一目標だろう(その次の目標は、1000以下の素数168個)。

⁂

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乗を計算できる(2項定理を大ざっぱに使用):
  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 は素数)について、高木貞治ていじ『初等整数論講義』による証明を紹介する。

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

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

(※)今回の内容を含む部分(ja.wikisource): PDF(JS不要), 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  ご名算!

」が成り立つ理由は…。

最初に「」の 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 が整域であることについては、「時計ワールド」の付録を参照。

(参考)  総和記号を使った【3】の説明

本文と同じ内容を総和記号を使って書いただけ。参考までに…

」右辺の2番目の丸かっこ内は:
  b = 0 から b = n−1 までの次の和  ∑ xayb
ここで a + b = n−1 つまり a = n−1−b なので、そのように置き換えると:
  b = 0 から b = n−1 までの次の和  ∑ [xn−1−byb]

今、この和の各項を b の値に応じて第b項と呼ぶと、次の2種類の積は、絶対値が同じで符号が反対なので、足し算すると打ち消し合う:
  第b項のx倍     [xn−1−byb] × x = xn−byb
  第b−1項の−y倍   [xn−1−(b−1)y(b−1)] × (−y) = −xn−byb

ただし、b = 0 のときは、第b−1項が存在しないので例外となり、第0項のx倍(すなわち xn)は消えずに残る。b = n のときも、総和の範囲外となり(第b項は存在しない)、第b−1項の−y倍(すなわち yn)も消えずに残る。どちらも、打ち消し合う相手がいないので。

それらが、すなわち「」の左辺。…「」はシンプルできれいな式なので、もうちょっとエレガントな導き方がありそうだが、ま、数学的には上の説明でもいいでしょう。

これでも魔女だもんね …ハイ!

注: 本文で「第1項・第2項・第3項…」と呼ばれているものは、b を基準にした上の書き方では「第0項・第1項・第2項…」となる。番号の付け方が違うだけで、計算内容は全く同じ。

⁂

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 の公倍数」。

⁂


メールアドレス(画像)