チラ裏バッファ: 数学5

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

数学 / 2 / 3 / 4 / 5 / 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 − 3 = 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 は合成数!

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 の倍数: 予選落ちして候補に入ってない。)

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 は予選落ち。)

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 を除外。

両端の和マイナス真ん中(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の倍数)
# = 合成数(11の倍数)

⁂

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 は、繰り上がりなしの足し算で暗算できる!

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

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個 暗算で素数表

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以下の素数の数。

【7】 (参考) 10~220の候補中、7の倍数に特別な印を付けておき(下記では@)、以下210単位で、同じ位置をマークすると、7の倍数は機械的に除去される(7の倍数プラス210は、再び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     

10~100の範囲では 49, 77, 91 の3個が該当。従って、それらに210を足した 259, 287, 301 の3個が220~310から除外される。この考え方で7の倍数をふるうと【3】の方法より速い(210周期の車輪に当たる)。

⁂

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 において合同でないものだけを別々の解としてカウントする。

【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日おきに仕事が休み」になるわけない。

同様に、位数 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。

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

【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ページ)に当たる。

⁂

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次式になることはあり得ない)。「」末尾の 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 の世界(素数位数の有限体)でも成立し、原始根の存在証明で役に立つ。

(参考)  総和記号を使った【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 の公倍数」。

⁂


メールアドレス(画像)