フォン・シュタウト&クラウセンの定理(遊びの数論37)

[遊びの数論] 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20


きちんとまとまった記事ではなく、雑多なメモ。誤字脱字・間違いがあるかもしれません。


✿ ✿ ✿ ✿ ✿


2025-01-20 なぜ 3 + 5 は 23 に等しいか?

#遊びの数論 #べき和 #(37)

奇数を次のように順々に足すと、立方数になる。
  ①初めの1個 1 = 1 = 13
  ②次の2個 3 + 5 = 8 = 23
  ③次の3個 7 + 9 + 11 = 27 = 33
  ④次の4個 13 + 15 + 17 + 19 = 64 = 43
  ···

従って、例えば:
  ①+② = 1 + (3 + 5) = 1 + 8 = 13 + 23
  ①+②+③ = 1 + (3 + 5) + (7 + 9 + 11) = 1 + 8 + 27 = 13 + 23 + 33

①+② は初めの 1+2 = 3 個の奇数の和。 ①+②+③ は初めの 1+2+3 = 6 個の奇数の和。 ①+②+③+④ は初めの 1+2+3+4 = 10 個の奇数の和。一般に、次のようになると予想される。

予想 1 から始めて最初の 1 + 2 + ··· + n 個の奇数を足した和は、 13 + 23 + ··· + n3 に等しい。

この予想は正しいか? 本当だとしたらすてきだけど、簡単に証明できるだろうか?

✿

まず「1 + 2 + ··· + n 個の奇数」という個数指定だが、要するに何個だよ、それ?

1 から n までの n 個の整数を足した和を A としよう。次の計算法は有名。
  A = 1 + 2 + ··· + (n−1) + n 同じ和を逆順に足して
  A = n + (n−1) + ··· + 2 + 1
上の二つの式を「縦に足し算」すると:
  2A = (n+1) + (n+1) + ··· + (n+1) + (n+1) 項の数は n 個
   = (n+1) × n = n(n+1)
  ∴ A = 2A/2 = n(n+1)/2

つまり 1 + 2 + ··· + n は n(n+1)/2 に等しい(まぁ、そのくらい常識かもしれないが)。よって、イントロの予想を次のように言い換えることができる。

予想 (ver. 2) 1 から始めて最初の n(n+1)/2 個の奇数を足した和は、 13 + 23 + ··· + n3 に等しい。

話が少し具体的になってきたぞ。次なる問題として、
  1 + 3 + 5 + 7 + ···
のように、1 から始めて、奇数をある個数、順々に足した和は、どんな値になるのだろうか?

いろんな考え方があるけど、あまり「ひらめき」を必要としない単純な計算法は、次の通り。

まず「偶数を順々に足した和」は、簡単に求まる。 2 から 2n までの n 個の偶数の和は:
  2 + 4 + ··· + 2n = 2 × (1 + 2 + ··· + n) = 2 × A = 2 × n(n+1)/2 = n(n+1)

便宜上、文字を変えて、「2 から 2m までの m 個の偶数の和」を B とすると(上の式の変数 n を m に改名しただけ):
  B = 2 + 4 + ··· + 2m = m(m+1)

一方、 1 から 2m までの 2m 個の整数の和 C は、 A で n = 2m とした場合なので:
  C = 1 + 2 + 3 + 4 + ···· + 2m = 2m(2m+1)/2 = m(2m+1)

〔例〕 2m = 6 の場合 m = 3 なので、そのとき C の右辺 m(2m+1) は、
  3(6+1) = 21
だ。確かに 1 + 2 + 3 + 4 + 5 + 6 に等しい。

1 + 3 + ··· + 2m−1 という m 個の奇数の和を D とすると、 D は、
  「1 から 2m までの全整数の和」から、「同じ範囲に含まれる全偶数」を引いたもの
だ。だって、ある範囲の整数から、同じ範囲の偶数を除去すれば、その範囲の奇数が残るじゃん!

要するに D は C から B を引いたものなので:
  D = C − B = m(2m+1) − m(m+1) = m((2m+1) − (m+1)) = m(m) = m2

これで、次のことが分かった。

面白い性質 1 から始めて m 個の奇数を順に足した和は、 m2 に等しい。

〔例〕 3個の奇数 1 + 3 + 5 = 9 = 32  4個の奇数 1 + 3 + 5 + 7 = 16 = 42

これはきれいな性質だっ! 少数の権力者が横暴を振るういびつな世の中にあって、数論の至純で永遠的な美は、いささかの慰めとなるであろう。

〔参考〕 この面白い性質は「四角数」というものを考えると、一見して明らか。下記の図解で、文字「a」は 1 個、文字「b」は 3 個、文字「c」は 5 個。そして、文字の合計数は 32 だ。同様の方法で、「c」を囲むように文字「d」を 7 個付け足せば、トータルの文字数は一辺 4 の正方形の面積になる。等々。

a b c
b b c
c c c

予想 (ver. 2) を証明するためには、 1 から始めて A = n(n+1)/2 個の奇数を足し合わせることを考えればいい。その足し算の結果は、「面白い性質」から:
  A2 = [n(n+1)/2]2

Faulhaber(ファウルハベル、ファウルハーバー)の法則 ∑k3 = (∑k)2 から、上記の数は、確かに 13 + 23 + ··· + n3 に等しい!

証明を厳密に完成させるためには、 Faulhaber の法則そのものを証明する必要があり、それには、
  13 + 23 + ··· + n3 = n2(n+1)2/4 = [n(n+1)/2]2
を示さなければなるまい。そのうち二つ目の等号は単純な式変形だけど、一つ目の等号は比較的難しい。「3乗和の公式」の導出については、別の場所で一応ちゃんと解説してるので、ここでは繰り返さない(真面目な証明簡易的な証明)。

✿

Faulhaber の法則は「3乗和は1乗和の平方」というものだが、この法則には続きがある。「5乗和と7乗和の和は、3乗和の平方の 2 倍」というのだ。
  ∑k5 + ∑k7 = 2(∑k3)2 = 2(∑k)4
あるいは、同じことだが:
  (1/2)(∑k7 + ∑k5) = (∑k3)2 = (∑k)4

この法則を紹介したとき「最初に気付いたのは誰なのか不明」とコメントしたが、 Faulhaber の異常なまでの計算力・洞察力を思えば、17世紀の当時(1600年代)に、本人が当たり前に気付いていた可能性が高そうだ。文献上 1847年に Schumacher(シュマヘル、シューマッハ)が Gauß に当てた手紙 No. 1147 の中でも言及されてい Gauß もこの関係を知っていたことになる。 Schumacher 自身は、この等式を Jacobi からの手紙で知ったそうで、 Jacobi も――わざわざ手紙に書くくらいだから――この法則を「あまり知られていない面白い関係」と認識していたのだろう。

画像: Faulhaber の法則について言及されている。
Schumacher が Gauß に宛てた手紙(1847年)より

けれど「最初にこれに気付いたのは、19世紀の Jacobi」とは考えにくい。なぜなら ∑k3 = (∑k)2 は古くから知られていた有名な関係で、それを知れば、ほぼ誰でも ∑k4 や ∑k5 などについても、同様のきれいな関係があるのだろうか?と好奇心を抱く。17世紀までには Faulhaber 多項式が発見されているのだから、
  ∑k5 + ∑k7 = 2(∑k3)2 = 2(∑k)4
に気付いた人が(Faulhaber 自身を含めて)当時からいただろう――ということは、想像に難くない。 Jacobi は、この法則の最初の発見者ではないだろうが、ひょっとすると、自力で独立に再発見したのかもしれない。

† https://archive.org/details/bub_gb_3jEDAAAAQAAJ/page/298/mode/1up

✿

イントロで記した 1 = 13, 3 + 5 = 23, 7 + 9 + 11 = 33 などは、同じ手紙の続きの部分で言及されている。たわいもないことだけど、美しい。

3 + 5 = 8 は、なぜ 2 の 3 乗に等しいのか? 上で見たように、 Faulhaber の法則の結果として、
  1 = 13
  1 + (3+5) = 13 + 23
  1 + (3+5) + (7+9+11) = 13 + 23 + 33
  ···
のようになってるから、最初の 1 個の奇数は 13 に等しく、それに続く 2 個の奇数の和は 23 に等しく、それに続く 3 個の奇数の和は 33 に等しい。等々。

最後に「面白い関係」(1 から 2m−1 までの m 個の奇数の和 D は m2 に等しい)の、さらなる別証明。

次の二つの和は、足し算の順序を逆にしただけで、どちらも等しい。
  D = 1 + 3 + 5 + ··· + 2m−3 + 2m−1  天
  D = 2m−1 + 2m−3 + 2m−5 + ··· + 3 + 1  地

天・地の第1項同士の和は 1 + 2m−1 = 2m だ。第2項同士の和も 3 + 2m−3 = 2m だし、第3項同士の和も 5 + 2m−5 = 2m。以下同様。

よって、天・地を項ごとに縦に足し算すると(どちらの式も項の数は m 個なので):
  2D = 2m + 2m + ··· + 2m + 2m = 2m × m = 2m2
  ∴ D = 2D/2 = m2

〔注〕 分かりにくければ 2m−1 = 7 の具体例で考えてみよう(m = 4):
   D = 1 + 3 + 5 + 7
   D = 7 + 5 + 3 + 1 縦に足すと
  2D = 8 + 8 + 8 + 8 = 32
  ∴ D = 32/2 = 16

✿ ✿ ✿


2025-01-23 12 + 22 + 32 + 42 = 30 を平方すると 「3、5、5」の法則

#遊びの数論 #べき和 #(37)

13 + 23 + 33 + 43 = 1 + 8 + 27 + 64 = 100 のような「3乗和」。それが、対応する1乗和(1 + 2 + 3 + 4 = 10)の平方に等しいことは、印象的だ。

実はこの、
  (1乗和)2 = (3乗和)
という関係には「マニアックな続編」があって、
  (3乗和)2 = (5乗和 + 7乗和)/2
が成り立つ。素朴な疑問として、
  (2乗和)2
についても、この種の恒等式があるのだろうか?

✿

とある仮説

小さい2乗数・3乗数・4乗数・5乗数
k2k3k4k5
k=11111
k=2481632
k=392781243
k=416642561024
k=5251256253125

例として、四つの数の「1乗和」「2乗和」をそれぞれ A, B とすると:
  A = 11 + 21 + 31 + 41 = 1 + 2 + 3 + 4 = 10
  B = 12 + 22 + 32 + 42 = 1 + 4 + 9 + 16 = 30

同様に「3乗和」「4乗和」「5乗和」を考えると:
  C = 13 + 23 + 33 + 43 = 1 + 8 + 27 + 64 = 100
  D = 14 + 24 + 34 + 44 = 1 + 16 + 81 + 256 = 354
  E = 15 + 25 + 35 + 45 = 1 + 32 + 243 + 1024 = 1300

われわれは「2乗和」の平方に興味がある。この例で言えば、
  (12 + 22 + 32 + 42)2 = B2 = 302 = 900
というわけだが、この B2 = 900 という数は、 B 自身以外の「○乗和」の値、つまり A, C, D, E などの値を使って、きれいに表現可能だろうか?

パズル感覚でちょっと考えてみると、とりあえず 900 は C = 100 のちょうど 9 倍、つまり 9C だ。けれど、それはこの場合限定の「偶然」で、一般には、
  (2乗和)2 = 9 × (3乗和)
が成り立つ見込みは全くない。なぜかって? 理由は単純。一般の2乗和は、
  12 + 22 + ··· + n2 = n(n + 1)(2n + 1)/6
という「n についての3次式」なので、その平方は6次式。他方、一般の3乗和は、
  13 + 23 + ··· + n3 = n2(n + 1)2/4
という4次式。 9 倍しても、4次式は4次式のままなので、6次式とイコールになるわけないっ!

「2乗和」の平方は6次式で表されるのだから、もしそれを表す簡単な別表現があるとしたら、もともと6次式である「5乗和」が関係している可能性が高い(注: 「m 乗和」の一般公式は m+1 次式)。上記の具体例でいえば、 E = 1300 という数が関係しているのでは?

そういう目で見ると、 E の 2 倍 2600 は、ターゲットである B2 = 900 の 3 倍(つまり 2700)に近い。ちょうど 100 ずれてるけど、 100 ってのは C だ。要するに、
  3B2 = 2E + C つまり 3(30)2 = 2(1300) + 100
となってる。この関係は、ひょっとしたら一般的に成り立つかもしれない。想定される一般形は:

「仮説」 3 × (2乗和)2 = 2 × (5乗和) + (3乗和)

〔補足〕 「両辺とも6次式」という点では、この「仮説」、一応つじつまは合っている。もっとも「6次式」といっても、6次の多項式の係数には無限のバリエーションがあるので、上記のイコールも「偶然」かもしれず、これだけで「同一の6次式になる」と決め付けるわけには、いかない。

その仮説、ホントかな?

最初の n 個の正の整数 1, 2, 3, ···, n について、それぞれ2乗して合計した「2乗和」を B とし、「3乗和」「5乗和」をそれぞれ C, E とする。果たして、
  「仮説」 3B2 = C + 2E
は、一般的に成り立つか?

式を使って検証してもいいけど、とりあえずお気楽に、具体的な数を使って(小さい n を当てはめて)チェックしてみる。まず 0 個の数の「○乗和」については、もちろん B = C = E = 0 なので、「仮説」の両辺は 0 で一致。 n = 1 の場合、 B = C = E = 12 = 13 = 15 = 1 なので、「仮説」の式は、
  3(1)2 = 1 + 2(1)
となり、これも正しい。 n = 2 の場合、 B = 12 + 22 = 1 + 4 = 5, C = 13 + 23 = 1 + 8 = 9, E = 15 + 25 = 1 + 32 = 33 なので:
  3(5)2 = 9 + 2(33) つまり 3 × 25 = 9 + 66

これも正しいっ! もしかして「いける」んでは、この「仮説」?

n = 3 のとき、 B = 12 + 22 + 32 = 1 + 4 + 9 = 14, C = 13 + 23 + 33 = 1 + 8 + 27 = 36, E = 15 + 25 + 35 = 1 + 32 + 243 = 276:
  「仮説」の左辺 = 3(14)2 = 3(196) = 588
  「仮説」の右辺 = 36 + 2(276) = 36 + 552 = 588
おおおっ! 一致したっっ!!

n = 4 の場合は、最初に検証済み(そもそも、それが仮説の出発点)。この「仮説」、正しいかも?!

まだ安心せず、 n = 5 の場合も試してみる。そのとき:
  B = 12 + 22 + 32 + 42 + 52 = 1 + 4 + 9 + 16 + 25 = 55
  C = 13 + 23 + 33 + 43 + 53 = 1 + 8 + 27 + 64 + 125 = 225
  E = 15 + 25 + 35 + 45 + 55 = 1 + 32 + 243 + 1024 + 3125 = 4425
  「仮説」の左辺 = 3(55)2 = 3(3025) = 9075
  「仮説」の右辺 = 225 + 2(4425) = 225 + 8850 = 9075

さらに n = 6 の場合(上の結果を一部再利用):
  B = 12 + 22 + ··· + 62 = 55 + 36 = 91
  C = 13 + 23 + ··· + 63 = 225 + 216 = 441
  E = 15 + 25 + ··· + 65 = 4425 + 7776 = 12201
  「仮説」の左辺 = 3(91)2 = 3(8281) = 24843
  「仮説」の右辺 = 441 + 2(12201) = 441 + 24402 = 24843

どちらの場合も、両辺は等しい。これで n = 0, 1, 2, 3, 4, 5, 6 の七つの入力に対して、「仮説」が正しいことが分かった。実は、七つの相異なる入力に対して値が一致するなら、二つの6次式は完全に同一なので、これによって「仮説」は証明されたのであるっ。やったぁ!

〔参考〕 「七つの入力に対して」うんぬんの根拠。「仮説」の左辺の6次式を f(n)、右辺の6次式を g(n) とし、その差 f(n) − g(n) を h(n) とする。6次式と6次式の和や差は、一般には再び6次式。例えば、もしも f(n) = 3n6 − 2n で g(n) = n6 + 8n3 だったら h(n) = f(n) − g(n) = 2n6 − 8n3 − 2n は6次式。ただし例外として、もし仮に f(n) と g(n) の6次の係数が同じなら h(n) は(6次の項が消滅して)5次式になるし、もし f, g の6次・5次の係数がそれぞれ同じなら4次式になる。同様に考えを進めると: h(n) は一般には6次式だが、 f, g の係数の一致度によっては5次式以下にもなり得るし、極端な場合には定数(0次式)になるかもしれず、特に、最も極端な場合、すなわち f(n) = g(n) の場合には、もちろん h(n) = f(n) − g(n) = 0 になる。この最も極端な場合を別にすると h(n) = 0 は6次方程式、5次方程式、等々なので、その解は最大でも6個。ところが、われわれは h(n) = 0 を満たす n を「7個」も見つけた。これは h(n) が恒等的に 0 に等しいこと、要するに f(n) = g(n) を意味する。

65 = 7776 について

上記の数値例では、小さい数(1~6)の2乗・3乗・5乗を使いました。小さい数の2乗や3乗(例えば 23 = 8 とか 33 = 27)は、日常生活で普通に扱う数値ですし、大抵の人にとっては「考えるまでもなく、パッと分かる値」でしょう。ただ 65 = 7776 だけは、比較的なじみが薄く、パッと分かりにくいかもしれません。参考までに、一つの考え方として…
  64 = (62)2 = 362 = 1296

これについては、 362 が幾つか覚えてなくても、 92 = 81 の 4 倍から 182 = 324 を得て、そのまた 4 倍から 362 = 1296 を得れば、手っ取り早い。 24 × 4 = 96 さえパッと分かれば、それ以外には繰り上がり無しで楽に暗算可能。

この「1296」という数を利用すると、 65 は、割と簡単に暗算できる:
  65 = 64 × 6 = 1296 × 6 = (1300 − 4) × 6
   = 1300 × 6 − 4 × 6 = 7800 − 24 = 7776

65 が幾つかといった個別の事柄を無理に丸暗記する必要は、もちろんないのです。数値計算なんて、コンピューターにやらせればいいわけで。でも「ちょっとした工夫で計算が楽になる」っていう原理というかコツみたいなもんは、数論でも日常生活でも役立つかもね?

「3、5、5の法則」とは

最初の n 個の正の整数について、それぞれ m 乗した合計を Sm(n) とする:
  Sm(n) = 1m + 2m + ··· + nm

Faulhaber 風の三つの恒等式
 ㋐ [S1(n)]2 = S3(n)
 ㋑ [S2(n)]2 = [S3(n) + S5(n) + S5(n)]/3 = [S3(n) + 2S5(n)]/3
 ㋒ [S3(n)]2 = [S5(n) + S7(n)]/2

このうち㋐は有名。言葉で言うと、「1乗和の平方は、3乗和に等しい」。

㋒はその「続編」のようなもの。言葉で言うと、「3乗和の平方は、5乗和と7乗和の平均に等しい」。つまり「5乗和」と「7乗和」を足して、 2 で割ったものに等しい。

㋑は、今回証明した「仮説」(の両辺を 3 で割ったもの)。言葉で言うと、「2乗和の平方は、3乗和・5乗和・5乗和の平均に等しい」。つまり「3乗和」と「5乗和の2倍」を足して、 3 で割ったものに等しい。この「3乗和・5乗和・5乗和の平均に等しい」というのが「3、5、5」の法則。

〔例1〕 n = 4 の場合。「3乗和」は 100 で、「5乗和」は 1300。「3乗和・5乗和・5乗和の平均」とは、
  (100 + 1300 + 1300)/3 = 2700/3 = 900
だ。それは「2乗和(つまり 30)の平方」に等しい!

〔例2〕 n = 10 の場合。
  B = 12 + 22 + ··· + 102 = 385
  C = 13 + 23 + ··· + 103 = 3025 (= 552)
  E = 15 + 25 + ··· + 105 = 220825
という三つの数たちは、 B2 = 148225 = (C + E + E)/3 = (C + 2E)/3 という関係を満たす。

㋑の代数的証明は次の通り。 1 から n までの整数の2乗和・3乗和・5乗和をそれぞれ B, C, E とすると:
  B = n(n + 1)(2n + 1)/6
  C = n2(n + 1)2/4
  E = n2(n + 1)2(2n2 + 2n − 1)/12

〔注〕 2乗和・3乗和の公式は既知とする。5乗和の公式の証明

B2 = (C + 2E)/3 を示す代わりに、その両辺を 36 倍した式、
  36B2 = 12C + 24E
を示す。上記 B の式の両辺を平方して、分母を払うと、
  36B2 = n2(n + 1)2(2n + 1)2 ☆
となる。一方、
  12C = n2(n + 1)2 × 3 と
  24E = 2n2(n + 1)2(2n2 + 2n − 1) = n2(n + 1)2 × (4n2 + 4n − 2)
の和は、
  n2(n + 1)2 × (3 + 4n2 + 4n − 2)
   = n2(n + 1)2 × (4n2 + 4n + 1) = n2(n + 1)2 × (2n2 + 1)2
であるから、確かに ☆ に等しい。∎

✿

恒等式㋑の発見者が誰なのかは不明。 1847年の Schumacher の手紙から推測すると、 Jacobi は既にこれに気付いていたのかもしれない。筆者が最初にこれを見た場所は、 Kraitchik (Kraïtchik) の1924年の著書 Recherches sur la théorie des nombres の12ページ。その記述は「既知の事実の一覧」というような淡々としたもので、 Kraitchik が独自にこれを(再)発見したのかどうかは、はっきりしない。とはいえ Kraitchik は同じ場所で「4乗和の平方」についての類似の恒等式も記していて、こうした関係を「もっと大きな現象」の事例と捉えていたようだ。

実際、21世紀の現在では、このような恒等式の存在は、さらに一般化・抽象化された形で研究・整理されている。でも、遊びの数論としては、
  3(12 + 22 + 32 + 42)2 = (13 + 23 + 33 + 43) + 2(15 + 25 + 35 + 45)
のような素朴な具体例が、先端的な研究よりむしろ楽しい。 Kraitchik 自身、純粋な数論研究者であると同時に、パズルや魔方陣の類いの「娯楽・息抜きとしての数学」の本も書いてる人だけど、古今東西、数論というものには「真面目な研究の要素と遊びの要素が、混ざってるような面」がある。「1, 4, 9, 16 の和の平方」と「3乗和・5乗和」の関係なんて、真面目な数学としては特に重大な問題でもないだろうし、ましてや日常生活では何の役にも立たないだろうけど、にもかかわらず、上記のような等式には「きれいで面白い」と感じさせる何かがある。

† 少し紛らわしいのだが、 Kraitchik には、 Théorie des nombres という題名(Recherches sur la が付かない)の著書もある(全2巻。1922年と1926年)。 Recherches… は、それら2巻とは別の本。

✿ ✿ ✿


2025-01-22 お知らせ 訂正・おわび

三つのメモについて。

①「なぜ 3 + 5 は 23 に等しいか?」の最後の部分の計算(別証明)に書き間違いがあり、結果は正しいものの、つじつまが合わなくなっていたので、訂正しました。「12 + 22 + 32 + 42 + 52 も 5 の倍数 v. シュタウトの定理」の中にも、微妙な不備が複数あったので、とりあえず気が付いた部分は全部修正しました。

②「なぜ 1 + 2 + 3 + 4 は 5 の倍数か? 簡単なようで深遠」と③「12 + 22 + 32 + 42 + 52 も 5 の倍数 v. シュタウトの定理」の二つのメモは、前編・後編のような関係です。前編だけでも、独立した軽い読み切り。前編・後編セットだと「フォン・シュタウト&クラウセンの定理」の証明になってます。

証明法は既存のもの(Rado による)と本質的に同じですけれど、数値例・具体例を挙げながら、なだらかに分かりやすく進んでいます。その点は良いのですが、「そもそもなぜ累乗の和がベルヌーイのあの形になるのか」という出発点が依然として天下り的。フェルマーの小定理などが必要なので、全くの予備知識ゼロで…というわけにも、いきません。でも比較で言えば、既存の教科書より分かりやすいかも。

それはともかく、ファイルサイズの都合で(詰め込み過ぎてページ『36』がでかくなり過ぎてた)、メモ②③を、①があるのと同じ新しいページ『37』に移動しました。リンクも更新したつもりですが、ページのキャッシュとかの関係で、リンク切れが発生するかもしれません。おわびしておきます。

✿

/articles/1/01/ に「チラ裏」として雑然と入っている「メモ」たちは、好奇心の赴くまま思い付きでダーッと書いてるものが多く、それ以外のディレクトリにある「記事」と違いあまり推敲などしていないため、誤字脱字、不備、書き間違いが結構多いです。書き間違いに気付いたら随時修正するので、最終的にはそう大きくは間違ってないとは思われますが、多少の不備については、ご容赦ください。

✿ ✿ ✿

2025-01-16 なぜ 1 + 2 + 3 + 4 は 5 の倍数か? 簡単なようで深遠

#遊びの数論 #べき和 #(37)

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55 という和をご存じの方は多いだろう。

12 + 22 + 32 + 42 + 52 = 1 + 4 + 9 + 16 + 25 も = 55 だっ!

結果が同じ 55 になるのは「偶然」だが、もう少し足し算すると:
  1 + 2 + ··· + 10 + 11 + 12 + 13 = 55 + 11 + 12 + 13 = 91
  12 + 22 + 32 + 42 + 52 + 62 = 55 + 36 = 91
また一致したっっ!

これも「単なる偶然」なのだが、好奇心を刺激する。「偶然ではない隠れた性質」もある。最初の例で、「11」の手前の 10 まで足した和 55 は「11」の倍数。二番目の例で、「7」の手前の 6 まで平方して足した和 91 は「7」の倍数。一般に p が素数のとき、 m 乗和 1m + 2m + ··· + (p − 1)m は p の倍数になることが多い(55 の例では p = 11, m = 1。 91 の例では p = 7, m = 2)。なぜ?

話は変わるが A = 1 + 2 + 3 + 4 = 10 とすると、 B = 13 + 23 + 33 + 43 = 1 + 8 + 27 + 64 = 100 は A2 に等しい。

一方 C = 15 + 25 + 35 + 45 = 1 + 32 + 243 + 1024 = 1300 と D = 17 + 27 + 37 + 47 = 1 + 128 + 2187 + 16384 = 18700 を足し合わせると、ちょうど 20000。つまり C + D は B2 の2倍に等しい:
  (15 + 25 + 35 + 45) + (17 + 27 + 37 + 47) = 2(13 + 23 + 33 + 43)2 = 2(1 + 2 + 3 + 4)4

このちょっと神秘的で美しい等式は「偶然」ではなく、一般に 1 から n までの1乗和・3乗和・5乗和・7乗和は、同様の関係を満たすのです。

「素数の倍数」との関連では、 1m + 2m + 3m + 4m は p = 5 のケースなので、和は 5 の倍数になる可能性が高い。事実 A, B, C, D は、どれも 5 の倍数だ。ところが m = 4 のときの 14 + 24 + 34 + 44 = 1 + 16 + 81 + 256 = 354 は 5 の倍数ではない。一体、どういう仕組みで、何が起きてるのだろうか?

✿

§1. イントロで記した「面白い現象」は、幾つかの別の話題を含んでいる。第一に 1 + 2 + ··· + 10 と 12 + 22 + ··· + 52 がどちらも 55 になるのは、面白いけど「ただの偶然」。こういう数は「三角数の四角すい数」(triangular square pyramidal number)と呼ばれ、 1 = 12 のような自明な例を別にすると、たった三つしかな三つのうち 55 と 91 については既に紹介した。三つ目(最後の一つ)は:
  1 + 2 + ··· + 645 = 12 + 22 + ··· + 852 = 208335

どうして「三つしかない」と言い切れるのか、どうやって効率的に 208335 を見つけるのかは、難しそうな問題だが、たぶん巧妙な解法が存在するのだろう。コンピューターを使ってブルートフォースの検索をすると、 208335 自体は1分もかからずに見つかる。

† https://oeis.org/A039596

§2. 立方和 13 + 23 + 33 + 43 = 100 が 1 + 2 + 3 + 4 = 10 の平方に等しい件だが、
  13 + 23 + ··· + n3 = (1 + 2 + ··· + n)2  ☆
は有名な関係で、高校の教科書などにも普通に記されているであろう。総和記号を使って書くと:
   { from k=1 to n }k3 = ( { from k=1 to n }k)2  ☆☆

ここで { from k=1 to n }k というのは「k を 1 から n まで順々に増やしながら、それらを全部足し合わせる」という意味で、要するに ☆☆ は ☆ を簡潔に書いただけ。以下ではさらに簡略に、 1 から n までの m 乗和を Sm(n) で表すことにする。
  定義 Sm(n) = 1m + 2m + ··· + nm

自然数を単純に足した和 S1(n) = 1 + 2 + ··· + n の値については、必要に応じて、大文字の N で表すことにしよう(例えば n = 4 なら N = 10 で n = 10 なら N = 55)。すると ☆ ないし ☆☆ をもっと簡単に、こう書くことができる。
  S3(n) = [S1(n)]2 つまり S3(n) = N2

m 乗和 Sm(n) を n についての式で表すこと、例えば、
  S1(n) = 1 + 2 + ··· + n = n(n + 1)/2
  S2(n) = 12 + 22 + ··· + n2 = n(n + 1)(2n + 1)/6
  S3(n) = 13 + 23 + ··· + n3 = n2(n + 1)2/4
といった公式は、よく知られている(m が小さい場合については)。 S3(n) が S1(n) つまり N の平方であることは、一目瞭然だろう。より一般的に、 m が奇数 3, 5, 7, ··· の場合、和 Sm(n) を N についての式で表すことができる。この形式は「Faulhaber の多項式」と呼ばれる。

Faulhaber(ファウルハベル、ファウルハーバー)は17世紀前半に活躍したドイツの研究者で、スイスの Bernoulli(ベルヌリ、ベルヌーイ)――18世紀に遺作として、10乗和までの公式を自慢げに公表した人――がまだ生まれてもいないうちに、既に17乗和(!)までの公式を正しく導いていた(n の式としても N の式としても)。かつては稀覯きこう本だったであろう原書を、今ではオンラインで自由に閲覧できるその計算力には圧倒される。自分自身「14乗和」まで導いたことがあるけど(Bernoulli 数の理論などのイージーな近代的ツールを使い、コンピューターで検算しながら)、「14乗和の公式」なんて特に役立つわけでもないし、われながらクレイジーな計算をしてると感じたものだった。ところが約400年前に、当時の限られた知見・リソースだけで、もっと先まで導出していた大先輩がいたのだ。一体どういう方法で Faulhaber がこの計算を行ったのか、 Knuth による論考があるものの、真相は謎に包まれている。

ともあれ S3(n) = N2 は、最初の Faulhaber 多項式。それに続く二つは:
  S5(n) = (4N3 − N2)/3 そして S7(n) = (6N4 − 4N3 + N2)/3

この二つの式は、それだけ見ると、特に印象的ではない。しかし足し合わせると、
  S5(n) + S7(n) = (6N4)/3 = 2N4
という簡潔な形になり、下記の魔法のような結論に至る。

Faulhaber の法則 「3乗和」は、「1乗和」の平方に等しい。「5乗和」と「7乗和」を足し合わせたものは、「3乗和」の平方の 2 倍に等しい(それは、「1乗和」の4乗の 2 倍でもある)。
  (15 + 25 + ··· + n5) + (17 + 27 + ··· + n7) = 2(13 + 23 + ··· + n3)2 = 2(1 + 2 + ··· + n)4

〔例〕 S1(10) = 55。 S3(10) = 3025 = 552。 S5(10) + S7(10) = 220825 + 18080425 = 18301250 = 2 × 30252 = 2 × 554

チャーミングな関係。最初に気付いたのは誰なのか不明だが、 Faulhaber 自身がこれを認識していたとしても、不思議ではない。いずれにしても Faulhaber の多項式から簡単に導かれる事柄なので、「Faulhaber の法則」と呼ぶことにする。 Wikipédia で言及されてい

関連メモ → 「なぜ 3 + 5 は 23 に等しいか?

† “Academia Algebrae”
https://archive.org/details/bub_gb_0pw_AAAAcAAJ/page/n13/mode/2up
題名はラテン語だが、本文は古風なドイツ語で解読困難。見開きページの下の方に、2ページにまたがって長々と書かれている公式自体は、比較的容易に解読可能。2ページずつ「1.」から「5.」として「13乗和」から「17乗和」が扱われ、ページの上の方には、具体例として Sm(4) が記されている(m = 13, ···, 17)。

‡ “Johann Faulhaber and sums of powers”
https://arxiv.org/abs/math/9207222

¶ “Formule de Faulhaber”
https://fr.wikipedia.org/wiki/Formule_de_Faulhaber#Polyn%C3%B4mes_de_Faulhaber
5乗和・7乗和の公式についての et donc 以下参照。

§3. Faulhaber の多項式を経由せず、古典的な m 乗和の公式から上記の法則を導くことも、難しくない。知識の整理にも役立つだろう。
  S4(n) = 14 + 24 + ··· + n4 = n(n + 1)(2n + 1)(3n2 + 3n − 1)/30
  S5(n) = 15 + 25 + ··· + n5 = n2(n + 1)2(2n2 + 2n − 1)/12
くらいまでは、まぁ何となく覚えてるとしても(4乗和の公式までの簡易的な証明、5乗和の公式までの真面目な証明)、
  S6(n) = 16 + 26 + ··· + n6 = n(n + 1)(2n + 1)(3n4 + 6n3 − 3n + 1)/42
  S7(n) = 17 + 27 + ··· + n7 = n2(n + 1)2(3n4 + 6n3 − n2 − 4n + 2)/24
になると、4次の因子と分母についてはうろ覚え、ということになりやすい。逆に言えば、それ以外の部分は m = 2, 4, 6, ··· の場合と m = 3, 5, 7, ··· の場合とで、それぞれ共通、 m = 2, 3 はよく知られている式なのだから、結局、4次の因子と分母さえ分かっていれば S6(n), S7(n) は難しくない。 Bernoulli 形式との関係などを考えてみたい。

第一に S6(n) までの各式では、古典形式での因子の(0 でない)定数項は ±1 であり、従って、分母は Bernoulli 形式の末尾の項の分母と一致。それは m = 2, 4, 6, ··· の場合 には Bernoulli 数 Bm の分母そのもの。要するに S2(n), S4(n), S6(n) の古典形式の分母は B2 = 1/6, B4 = −1/30, B6 = 1/42 の分母と一致し、迷う余地はない。一方、 m = 3, 5, 7, ··· の場合には、直前の偶数番目の Bernoulli 数を m 倍して 2 で割ったものが、 Bernoulli 形式の末尾の(つまり n2 の)係数となる。 S1(n) の分母が 2 で S3(n) は S1(n) の平方なのだから、 S3(n) の分母が 4 であることは考えるまでもないのだが、 Bernoulli 数の観点からは「B2 = 1/6 を m = 3 倍して 1/2、 それを 2 で割って 1/4」という関係になっている。

同様に S5(n) の分母は、「B4 = −1/30 を m = 5 倍して −1/6、 それを 2 で割って −1/12」ということから、 12 となり、もちろん定数項は −1 となる。

従って、 S7(n) の分母は、「B6 = 1/42 を m = 7 倍して 1/6、 それを 2 で割って 1/12」ということから 12 となりそうだが――実際、 Bernoulli 形式の末尾の係数は 1/12 なのだが――、古典形式では定数項が 2 なので、 2/24 = 1/12 でないと(つまり分母が 24 でないと)、つじつまが合わない。古典形式の公式について、S6(n) までの因子の定数項は絶対値「1」だが、 S7(n) では(4次の)因子の定数項が「2」になり、 S8(n), S9(n) では(4次または6次の)因子の定数項の絶対値がさらに増えて「3」になる、という事実(1→2→3)を意識すると、意外とすっきり理解できるかもしれない。

第二に、 S6(n), S7(n) の4次の因子の係数は、どちらも 3, 6 と始まる。「最高次(4次)の係数から見て、3次の係数が 2 倍になっている」ということには、解析的な意味がある。同様に、どちらにおいても、2次の係数から見て、1次の係数は 3 小さい: これら二つの係数は、 S6(n) では 0, −3 で、 S7(n) では −1, −4 だが、前者は要するに「4次の因子に2次の項がない」という意味なので、印象に残りやすい。

§4. とはいえ、別に細かく覚えてなくても、こんなことは公式集を確認すれば済む話で、
  S5(n) + S7(n) = n2(n + 1)2(2n2 + 2n − 1)/12 + n2(n + 1)2(3n4 + 6n3 − n2 − 4n + 2)/24
を通分すると、
   = n2(n + 1)2(4n2 + 4n − 2)/24 + n2(n + 1)2(3n4 + 6n3 − n2 − 4n + 2)/24
   = n2(n + 1)2/24 × [(4n2 + 4n − 2) + (3n4 + 6n3 − n2 − 4n + 2)]
となって、この [ ] 内では、1次の項は +4n と −4n なので打ち消し合い、定数項も −2 と +2 が打ち消し合い、2次以上の項だけが残る; 実質 4n2 − n2 = 3n2 だけを計算すればいい。すなわち:
   = n2(n + 1)2/24 × (3n4 + 6n3 + 3n2)
3 を約分して n2 をくくり出すと:
   = n2(n + 1)2/8 × n2(n2 + 2n + 1) = n2(n + 1)2/8 × n2(n + 1)2
   = n4(n + 1)4/8 = 2 × n4(n + 1)4/16
   = 2 × [n(n + 1)/2]4 = 2N4

ここで N = n(n + 1)/2 = S1(n) である。 Faulhaber の法則 S5(n) + S7(n) = 2N4 の直接証明、あっさり完了!

S5(n) を通分(分子・分母を 2 倍)して、もともとの因子 2n2 + 2n − 1 が 4n2 + 4n − 2 になったとき、それが S7(n) の4次の因子と大部分、打ち消し合うということから、 S7(n) の4次の因子の末尾は −4n + 2 でなければならない。ところが前述のように、この4次の因子は 3n4 + 6n3 + Xn2 + (X−3)n + Y の形を持つのだから、 X−3 = −4 つまり X = −1 となるはずで、そして Y = 2 となるはずで、結局、
  3n4 + 6n3 − 1n2 − 4n + 2
となるはず。

〔注〕 そしてこの定数項が 2 だから、公式の分母は 12 でなく 24 になる。

S5(n) + S7(n) が簡単な形になる――というのは「マニアックな豆知識」かもしれないが、その豆知識を活用すると、 S5(n) の形から S7(n) を「逆算」できる。 Faulhaber の法則のおかげで S1(n) と S3(n) が容易にセットで覚えられるのと同様に、 S5(n) と S7(n) はセットで考えると便利かもしれない。 4n2 + 4n − 2 と打ち消し合って 3n4 + 6n3 + 3n3 が残るためには、そこに何があればいいか?という発想。

〔付記〕 「覚える・記憶に残る」ということは、ある意味、旅や探検の思い出のような「副産物」で、それ自体が目的ではない。何かが記憶に残るかどうかと無関係に、 Faulhaber の法則は美しいし、面白い。そもそも命は有限だから「記憶・思い出」を無限に保持できるわけではないが、だからといって、興味を感じることについて研究する楽しさが、消滅するわけでもないだろう。

§5. さて、 Faulhaber は「13乗和」から「17乗和」の一般公式と共に、次の具体例を記している。
  S13(4) = 113 + 213 + 313 + 413 = 6871 1380
  S14(4) = 114 + 214 + 314 + 414 = 2 7323 4810
  S15(4) = 115 + 215 + 315 + 415 = 10 8812 3500
  S16(4) = 116 + 216 + 316 + 416 = 43 3807 9554
  S17(4) = 117 + 217 + 317 + 417 = 173 0914 0420

これらの五つの数は大き過ぎて(千万~百億単位)、実感が湧きにくいが、 m = 16 のケース以外では末尾(最下位桁)が 0 であること、 m = 16 のケースだけは末尾が 4 であることが見て取れる。もっと小さい m で何が起きるか、実験してみる。
  S1(4) = 11 + 21 + 31 + 41 = 1 + 2 + 3 + 4 = 10
  S2(4) = 12 + 22 + 32 + 42 = 1 + 4 + 9 + 16 = 30
  S3(4) = 13 + 23 + 33 + 43 = 1 + 8 + 27 + 64 = 100
  S4(4) = 14 + 24 + 34 + 44 = 1 + 16 + 81 + 256 = 354
  S5(4) = 15 + 25 + 35 + 45 = 1 + 32 + 243 + 1024 = 1300

今度は m = 4 の場合だけ和の末尾が 4 になり、それ以外では末尾が 0 になった。

他の m の値の例: S6(4) = 4890。 S7(4) = 18700。 S8(4) = 72354。 S9(4) = 282340。 S10(4) = 1108650。 S11(4) = 4373500。 S12(4) = 17312754。

ちなみに S5(4) と S7(4) の和がちょうど 20000 で、 S3(4) = 100 の平方の 2 倍に等しい――というのが、既に証明した Faulhaber の法則の例。それはともかく、これらの数値実験から、次のことが予想されるであろう。

予想 Sm(4) の値は、大抵、末尾が 0 の数(つまり 10 の倍数)になる。ただし m が 4 の倍数のときは例外で、末尾が 4 になる。

ところで m が 1 以上のとき Sm(4) = 1m + 2m + 3m + 4m が偶数になるのは明らか。なぜなら、一方において、奇数 1 と 3 は m 乗しても奇数のままなので、 1m と 3m の和は、奇数と奇数の和で、偶数。他方において、偶数 2 と 4 は m 乗しても偶数のまま。一方と他方を総合すると、トータルでは三つの偶数を足し合わせることになり、結果はもちろん偶数。よって「大抵 10 の倍数になる」つまり「2 × 5 の倍数になる」という現象のうち、因子 2 の部分(要するに偶数になるということ)は、分かり切っている。問題の本質は「5 の倍数になる」ということにある(まぁ 10 の倍数は 5 の倍数に決まってるので、どっちでも同じようなもんだけど)

同様に「末尾が 4」つまり「10 で割って 4 余る」ということも、「偶数であることは当たり前」という前提を考慮すると、本質は「5 の倍数より 1 小さい」ということ、言い換えれば「5 で割って 4 余る」ということにある(これもまぁ 10 で割って 4 余るなら、 5 で割っても 4 余るに決まってるので、どっちでも同じようなもんだが)

例外もあるだろうけど、数論では「10 の倍数がどうこう」より「5 の倍数がどうこう」と考えた方が便利なことが多い。 10 は合成数だけど 5 は素数だから。複数の成分が合成されている数よりも、一つの成分だけを含む素数の方が、シンプルで扱いやすいのだ。しかも、ここでは四つの数を足すことを考えている。もし 0m から足し始めるとするなら(0m = 0 なので、そんな項はあってもなくても結果に影響しないけど)、五つの数の足し算であり、「5」というのが何らかのキーワードになっている可能性がある。

実際、このように考えると「予想」の半分は直ちに証明される。というのも、
  p が素数のとき、 k が p の倍数以外なら、常に kp−1 ≡ 1 (mod p)
という Fermat(フェルマ、フェルマー)の小定理を適用できるから。小定理で p = 5 とすると「p−1 乗」は「4乗」のことなので、
  14 ≡ 1 かつ 24 ≡ 1 かつ 34 ≡ 1 かつ 44 ≡ 1 (mod 5)
が成り立つ。ただし ≡ 1 (mod 5) という記号は「5 で割ると 1 余る」という意味。事実 14 = 1 も 24 = 16 も 34 = 81 も 44 = 256 も「5 で割ると 1 余る」数だ。

ゆえに、
  S4(4) = 14 + 24 + 34 + 44 ≡ 1 + 1 + 1 + 1 = 4 (mod 5)
は明白で、従ってまた、
  S8(4) = (14)2 + (24)2 + (34)2 + (44)2 ≡ 12 + 12 + 12 + 12 = 4 (mod 5)
  S12(4) = (14)3 + (24)3 + (34)3 + (44)3 ≡ 13 + 13 + 13 + 13 = 4 (mod 5)
等々となり、一般に m が 4 の倍数なら Sm(4) ≡ 4 (mod 5) となる。すなわち「予想」の半分は、証明されたのである。

§6. 上記のことは、一見たわいもない事柄のようだが、意外とインパクトがでかい。第一に、
  S1(n) = 1 + 2 + ··· + n = n(n + 1)/2
  S2(n) = 12 + 22 + ··· + n2 = n(n + 1)(2n + 1)/6
  S3(n) = 13 + 23 + ··· + n3 = n2(n + 1)2/4
  S4(n) = 14 + 24 + ··· + n4 = n(n + 1)(2n + 1)(3n2 + 3n − 1)/30
等々の公式は、どれも分子に n + 1 という因子を持っている。よって n = 4 を入れれば、分子は必ず 5 の倍数になる。右辺は分数の形ではあるが、左辺は整数の和なので、この分数は必ず約分されて整数になる。ということは、分子が 5 の倍数なら、その「5」という因子は、約分で消えない限り最後まで残って、結果は 5 の倍数になる(前記の数値例を見ても、事実、大抵そうなっている)。しかるに、今「m が 4 の倍数のときは Sm(4) が 5 の倍数にならない」ことを証明したのだから、論理的帰結として、「4乗和」「8乗和」「12乗和」などの公式では、必ず分子の 5 が約分で消える。従って、分母が因子 5 を持つ(分母が 5 の倍数である)。内容は単純で当たり前だが、その結果は重大で、一般公式の形についての「縛り」になっている――実際、「4乗和」の公式の分母 30 は 5 の倍数だ(論理的に、そうでなければならない)。

われわれは「16乗和」「20乗和」「24乗和」などの公式が、一体どんな形になるのか、よく知らないけど、それでも、「4の倍数」乗和の公式は分母が 5 の倍数になるであろう、と予言できる立場になったのである!

第二に、この「予想」は四つの数の和に基づく。四つ、という数値は、素数 p = 5 に対する p−1 = 4 だけど、 p = 5 という選択自体に特別な意味はない。他の素数、例えば p = 3 や p = 7 や p = 11 や p = 13 を選んで Sm(p−1) を考えても、 Fermat の小定理は有効だろう。そこから得られる同様の「縛り」を総合すると、 Sm(n) の一般公式の形(少なくとも分母の因子)について、かなり詳細な「予言」が可能になるかもしれない。この分母は Bernoulli 形式の最後の項の係数と関係していて、それは Bernoulli 数そのもの(または、それを m 倍して 2 で割ったもの)。一見たわいもない「予想」だが、多少なりとも「Bernoulli 数の振る舞い」という深遠な現象の核心に迫っている。

〔補足〕 事実、4 の倍数番目の Bernoulli 数は、 B4 = B8 = −1/30、 B12 = −691/2730 のように分母が 5 の倍数のようだ。それ以外の Bernoulli 数は、 B2 = 1/6、 B6 = 1/42、 B10 = 5/66 のように、分母が 5 の倍数以外のようだ。この種の性質をもっといろいろと正確に決定できるなら、 Bernoulli 数を求める高速なアルゴリズムにつながるかもしれない。

§7. 予想の残り半分の証明は、次の通り。 a が 5 の倍数以外なら、「曜日ばらばらの原理」によって、
  {1, 2, 3, 4} と {1a, 2a, 3a, 4a}
は、 mod 5 において、同一の集合だ。例えば a = 2 なら第二の集合は {2, 4, 6, 8} だが、 6 ≡ 1 かつ 8 ≡ 3 (mod 5) なので、第二の集合は、「第一の集合の各要素」と合同な要素を過不足なく含む。 a = 3 や a = 4 などでも結論は同じ。従って、
  1m + 2m + 3m + 4m ≡ (1a)m + (2a)m +(3a)m + (4a)m (mod 5)
が成り立つ――なぜなら、右辺の 4 項は、 mod 5 においては、左辺の 4 項(のそれぞれと合同な項)を並び替えただけなので。

上記の合同式を整理すると:
  1m + 2m + 3m + 4m ≡ 1mam + 2mam + 3mam + 4mam = (1m + 2m + 3m + 4m)am
  移項して (1m + 2m + 3m + 4m)am − (1m + 2m + 3m + 4m) ≡ 0
  ∴ (1m + 2m + 3m + 4m)(am − 1) ≡ 0 (mod 5)

このことから、何が言えるか? (1m + 2m + 3m + 4m) と (am − 1) の積が ≡ 0 (mod 5) であるから(そして 5 は素数であり、従って mod 5 の世界には零因子がないから)
  因子 1m + 2m + 3m + 4m または 因子 am − 1 の少なくとも一方は ≡ 0
(注: 「積 xy が 0 なら x か y の少なくとも一方は 0 でしょ、普通」という当たり前のことを言っている)。もし m が p−1 = 4 またはその倍数なら、 Fermat の小定理から am − 1 ≡ 1 − 1 ≡ 0 であり、確かに上記の通り。けれど、その情報はあまり役立たないし、 m が 4 の場合については、予想は既に証明済みでもある。問題は m が 4 の倍数以外のとき…。小定理は、
  m が 4 の倍数 ⇒ am ≡ 1 ⇒ am − 1 ≡ 0
を保証してくれるが、
  m が 4 の倍数以外 ⇒ am ≢ 1 ⇒ am − 1 ≢ 0  ★
を保証してくれるだろうか? もし仮に ★ の保証があるなら、そのときには、必然的に、
  もう一方の因子 1m + 2m + 3m + 4m ≡ 0 (mod 5)
となり、それは 1m + 2m + 3m + 4m が「5 で割って 0 余る数」要するに「5 の倍数」という意味なので、予想の証明が完成するのだが…?

★ は、「m が 4 の倍数以外なら am ≢ 1」ということ、つまり「a の位数が 4」ということ、要するに「a は原始根」ということを意味しているが、もちろん Fermat はそんな保証をしてくれない。原始根というのは、(一般には見つけるのに苦労するような)比較的まれな存在であり、「5 の倍数以外」という緩い条件で選んだ a が必ず原始根になる――なんて保証は、どこにもない。でも、原始根が存在すること自体は保証されている。そして a は任意に選択可能なパラメーターなのだから、この場合、単に最初から「mod 5 の原始根を一つ選んでそれを a とする」とすれば、全て解決。その設定なら ★ のロジックが成り立つ。話の出発点となっている「曜日ばらばらの原理」は、 5 の倍数以外の任意の a について成り立つので、もちろん a が原始根のときも成立する(a の設定に応じて、前述の「集合の要素の並び替え」が起きるが、集合の要素をどんな順序で並べようと同じ集合であることに変わりはないという意味において、並び替えのパラメーターは自由)。すなわち「予想」の証明が完成したのである。

§8. より一般的に、次の命題が成り立つ。

Rado の補題 p を素数とする。 Sm(p−1) の値は、大抵の場合 p の倍数になる。ただし m が p−1 の倍数の場合だけは例外で、そのときには Sm(p−1) の値は、 p の倍数より 1 小さくなる。

前節まででは p = 5 のケースを扱った。 p = 5 の場合、補題の内容は: 「Sm(4) は大抵 5 の倍数だが、 m が 4 の倍数のときだけは 5 の倍数より 1 小さくなる」。これについては、既に多くの数値例を挙げた(前節では「5 の倍数より 1 小さくなる」の代わりに「5 で割ると 4 余る」という捉え方をしたが、どっちでも同じ意味)。 S1(4) = 1 + 2 + 3 + 4 = 10 は 5 の倍数――という何げない事実も、この補題の現れ。もうちょっと素朴に言うと、「端から2項ずつペアにして足すと、どのペアも和は 5 なので、全体の和は 5 の倍数」ということだが、別の観点からすると、それと同じ結論が、一般の m 乗和について成り立つ(例外ケースを除く)。

p = 7 の場合、補題の内容は: 「Sm(6) は大抵 7 の倍数だが、 m が 6 の倍数のときだけは 7 の倍数より 1 小さくなる」。

本当だろうか?
  S1(6) = 1 + 2 + 3 + 4 + 5 + 6 = 21  確かに 7 の倍数
  S2(6) = 1 + 4 + 9 + 16 + 25 + 36 = 91  確かに 7 の倍数
  S3(6) = 1 + 8 + 27 + 64 + 125 + 216 = 441  確かに 7 の倍数

どうやら本当らしい。このうち S2(6) = 91 については、別の文脈(三角数の四角すい数)で既に言及した。 S3(6) = 441 は S1(6) = 21 = 3⋅7 の平方なので、もちろん 7 の倍数(それどころか 72 の倍数)。計算を続けると Sm(6) の値は、 m = 4, 5 に対しても 7 の倍数になること、 m = 6 だと例外ケースで 7 の倍数より 1 小さくなること、そして m = 7, 8, ··· に対しては再び 7 の倍数になることを確認できる。

さらに別の例として p = 11 の場合: 「Sm(10) は大抵 11 の倍数だが、例外として、うんぬん」。具体的には S1(10) = 55 や S2(10) = 385 など大抵の Sm(10) は 11 の倍数。しかし S10(10) や S20(10) や S30(10) などは例外で、 11 の倍数より 1 小さくなる。

具体例を調べると、補題の正しさが何となく実感される。感覚がつかめたところで、論理的な証明を…

証明 とりあえず p を 2 以外の素数とする。前節までの p = 5 の例と同様に証明を進める。

g を mod p の原始根とすると、 {1, 2, ···, p−1} と {1g, 2g, ···, (p−1)g} は mod p では同じ集合。ゆえに:
  Sm(p−1) = 1m + 2m + ··· + (p−1)m ≡ (1g)m + (2g)m + ··· + ((p−1)g)m
  つまり 1m + 2m + ··· + (p−1)m ≡ (1m + 2m + ··· + (p−1)m)gm
  移項して (1m + 2m + ··· + (p−1)m)(gm − 1) ≡ 0

従って、因子 1m + 2m + ··· + (p−1)m または因子 gm − 1 の少なくとも一方は、必ず ≡ 0 になる。 m が p−1 の倍数ではないとすると、 gm ≢ 1 なので(なぜなら g は原始根なので m が p−1 の倍数のときに限って ≡ 1 になる)、 gm − 1 ≢ 0。従って、もう一方の因子が ≡ 0 になることが必要。要するに、
  m が p−1 の倍数ではない ⇒ Sm(p−1) ≡ 0 (mod p)
となる。これで、例外ケース以外の場合が証明された。

例外ケースについて。もし m = p−1 なら、 Fermat の小定理から、
  Sm(p−1) = 1m + 2m + ··· + (p−1)m
の右辺各項は ≡ 1 (mod p) であり、項の数は p−1 なので、上記の右辺は 1 を p−1 個、足し合わせたもの(要するに p−1)と合同。同様に、もし m が p−1 の倍数なら、 m = (p−1) × a とすると、上記の右辺は 1a を p−1 個、足し合わせたものと合同で、結論は同じ。すなわち、
  m が p−1 の倍数 ⇒ Sm(p−1) ≡ p−1 (mod p)
が成り立つ。つまり、例外ケースについての命題の主張も正しい。

最後に p = 2 の場合について。このとき、任意の m は、もちろん p−1 = 1 の倍数だから、補題が正しいとすれば「例外ケース」しか存在せず、 m の値にかかわらず、和 Sm(p−1) = Sm(1) は、 p = 2 の倍数より 1 小さくなる。それを証明することは易しい。実際、
  Sm(1) = 1m = 1
であり、この 1 という値は、もちろん「2 の倍数より 1 小さい」。∎

§9. ここまでは散文的な書き方をしてきたが、もう少し記号的に表現した方が便利なこともあるだろう。「p の倍数である」ということは、記号的には ≡ 0 (mod p) であり、「p の倍数より 1 小さい」ということは、記号的には ≡ −1 (mod p) である。「b は a の倍数である」ということ、言い換えれば「b は a で割り切れる」「a は b の約数である」「a は b を割り切る」ということは、記号的には a∣b で表される。

Rado の補題は、 (p−1)∣m が真か偽かに応じて Sm(p−1) は ≡ −1 か ≡ 0 (mod p) ――と要約される。

それをさらに記号化するため、 Rado は次のような「関数」を定義した。
  定義 εm(p) は、もし (p−1)∣m が真なら「1」を表し、もし (p−1)∣m が偽なら「0」を表す。

〔補足〕 ギリシャ文字 ε の真意は不明だが、 Kronecker の delta の変種のようなものなので、 δ の次の文字を使ったのかもしれない。

この定義によれば、補題の内容は Sm(p−1) ≡ −εm(p) (mod p) と要約される。この表記法は Hardy–Wright §7.9 以下で、そのまま引用されていて、この文脈においてはそれなりに標準的なのかもしれない。しかし定義は明確でも、必ずしも直観的に最も分かりやすい表現法とは言えないであろう。こういうとき Knuth は、 ε のような「ヘルパー関数」を定義・介在させる代わりに、次のような汎用的表記法を使うことがある。
  Sm(p−1) ≡ −[(p−1)∣m] (mod p)

この場合の角かっこ [ ] は、その内側に書かれている式が true なら 1 を返し、 false なら 0 を返す。「式の値」を 1 or 0 に変換――というのは、プログラミングではありふれた発想(あるいは言語仕様)だ。参考までに、上記の右辺をC言語で書けば、
  −(int)(m%(p-1)==0)
というわけ。少なくともプログラマーにとっては、まあまあの可読性だろう。オーバーヘッド、ゼロ。これを、
  −epsilon(m, p)
のように書くのは、可読性の点で「すっきり」はしているけど、 epsilon の定義を覚えて思い出す手間が生じ、関数呼び出しのオーバーヘッドが増え、引数の順序をうっかり間違うリスクも生じる。どっちも一長一短というところか。

いずれにしても、要点は:

✿

この補題は、 Bernoulli 数についての興味深い定理の証明の土台となり、さまざまな話題へと発展していく。(下に続く)

✿ ✿ ✿


2025-01-19 12 + 22 + 32 + 42 + 52 も 5 の倍数 v. シュタウトの定理

#遊びの数論 #べき和 #(37) #ベルヌーイ数

12 + 22 + 32 + 42 = 1 + 4 + 9 + 16 = 30 は 5 の倍数。より一般的に A = 1m + 2m + 3m + 4m は大抵、5 の倍数。例外として、 m が 4 の倍数のときに限って、和 A は 5 の倍数より 1 小さい数になる。

もう一つ先の数まで足して B = 1m + 2m + 3m + 4m + 5m を考えても、この性質は変わらない。 5m はもちろん 5 の倍数なので、 A が 5 の倍数なら当然 B も 5 の倍数になるし、例外ケースとして A が 5 の倍数でないなら、 B も 5 の倍数ではない。例えば、
  12 + 22 + 32 + 42 + 52 = 30 + 25 = 55
は 5 の倍数だが、
  14 + 24 + 34 + 44 = 1 + 8 + 81 + 256 = 354
  14 + 24 + 34 + 44 + 54 = 354 + 625 = 979
は、どちらも 5 の倍数より 1 小さい。

✿

§10. 最近(2022年ごろ)、 Bernoulli 数 B1 の定義は 1/2 と −1/2 のどちらが良いかということが、ホットな話題となった。20世紀には B1 = −1/2 という定義が多かったようだが、 Peter Luschny は 2004年ごろ B1 = +1/2 と定義するべきだと Knuth に訴え、2010年代には The Bernoulli Manifesto というウェブページを作って、その論拠をまとめた。 Knuth は当初、定義変更について全く乗り気でなかったが、最終的にはこの主張に同意、2020年代に著書を大幅に書き換え、定義 −1/2 を「悪い」とまで言うようになった。

定義の違いが、具体的にどんな影響を及ぼすか。身近なところでは、 B1 = −1/2 と B1 = +1/2 のどちらの定義を採用するかによって、全く同じ形の式が、
  1m + 2m + ··· + (n−1)m
という和を表すのか、それとも、
  1m + 2m + ··· + nm
という和を表すのか、という違いが生じる。「定義」は約束事なので、首尾一貫して同じ定義を使う限り、論理的にはどちらでも構わない。

本家本元の Bernoulli 自身は、遺作の中で B1 = 1/2 を使っている。歴史的な事実関係だけを言うなら、 Knuth は Bernoulli 自身の本来の定義を復活させた、ということになる。文献によって異なる二つの定義の存在は、多少の混乱の原因になるかもしれないが、 Knuth は計算機科学の分野では影響力の強い存在で、今後 B1 = 1/2 がますます一般的になっていく可能性もある。このメモや他のメモでも、 Knuth と同じ B1 = 1/2 の定義を採用している。

§11. 例として、 Bernoulli ご自慢の10乗和の公式(11次式)。 Bernoulli 自身は、次のような計算法を記した:
  S10(n) = (1/11)n11 + (1/2)n10 + (10/2)(1/6)n9 + (10⋅9⋅8/2⋅3⋅4)(−1/30)n7 + (10⋅9⋅8⋅7⋅6/2⋅3⋅4⋅5⋅6)(1/42)n5 + (10⋅9⋅8⋅7⋅6⋅5⋅4/2⋅3⋅4⋅5⋅6⋅7⋅8)(−1/30)n3 + (10⋅9⋅8⋅7⋅6⋅5⋅4⋅3⋅2/2⋅3⋅4⋅5⋅6⋅7⋅8⋅9⋅10)(5/66)n
   = (1/11)n11 + (1/2)n10 + (10↓1/2↑1)(1/6)n9 + (10↓3/2↑3)(−1/30)n7 + (10↓5/2↑5)(1/42)n5 + (10↓7/2↑7)(−1/30)n3 + (10↓9/2↑9)(5/66)n

丸かっこ内の 1/2, 1/6, −1/30, 1/42, −1/30, 5/66 が Bernoulli 数で、順に B1, B2, B4, B6, B8, B10 に当たる。微妙にゴチャゴチャしてるが、意味は明確。 不規則な Bernoulli 数を別にすると(仮に ○ で表すと)、次のようにシンプルで規則的なパターンになっている。
  (1/11)n11 + (○)n10 + (10↓1/2↑1)(○)n9 + (10↓3/2↑3)(○)n7 + (10↓5/2↑5)(○)n5 + (10↓7/2↑7)(○)n3 + (10↓9/2↑9)(○)n

現代の表記法(総和記号、二項係数)を使って、これを簡潔に整理する方法は、複数ある。多分、最もすっきりした書き方は:
  S10(n) = (1/11) { from k=0 to 10 } (11 C k)⋅(Bk)n11−k  《あ》

ただし B0 = 1 として、 B3 以降の奇数番目の Bk は = 0 とする。ほんの少し違う書き方として、「総和全体」に掛かってる「1/11 倍」を「総和記号の内側」に入れた形は下記の通り―― (1/11)(a + b + c) = a/11 + b/11 + c/11 みたいな発想。
  S10(n) = { from k=0 to 10 } (11 C k)⋅(Bk)(n11−k/11)  《い》
   = 1⋅(1)(n11/11) + 11⋅(1/2)(n10/11) + 55⋅(1/6)(n9/11) + 330⋅(−1/30)(n7/11) + 462⋅(1/42)(n5/11) + 165⋅(−1/30)(n3/11) + 11⋅(5/66)(n/11)

各項の先頭にある係数、
  1, 11, 55, 165*, 330, 462*; 462, 330*, 165, 55*, 11, 1*
は、11乗の二項係数。右辺では *印の係数は、省略されている。というのも、 B3 以降の奇数番目の Bernoulli 数は 0 なので、 k = 3, 5, 7, 9 に対応する項は、消滅。例えば、8次の項を明示的に書けば 165⋅(0)n8/11 だが、どうせ項の値は 0 なので、有っても無くても同じこと。

ちなみに、もし B1 の定義を 1/2 から −1/2 に変えると、右辺第2項が、
  11⋅(1/2)n10/11 = (1/2)n10 から 11⋅(−1/2)n10/11 = (−1/2)n10 に
変わり、その項の値が(従って項の和である式の値が)ちょうど n10 だけ小さくなる。上記の例は、そのままだと、
  S10(n) = 110 + 210 + ··· + (n−1)10 + n10
の値に等しいのだが、もし仮に B1 = −1/2 とすると値がちょうど n10 小さくなるのだから、その場合には S10(n) の意味が変わり、
  1項少ない和 110 + 210 + ··· + (n−1)10
を表す式になる。ここではその別定義を使わないで、 B1 = +1/2 としていることを再度、強調しておく。

〔注〕 現代的表記として、11乗の二項係数の代わりに、10乗の二項係数を使う方法もある(後述)。

§12. p を素数として、 1 から始めて最初の p 個の整数の10乗和がどんな性質を持つか、考えてみたい。

前回証明したように、 1m + 2m + 3m + 4m は大抵 5 の倍数になる(m が 4 の倍数の場合だけは例外で、そのときには、この和は 5 の倍数より 1 小さくなる)。 m = 10 は 4 の倍数ではないので、例外ケースではなく、
  110 + 210 + 310 + 410 = 1108650
は 5 の倍数。従って、
  110 + 210 + 310 + 410 + 510 = 10874275
も 5 の倍数。つまり p = 5 の場合、「最初の p 個の整数の10乗和」は p の倍数になる。

p = 7 や p = 13 の場合も全く同様で、「最初の 7 個の整数の10乗和」、
  110 + 210 + ··· + 710 = 353815700
は 7 の倍数であり、「最初の 13 個の整数の10乗和」、
  110 + 210 + ··· + 1310 = 240627622599
は 13 の倍数。この現象が成り立つ理由は単純で、「例外ケース」に該当しないから。すなわち m = 10 が、 p−1 つまり 6 ないし 12 の倍数ではないから。言い換えると、 p−1 が 10 を割り切らないから。 10 を割り切る最大の数はもちろん 10 自身なので、 p がさらに大きくなった場合(p = 17, 19, 23 など)、 p−1 が 10 を割り切ることは絶対に不可能であり、その結果、十分大きい p に対して、
  110 + 210 + ··· + p10
は、必ず p で割り切れる。

〔例〕 p = 31 の場合、
  110 + 210 + ··· + 3110 = 2741681213994576
は 31 の倍数。 p−1 = 30 が指数 m = 10 を割り切らないので、例外ケースには該当しない。割る数・割られる数をあべこべにすると m = 10 は p−1 = 30 を割り切るが、それは無関係。あべこべに考えてはいけない!

p = 3 の場合、 m = 10 は p−1 = 2 の倍数なので「例外ケース」となり、
  110 + 210 + 310 = 60074
は 3 では割り切れない。 3 の倍数より 1 小さい数になる。この場合、もし +1 を補正して、
  110 + 210 + 310 + 1 = 60075
という数を考えるなら、それは 3 で割り切れる。同様に p = 2 の場合、 m = 10 はもちろん p−1 = 1 の倍数なので、
  110 + 210 = 1025
は 2 では割り切れないが、もし +1 を補正して、
  110 + 210 + 1 = 1026
を考えるなら、それは 2 で割り切れる。最後に p = 11 の場合にも、 m = 10 は p−1 = 10 の倍数なので、
  110 + 210 + ··· + 1110 = 40851766526
は 11 では割り切れないが、もし +1 を補正して、
  110 + 210 + ··· + 1110 + 1 = 40851766527
を考えるなら、それは 11 で割り切れる。

要するに、 p−1 が m = 10 を割り切るとき――言い換えれば、 m = 10 の約数 1, 2, 5, 10 のいずれかより 1 大きい数を素数 p として選んだときに――「例外ケース」となる(5 + 1 は素数でないので、素数 p としては選択不可)。和 Sm(p) は、例外的な素数 p では割り切れないが、その場合でも +1 を補正すれば p で割り切れる整数になる。一般に、与えられた整数 m の約数は有限個なので、「例外ケース」は有限個。「例外ケース」以外の任意の(無限種類の)素数 p に対しては、単純に、
  Sm(p) = 1m + 2m + ··· + pm
が p の倍数となる。

1 から p までの m 乗和 m を正の整数、 p を素数とする。 p 個の整数をそれぞれ m 乗して足し合わせた和、
  1m + 2m + ··· + pm
は、原則として p の倍数。例外として、 p−1 が 指数 m を割り切るときには上記の和は p の倍数にならないが、そのときには、
  1m + 2m + ··· + pm + 1
が p の倍数となる。

§13. 具体例として、 m = 10 の場合について、前記 Bernoulli 形式・現代版《い》と組み合わせると、任意の素数 p について、
  S10(p) + E  《う》
   = 1⋅(1)(n11/11) + 11⋅(1/2)(n10/11) + 55⋅(1/6)(n9/11) + 330⋅(−1/30)(n7/11) + 462⋅(1/42)(n5/11) + 165⋅(−1/30)(n3/11) + 11⋅(5/66)(n/11) + E
は p で割り切れる。ここで E は 原則 E = 0 で、有っても無くても同じ。例外ケースに該当する p = 2, 3, 11 の場合にのみ E = 1 となる(例外ケースは、 p − 1 が m = 10 を割り切る場合: p − 1 = 1, 2, 10)。文字 E の代わりに [(p−1)∣m] とか εm(p) のような記号が書かれることもあるが(§9)、ここでは簡略に E としておく。例外ケースは、全体から見ればごくまれ。しかしその少数の例外の存在が、実は大きなインパクトを持つ。すなわち、
  Bernoulli 数 B10 = 5/66
に、例外ケースの素数 p = 2, 3, 11 のそれぞれの逆数を足したものは、整数になる:
  5/66 + 1/2 + 1/3 + 1/11 = 5/66 + 33/66 + 22/66 + 6/66 = 66/66 = 1

一般に m が 2 以上の任意の偶数のとき(m = 2, 4, 6 など)、または m = 1 のとき、次の関係が成り立つ:
  Bm + { for p−1∣m }(1/p) = Bm + { for p }(E/p) = 整数  《え》
ここで、一つ目の総和記号は、 p−1 が m の約数であるような全ての素数 p にわたる。二つ目の総和記号は、全ての素数 p にわたる(ただし p−1 が m の約数であるときだけ E = 1 なので、二つ目の総和は、一つ目の総和と全く同じ意味を持つ)。要するに、例外ケースの全素数について、それらの逆数を Bm に足す。

そのことが、どう重大なのか?

性質《え》は、「von Staudt–Clausen の定理」「von Staudt の定理」などと呼ばれる。1840年に von Staudt(フォン・シュタウト) と Clausen(クラウセン) の二人が独立にこれを発見し、 1934年に Rado が別証明を公表。この定理は、それ自体として面白いだけでなく、さまざまな応用を秘めていて、小さい Bernoulli 数を素早く導出するための、便利なショートカットを与えてくれる。一見「不規則」に見える Bernoulli 数の、隠れた規則性に光を当てる優れ物。以下では、この定理を証明する!

〔メモ〕 Clausen はデンマークの研究者。 Fermat 数 F6 = 264 + 1 の素因数 274177 を発見し F6 が素数でないことを示した偉業でも、知られる(1855年ごろ)。この分解は、1880年に Landry によっても再発見された。 von Staudt はドイツの学者。

§14. 《う》の S10(p) + E は必ず p で割り切れるのだから、右辺を p で割った数(便宜上、項を少し並び替え、末尾の 2 項を先頭に書く)、
  5/66 + E/p + 1⋅(1)p10/11 + 11⋅(1/2)p9/11 + 55⋅(1/6)p8/11
   + 330⋅(−1/30)p6/11 + 462⋅(1/42)p4/11 + 165⋅(−1/30)p2/11  《お》
は、整数になる。あるいは、同じことだが、 Hardy–Wright 風に言うなら ≡ 0 (mod 1) となる。つまり「1 の倍数」。この p は任意の素数。例外的な素数・それ以外の素数のどちらを p としてもいい。第2項 E/p によって例外ケースを補正しているので、例外ケースも含めて、この式の値は整数。

注目すべき事実(単純だが、気が付きにくい!)として、 p としてどんな素数を選んでも、最初の2項、
  5/66 + E/p
を通分・計算して(可能なら)約分した分数の分母は、決して p では割り切れない。この事実は、 p が例外的な素数 2, 3, 11 のどれとも異なる場合には、一目瞭然だろう。その場合 E = 0 なので、上記の和は 5/66 自身に他ならず、その分母 66 = 2⋅3⋅11 は、もちろん 2, 3, 11 以外の p では割り切れない。問題は p が 2 or 3 or 11 の場合。そのとき、もしも和が 5/66 のままなら、その分母 66 は p で割り切れるところだが、実際にはこれらのケースでは E = 1 なので、次のような分数計算になり、約分が起きて、分母が小さくなる。

p = 2 のとき:
  5/66 + 1/2 = 5/66 + 33/66 = 38/66 = 19/33 分母 33 は p = 2 で割り切れない

p = 3 のとき:
  5/66 + 1/3 = 5/66 + 22/66 = 27/66 = 9/22 分母 22 は p = 3 で割り切れない

p = 11 のとき:
  5/66 + 1/11 = 5/66 + 6/66 = 11/66 = 1/6 分母 6 は p = 11 で割り切れない

この現象は、単純ではない。例えば 5/66 の代わりに 5/33 を考えてみると、 p = 3 のとき 5/33 + 1/3 = 16/33 の分母 33 は p で割り切れるし、 p = 11 のとき 5/33 + 1/11 = 8/33 の分母 33 も p で割り切れる。「なぜどんな素数 p に対しても、和の分母が p で割り切れないと言い切れるのか?」―― Bernoulli 数の本質と関係ありそう。

以下で「分数」というのは、分子・分母がどちらも整数の既約分数を指す。「分数」として扱う場合(特に「分母」を考える場合)、値がちょうど整数の場合には、それを「分母 1 の分数」と見なすことにする。

観察 p, q を相異なる素数とする。分数 a/b の分母 b が p で割り切れないとき、分数 a/b と分数 1/q の和の分母も p で割り切れない。

〔証明〕 a/b + 1/q の分母は bq か、または(約分が可能なら)その約数。仮定により b は素因子 p を持たず、 q は p と異なる素数なので、 bq またはその約数は、 p では割り切れない。∎

上記の例では、分数 5/66 + 1/2 の分母は 2 で割り切れないのだから、分数 (5/66 + 1/2) + 1/3 の分母も 2 で割り切れず、従って分数 X = (5/66 + 1/2 + 1/3) + 1/11 の分母も 2 で割り切れない。足し算の順序を変えて同様に考えると、 X と等しい分数 (5/66 + 1/3 + 1/2) + 1/11 の分母は 3 で割り切れず、 X と等しい分数 (5/66 + 1/11 + 1/2) + 1/3 の分母も、 11 で割り切れない。 p がそれ以外の素数のとき X の分母が p で割り切れないことは、言うまでもない。要するに X の分母は、いかなる素数でも割り切れない。これは X の分母が一つの素因子も持たないこと、つまり分母が 1 であること、要するに X が整数であることを意味する。

結局、「どんな素数 p に対しても、 5/66 + E/p の分母は p で割り切れない」という事実は、 X = 5/66 + ∑ (E/p) が整数になることを含意している(この ∑ の意味は《え》の通り)。具体例 m = 10 については、実際に X が整数になることを直接計算で確かめられるけど、一般の m について「どんな素数 p に対しても Bm + E/p の分母が p で割り切れない」ということを証明できれば、上記の理由から、 Bm + ∑ (E/p) が整数になること(von Staudt–Clausen の定理)が示される。

§15. 証明のアイデア。「整数から分数 a/b を引き算した分数」も分母が b だ、ということは、明らかだろう。よって「分数 Bm + E/p の分母が p で割り切れない」ことを示す代わりに、「整数からその分数を引き算した結果の分母が p で割り切れない」ことを示してもいい。

例えば、前記の式《お》について、 Bernoulli 数を B10 などの記号で表すとともに、第3項以降を総和記号で表現すると:
  B10 + E/p + { from k=0 to 8 }(11 C k)⋅(Bk)p10−k/11  《か》
これが整数になることは、分かっている。よって、最初の 2 項の和 B10 + E/p の分母が p で割り切れないことを言う代わりに、(第3項の)総和の分母が p で割り切れないことを示してもいい。なぜなら、
  B10 + E/p = 整数 − 総和
において、左辺の分母と右辺の分母は等しい。

どうすれば、総和の分母が p で割り切れないことを示せるか?

もし「総和を構成するどの項の分母も p で割り切れない」ことを示せれば、総和の分母が p で割り切れないことも示される!

〔理由〕 「分母が素因子 p を含まない分数」たちを幾つ足し合わせても、「どの分母にも、もともと素因子 p が無い」のだから、途中計算の通分によって分母に素因子 p が生じる可能性は無く、和の分母は素因子 p を含み得ない。

「分数計算のどの項の分母も、どんな素数 p でも割り切れない」という可能性は、一見、直観に反している。分数があるからには分母があって、分母があるからには、当然、分母の素因子があるはずでは…。しかしこの場合の分数計算は、分子に変数 p の累乗を含んでいる。例えば、
  462⋅(1/42)p4/11 = 462p4/(42⋅11)
という項の分母は、見かけ上 42 × 11 で、 p = 2, 3, 7, 11 のどれでも割り切れそうにも思えるけど、 p がそれらの素数なら、分子の p4 の作用で、該当する素因子は約分され、分母から消滅(この場合 462/(42⋅11) = 1 でもあり、約分すれば、そもそも分母は 1 だ)。従って、それらの p で、分母を割り切ることはできない!

一般に、分子が p4, p5 などの因子を含むとき、分母が p で割り切れるためには、「約分」による「分数のリストラ」の後で、分母に因子 p が最低 1 個、残る必要がある。それには、分母が十分にたくさんの素因子 p ――例えば p6 など――を含んでいる必要がある。少なくともこの B10 の例では、分母に含まれ得る数値は比較的シンプルで、同じ因数を何重にも含んでいそうにない。

B12, B14, B16 等々がこの先どんな挙動を示すのか、まだ分からないけど、コンセプト的には、次のような論法が成り立つ可能性がある。

すなわち von Staudt–Clausen の定理が仮に正しいとすると、《え》によって、
  整数から Bm を引いた結果の、端数のような分数 ∑ (E/p)
は、相異なる幾つかの(c 個としよう)素数の逆数の和に等しい(端数といっても、この和は 1 以上かもしれないが、残りの部分は整数なので、この分数の値によって Bm の分母が決まることに変わりはない)。それは 1/p1 + 1/p2 + ··· + 1/pc の形なので、その和の分母――言い換えると、通分されたBm の分母(どちらの分母も等しい)――は p1p2···pc で、同じ素因子を二重・三重には含まない。要するに、平方因子を持たない(=平方数で割り切れない。同じ素数で2回は割り切れない)。

すると、どうなるか?

再び B10 の例《か》で考えると、総和の部分は、
   { from k=0 to 8 }(11 C k)⋅(Bk)p10−k/11
であり、大筋において、分母の素因子の発生源は B8 以下の Bernoulli 数の分母だ。

すると…

「小さい偶数の番号 m−2 (例えば 8)以下の Bernoulli 数について定理が正しいなら(その結果として Bm−2 などが分母に平方因子を持たないなら)、その次の偶数の番号 Bm (例えば 10)についても定理は正しい」――という帰納法が成り立つかも!

§16. もう少し具体的に考えてみる。例えば k = 4 のとき、上記の二項係数は、
  (11 C 4) = 11⋅10⋅9⋅8/4!
だが、そのとき係数の後ろの方には p6/11 があるので、分子の「11」を約分して、代わりに、
  (10 C 4) = 10⋅9⋅8⋅7/4!
を使うと、後ろにあった分母の「11」は約分されて消える。ただし、二項係数をいじった副作用で分子に「7」が追加されたので、それをキャンセルするため後ろの分母を「7」に置き換え p6/7 とする必要がある。全体としての値はもちろん同じだが、これによって見かけ上の分母が「11」から「7」に減る。分母が小さければ小さいほど、分母が何かで割り切れる可能性が制限され、証明の上で有利。同様の整理を各項で行うと:
   { from k=0 to 8 }(11 C k)⋅(Bk)p10−k/11 = { from k=0 to 8 }(10 C k)⋅(Bk)p10−k/(11 − k)
分子の p を一つだけ前に移動させると(この変形の意図は、すぐ明らかになる):
   = { from k=0 to 8 }(10 C k)⋅(pBk)p9−k/(11 − k)

任意の素数 p について、この総和のどの項の分母も p で割り切れないことを示したいのであった(これは約分前の「見かけ上の分母」の話ではなく、「約分後に残る分母」の話だ)。 B8 までの Bernoulli 数の分母 1, 2, 6; 30, 42, 30 は平方因子を持たない。つまり、上の総和に含まれる Bk の分母は、どの数も平方因子を持たない。よって Bk の分母に素因子 p があるとしても一つだけで、分子を p 倍した pBk では、 Bk の分母の素因子 p は、存在するとしても、約分され消滅。ゆえに pBk を一つの分数にまとめた場合、その分母は p で割り切れない。一方、その手前にある二項係数は整数なので、その分母 1 は、やはり p では割り切れない。最後に、後ろにある分数 p9−k/(11 − k) だが、その分母が p で割り切れるためには、まず約分によって分子の p9−k が消える必要がある。つまり、 11 − k が 9−k を超える個数の素因子 p を含む必要がある。 k が 0, 1, 2 などの小さい数のとき、それが無理なことは明白(11 程度の数が、素数の7乗・8乗などを因子とするわけない)。可能性があるとすれば k = 8 の瞬間だが、そのとき 11 − k = 3 であり、それが 9−k = 1 を上回る個数の素因子(つまり素数の2乗以上の因子)を含むのは、やはり無理。だって素数の2乗は、最小でも 22 = 4。

以上をまとめると、この総和の各項のどの部分にも、「分母が p で割り切れるようになる余地」は全くない!

〔補足〕 二項係数をいじって、見かけ上の分母を 11 から 11 − k に減らしておいたことのメリット。分母が 11 のままだったら、その数は「サイズ的に」素数の平方 22, 32 を因子として含み得る。「11」という具体的な数を扱っているとき、それが平方因子を持たないことは明らかだが、一般の m について扱う場合、細かく因子を分析するのは困難で、大きさに関する不等式に帰着させた方が良いだろう。

§17. 前節の議論は m = 10 という一つの例に関するものだが、全く同様にして、一般の m についての証明を行うことができる。

今、 m を 4 以上の任意の偶数とする。 m = 10 の場合の《か》、
  B10 + E/p + { from k=0 to 8 }(11 C k)⋅(Bk)p10−k/11
に当たる式の一般形は:
  Bm + E/p + { from k=0 to m−2 }(m+1 C k)⋅(Bk)pm−k/(m+1)  《き》

示したいのは、総和記号内のどの項の分母も p で割り切れないこと。二項係数の分子の先頭にある m+1 と、各項の末尾にある分母 m+1 を約分して、
  (m C k)⋅(Bk)pm−k/(m+1−k) = (m C k)⋅(pBk)pm−1−k/(m+1−k)  《く》
を得る。因子 p を一つだけ前に移動するのは、前節と同様。

〔注〕 分母に m+1−k が生じるのは、二項係数の分子を次のように変更したため(前節の具体例参照)。
  旧 m+1 から m+1−k+1 = m+2−k まで下る k 項の積
  新 一つずらして m から m+1−k まで下る k 項の積

二項係数は整数なので、分母に寄与しない。帰納法の仮定により Bk の分母は平方因子を持たず、よって pBk の分母は p で割り切れない(この主張は、 k が 3 以上の奇数の場合の pBk = 0 = 0/1 についても真)。分数 pm−1−k/(m+1−k) の分母が p で割り切れるためには、見かけ上の分母 m+1−k が、因子 p を m−1−k 個より多く(つまり m−k 個以上)含まねばならず、そのためには、
  不等式 m+1−k ≥ pm−k
が成り立つ必要がある。 k の範囲は 0 から m−2 なので、不等式の右辺は、最小でも k = m−2 のときの pm−(m−2) = p2 ≥ 22 = 4 だが、そのとき不等式の左辺は m+1−(m−2) = 3 なので、この不等式は成り立たない。もし k を減らすと、 k が 1 小さくなるごとに、右辺の値は p 倍(最低でも 2 倍)されるが、左辺の値は 1 ずつしか増えないので、ますます右辺は左辺より大きくなり、この不等式は不成立。結局、総和記号内のどの項の分母も、 p で割り切れない。これが示されるべき事柄だった。

最後に m = 1 のとき、その約数は 1 だけなので、条件 (p−1)∣m を満たす素数は p = 2 のみ。よって、定理が正しければ、
  B1 + 1/2 = 整数
となるはずだが、事実その通り(B1 = 1/2 と定義するにせよ −1/2 と定義するにせよ)。 m = 2 のとき、その約数は 1, 2 なので、条件 (p−1)∣m を満たす素数は p = 2, 3。よって、定理が正しければ、
  B2 + 1/2 + 1/3 = B2 + 5/6 = 整数
となるはずだが、事実その通り(B2 = 1/6)。これで帰納法の仮定が正しいことが示され、定理の証明が完了した。∎

〔注〕 この定理は、 3 以上の奇数 m に対しては、有効でない。 m = 0 の場合にも有効でない。 von Staudt–Clausen の定理は、 Bernoulli 数の(整数未満の)端数を特徴付けるもの。 B0 = 1 とか B3 = B5 = B7 = 0 とかの、もともと端数がない分かり切った値は、まぁどうでもいいだろう。

§18. Bernoulli 形式のべき和の、もう一つの現代的表記。
  S10(n) = (1/11)n11 + (1/2)n10 + (10/2)(1/6)n9 + (10⋅9⋅8/2⋅3⋅4)(−1/30)n7 + ···
のような式は、
   = (1/11)n11 + (1/2)n10 + (10/2!)(1/6)n9 + (10⋅9⋅8/4!)(−1/30)n7 + ···
なので、その観点では、第3項以降の係数の「分子の因子」が、「分母の因子」より 1 個多い(例: 10/2! の分子は 10 一つだが、分母は 2⋅1 の二つ)。二項係数を使った現代的表記に変換するには、分子の因子を 1 個増やす必要がある。最も簡単なのは、分子の因子を一つ上の 11 から始めて(つまり 11 倍して)、 11⋅10/2! とか 11⋅10⋅9⋅8/4! として、その代わり全体を 11 で割ってやること。最初の《い》、
  S10(n) = { from k=0 to 10 } (11 C k)⋅(Bk)(n11−k/11)
は、その書き方。この場合、第1項(k = 0)の二項係数は 1 で、そこにはもともと 1/11 があるので、つじつまが合うし、第2項(k = 1)の二項係数 11 も、付け足した 1/11 により消えるので、つじつまが合う。

しかし分子に 11 を増やして、後から 11 で割るのは、無駄な遠回りとも思える。代わりに10次の二項係数を使って、 10/2! を 10⋅9/2! にして 9 で割り、 10⋅9⋅8/4! を 10⋅9⋅8⋅7/4! にして 7 で割り··· というふうに書くこともできる。その方が分子を少し小さくできる。その代わり、ある項は 9 で割り、次の項は 7 で割り··· といったことになり、全体を統一的に 11 で割ればいい《い》と比べ、式がほんの少し複雑に:
  S10(n) = { from k=0 to 10 } (10 C k)⋅(Bk)n11−k/(11−k)
この場合も、第1項(k = 0)の二項係数は 1 なので値に影響せず、第2項(k = 1)の二項係数 10 も 1/(11−k) によって消えるので、つじつまは合う。

一般の m 乗和の場合、一つ目の書き方だと、
  Sm(n) = { from k=0 to m } (m+1 C k)⋅(Bk)nm+1−k/(m+1)  《け》
となり、二つ目の書き方だと、
  Sm(n) = { from k=0 to m } (m C k)⋅(Bk)nm+1−k/(m+1−k)  《こ》
となる。前者なら 1/(m+1) をくくり出して、こう整理することもできる:
  Sm(n) = 1/(m+1) { from k=0 to m } (m+1 C k)⋅(Bk)nm+1−k  《さ》

《け》から《こ》への書き換えと同様のことは、「分母を小さくする」目的で、定理の証明の中でも既に行った: 《く》の左辺参照(全体を n = p で割った後の式なので、 p の指数は 1 小さくなっている)。二つの表記《け》《こ》の違いは、 B1 の定義の違いとは別問題: B1 の定義が一定なら、どちらの表記も同じ値を表す。

〔参考〕 《さ》は Concrete Mathematics の (6.78) 式(変数名も全く同じ)。《こ》は Hardy–Wright §7.9 の表記。そこでは変数を表す文字が異なり、上記 m, k が、それぞれ k, r と呼ばれている。 Hardy–Wright では B1 に当たる β1 が +1/2 でなく −1/2 と定義されていて、従って和は Sm(n) でなく Sm(n−1) に当たる。

§19. m を 2 以上の任意の偶数とする。 m は少なくとも約数 1, 2 を持ち、従って少なくとも p = 2, 3 が定理の条件を満たすので、
  Bm + 1/2 + 1/3 (+ ···) = Bm + 5/6 (+ ···) = 整数
となり、 Bm の分母は因子 6 を持つ。しかし平方因子 22 を持たないので、 Bm の分母は、必ず6 の奇数倍に等しい。例えば、
  B2 = 1/6, B4 = −1/30, B6 = 1/42
の分母は、それぞれ 6 の 1 倍、 5 倍、 7倍。

m の約数のうち、 3 以上の奇数 d は Bm の分母に寄与しない。なぜなら d+1 は 4 以上の偶数、つまり合成数。 p は素数なので、 d = p−1 となること(つまり d+1 = p となること)は不可能だ。 d∣m ではあるけど。

 q が 6k+1 型の素数なら、 B2q の分母は 6。 B2q は正で、整数 + 1/6 に等しい。無限個の Bernoulli 数がこの形を持つ。

証明 2q の約数は 1, 2, q, 2q の四つだが、 q は奇数なので分母に寄与しない。 2q は偶数だが、 q ≡ 1 (mod 6) なので 2q + 1 ≡ 3 (mod 6) は合成数(3 の倍数)。分母に寄与しない。 2q ≡ 2 (mod 4) なので B2q は正。 6k+1 型の素数は無限に存在する。∎

最初の三つの 6k+1 型素数 q と、対応する B2q は次の通り(単なる例示なので、整数部分の計算法は略):
  q = 7 ⇒ B14 = 7/6 = 1 + 1/6
  q = 13 ⇒ B26 = 1425517 + 1/6
  q = 19 ⇒ B38 = 488332318973593 + 1/6

系2 q が素数 3 または 6k−1 型の素数なら、 B2q は正。その端数は、 2q+1 が素数なら 1/6 − 1/(2q+1) = (2q−5)/[6(2q+1)] に等しく、さもなければ 1/6 に等しい。

証明 2q ≡ 2 (mod 4) なので B2q は正。 2q の約数は 1, 2, q, 2q で、もし 2q+1 が合成数なら、 q が 6k+1 型素数の場合と同様。しかし q ≡ −1 (mod 6) なので 2q+1 ≡ −1 (mod 6) も素数になり得る(そのとき q は Sophie Germain 素数)。その場合、定理によって、
  B2q + 1/2 + 1/3 + 1/(2q+1) = 整数
となるが、 1/(2q+1) < 1/6 なので、 B2q の端数は 1 − 1/2 − 1/3 − 1/(2q+1) = 1/6 − 1/(2q+1) > 0 に等しい。∎

q = 3 のとき(2q+1 = 7 は素数)、 B6 = 1/6 − 1/7 = 1/42。分母 42 = (6+1) × 6。分子 1 = 6−5。

q = 5 のとき(2q+1 = 11 は素数)、 B10 = 1/6 − 1/11 = 5/66。分母 66 = (10+1) × 6。分子 5 = 10−5。

q = 11 のとき(2q+1 = 23 は素数)、 B22 = 854513/138 = 6192 + 17/138。ここで 17/138 = 1/6 − 1/23。分母 138 = (22+1) × 6。分子 17 = 22−5。

q = 17 のとき(2q+1 = 35 は合成数)、 B34 = 429614643061 + 1/6。

q = 5, 11, 23, 47 は、長さ 5 の Cunningham chain 2, 5, 11, 23, 47 に含まれる(q = 2 は自明な Bernoulli 数 B4 = 0 をもたらす)――この場合の Cunningham chain とは、「ソフィー・ジェルマン素数」の連鎖のこと。個々の Cunningham chain の長さは有限なので、ある素数が Sophie Germain 素数であるとしても、必ず chain の末端に非 Sophie Germain の素数 q が存在して、「整数 + 1/6」型の Bernoulli 数 B2q をもたらす。そして、その素数より大きい無限個の素数が存在する。従って、無限個の 6k+1 型素数が存在するか否かと無関係に、分母 6 の Bernoulli 数は無限個(cf. Concrete Mathematics, Exercise 6.54c)。

q が合成数で、二つ以上の(必ずしも相異ならない)奇素数の積に等しい場合にも、 B2q は「整数 + 1/6」型になり得る。例は q = 49 = 72 と q = 91 = 7⋅13。

q が2因子から成る場合、 q = r2 なら 2q の約数は 1, 2, r, 2r, r2, 2r2 = 2q で、 q = rs なら 2q の約数は 1, 2, r, s, 2r, 2s, rs, 2rs = 2q だが、 B2q が上記の型になるためには 2r+1, 2q+1 が合成数であることが必要。 q = rs なら 2s+1 が合成数であることも必要。 q = r2 の r、 ないし q = rs の r, s が 6k+1 型なら、 2r+1 等は 3 の倍数で、必要条件が満たされる。 r 等が 6k−1 型だとしても、条件が満たされる可能性はある(q = 289 = 172 のように)。 r = 2, 3 は条件を満たさない(2r+1 が素数)。

q が3因子から成る例は、 q = 343 = 73 と q = 1729 = 7⋅13⋅19 と q = 2197 = 133。 q が4因子から成る例は q = 2401 = 74

✿

References:
[1] Concrete Mathematics (2nd ed.), §6.5 / Exercise 6.54 (p. 315) / Answers 6.54 (p. 555)
[2] Hardy–Wright, §7.9, §7.10

[1] でも当初 B1 = −1/2 だった。 2022年の第34刷で +1/2 に変更されたそうだ。オンラインで新版(変更のあった節など)を自由に閲覧できる。
https://www-cs-faculty.stanford.edu/~knuth/gkp34.pdf

✿ ✿ ✿


2025-01-26 「6 の倍数 + 1」の形の素数は無限個ある 7, 13, 19, 31, …

#遊びの数論 #(37) #ベルヌーイ数 #円分多項式

分母が 6 の Bernoulli 数は、無限個ある。関連する話題について、何回かに分けて考えみたい。

Bernoulli(ベルヌリ、ベルヌーイ)の数のうち、分母 6 のものが無限個あること。その一つの証明法は 6k+1 型素数が無限にあることに基づく。 Knuth たちは、より簡単な別証明を記している。実は、さらに簡単な証明法もある。

今回は、 6k+1 型素数(6 の倍数より 1 大きい)が無限に存在あること――そのこと自体は Bernoulli 数とは関係ないが――だけを扱う。

✿

§20. 3 以外の(正の)素数は、 3 の倍数より 1 大きいか、または 3 の倍数より 1 小さい。つまり 3k+1 型か、または 3k−1 型だ(後者は 3k+2 型とも呼ばれる)。 k が奇数のとき 3k±1 は 偶数(つまり 2 の倍数)なので、偶数の素数 2(それは 3k−1 型である)を別にすると、「3k±1 型素数」と言うときの k は奇数でなければならない。「k は奇数」という隠れた条件をなくして対象の性質をより明確に述べるなら、 3k+1 型素数とは、実際には「6k+1」型素数で(7, 13, 19, 31, 37 など)、 3k−1 型素数とは、実際には 2 または「6k−1」型素数(5, 11, 17, 23, 29, 41 など)だ。

「3k+1 型素数」と「6k+1 型素数」という二つの表現は、ニュアンスの違いはあるとしても、全く同一の対象を指

† 「3k−1 型」と「6k−1型」には、もう少し明確な違いがある―― 2 は前者に含まれるが、後者には含まれない。負の素数を考える場合、同様に −2 は「3k+1 型」だが「6k+1 型」ではない、という違いがあるけれど、実際上、負の素数をこのように分類することは、ほとんどない。

Knuth たちが指摘しているように、 6k+1 型素数が無限に存在することの証明は、本質的に難しい。正式には解析的数論の問題であり、そこまで深く扱わないとしても、体系的に扱うには円分多項式を使う必要があり、さもなければ、工夫した(多少天下り的な)多項式を使う必要がある。平方剰余の理論、または位数の理論が必要になるだろう。とはいえ 6k+1 型の素数が無限に存在することは、Bernoulli 数の分母の話題に限らず、それ自体としても研究価値があるし、素朴に興味が湧く話題だ。以下では3種類の証明を紹介する。

証明1 p1, p2, ··· を相異なる 6k+1 型素数とする。この型の素数が有限個(c 個としよう)しか存在しないと仮定し、矛盾を導く。
  偶数 x = 2p1p2···pc
は因子 3 を持たず、従って、
  奇数 y = x2 + 3
は 2 でも 3 でも割り切れない。今、 y の任意の素因数を q とすると、
  y = x2 + 3 ≡ 0 つまり x2 ≡ −3 (mod q)
が成り立つが、任意といっても、上記のように q は 2 または 3 ではない。のみならず、平方剰余の相互法則(または「負の第三補充法」)によれば、この合同式を満たす 6k−1 型の法 q は存在しない。つまり q は 6k+1 型の素数。さて q は y を割り切るが、 p1, p2, ···, pc のいずれも y を割り切らない(そのどれで y を割っても 3 余る)。よってこの(6k+1 型の)素数 q は、最初に存在を仮定した c 個の 6k+1 型素数の、どれとも異なる。ゆえに「この型の素数が c 個しかない」という最初の仮定は不合理。∎

† 「q を 5 以上の素数とする。 x2 ≡ −3 (mod q) を満たす x は、 q が 3k+1 型なら存在し、 q が 3k+2 型なら存在しない」というもの。この場合、現に x は(c 個の素数の積の 2 倍として)具体的に構成され、存在するのだから、必然的に q は 3k+1 型(6k+1 型)でなければならない。

〔例1〕 x = 2⋅7⋅13 = 182 とすると y = 1822 + 3 = 33127 = 157 × 211。どちらの素因数も 6k+1 型。

〔例2〕 x = 2⋅7⋅13⋅19⋅31 = 107198 とすると y = 11491411207 は、それ自身、6k+1 型の素数。

証明2(cf. Kraitchik (1924), p. 8) 6k+1 型素数が c 個しかないと仮定し、それらの積を P とする。奇数 12P2 + 1 の任意の素因数 q は 6k+1 型で、最初に仮定した c 個の素数のどれとも異なる。実際、
  12P2 + 1 ≡ 0 つまり 3(2P)2 ≡ −1 (mod q)  《そ》
の両辺がもし平方剰余なら、第三補充法則から q は 12k±1 型だが、第一補充法則から q は 12k−1 型ではあり得ない。他方、もし《そ》の両辺が非剰余なら、第三補充法則から q は 12k±7 型だが、第一補充法則から q は 12k−7 型ではあり得ない。要するに q は 12k+1 型または 12k+7 型。∎

〔例3〕 P = 7⋅13 = 91 とすると 12P2 + 1 = 99373 = 43 × 2311。どちらの素因数も 6k+1 型(より詳しく言うと 12k+7 型)。

〔例4〕 P = 7⋅19 = 133 とすると 12P2 + 1 = 212269 = 37 × 5737。どちらの素因数も 6k+1 型(より詳しく言うと 12k+1 型)。

〔例5〕 P = 7⋅13⋅19⋅31⋅37 とすると 12P2 + 1 = 47195225814829 = 223 × 307 × 689373889。どの素因数も 6k+1 型(二つの3桁の素因数は 12k+7 型で、もう一つの大きい素因数は 12k+1 型)。

(12k+1 型の奇数 12P2 + 1 が 12k+7 型の素因数を持つなら、その個数は必ず偶数。 12k+1 型の素因数の個数は、偶数にも奇数にもなり得る。)

§21. 円分多項式に基づく一つの証明法は、次の通り。円分多項式を使うアプローチは比較的分かりにくいけど、「同様の手法によって、一般に ℓk+1 型素数(ℓ = 3, 4, 5, ···)が、それぞれ無限に存在することを証明できる」というメリットがある。

証明3 まず次の恒等式を導いておく。
  A6 − 1 = (A2 − 1)(A4 + A2 + 1) = (A2 − 1)[(A4 + 2A2 + 1) − A2] = (A2 − 1)[(A2 + 1)2 − A2]
  ∴ A6 − 1 = (A + 1)(A − 1)(A2 + A + 1)(A2 − A + 1)  《た》

今 6k+1 型素数が c 個しか存在しないと仮定し、それらの積を A とすると A ≡ 1 (mod 6) だが、そのとき《た》の左辺の因子 A2 − A + 1 も ≡ 1 (mod 6) であり、 2 でも 3 でも割り切れない。この因子の任意の素因数を q とすると、 q ≠ 2 かつ q ≠ 3。

《た》の左辺は q の倍数なので、右辺も q の倍数。つまり:
  A6 − 1 ≡ 0 すなわち A6 ≡ 1 (mod q)
ゆえに mod q での A の位数は 6 の約数 1, 2, 3, 6 のどれかだ

さて A は c 個の素数の積だが、その素数のどれも A2 − A + 1 を割り切らない(もし割れば、明らかに 1 余る)。一方、素数 q はこれを割り切るのだから、 A を構成する c 個のどの素因数とも q は値が異なる。つまり A は q の倍数ではない。よって Fermat の小定理から、
  Aq−1 ≡ 0 (mod q)
が成立。 A の位数が 6 であることを示せば、 6∣q−1 つまり q ≡ 1 (mod 6) となって、証明が完了する(そのとき q は 6k+1 型だが、最初に存在を仮定した c 個の素数のどれとも異なる「新しい」素数なので)

証明を完成させるため、もしも A の位数(mod q での)が 6 でなかったら矛盾が生じることを示す。

(I) もしも位数が 1 なら A ≡ 1 つまり A − 1 ≡ 0。もしも位数が 2 なら A2 − 1 = (A + 1)(A − 1) ≡ 0。もしも位数が 3 なら A3 − 1 = (A − 1)(A2 + A + 1) ≡ 0。いずれにしても、 A + 1, A − 1, A2 + A + 1 のどれかが q の倍数になり、《た》の右辺は q で少なくとも 2 回、割り切れてしまう(q の定義により A2 − A + 1 も q の倍数なので)。従って、それと等しい左辺についても:
  A6 − 1 ≡ 0 (mod q2)  《ち》
ところが…

補題 q を任意の素数とする。任意の整係数の多項式 h(x) と任意の整数 A について、 h(A) ≡ h(A + q) (mod q)

(II) もしも (I) の状況が発生し《た》の右辺が q2 で割り切れてしまったなら、そのときには上記の補題(証明は後述)から、《た》で「A を A + q に置き換えた等式」においても、右辺は q2 で割り切れてしまう。そのとき、「置き換えた等式」の左辺を考えると、
  (A + q)6 − 1 ≡ 0 (mod q2) つまり
  A6 + 6A5q + 15A4q2 + 20A3q3 + 15A2q4 + 6Aq5 + q6 − 1 ≡ 0 (mod q2)
が成り立つ。この最後の合同式の左辺について、 mod q2 において ≡ 0 である項(つまり q2 の倍数)を省くと:
  A6 + 6A5q − 1 ≡ 0 (mod q2)
《ち》から A6 − 1 も ≡ 0 なので:
  6A5q ≡ 0 (mod q2) 両辺を q で割って
  6A5 ≡ 0 (mod q)  《つ》

6 も A も q で割り切れないので、結論《つ》は事実に反する。なぜこの矛盾が生じたか。 (II) は仮定 (I) に基づくのだから、仮定 (I) が間違いだったのだ。すなわち A の位数は 6 でなければならない。∎

〔例6〕 A = 7⋅13⋅19 = 1729 とすると、 A2 − A + 1 = 37 × 80749。 q = 37 とすると、
  A2 − A + 1 ≡ 0 ⇒ A6 − 1 ≡ 0 (mod 37)
が成り立ち、 mod 37 での A の位数は 6 の約数、実は 6。 q = 37 との関係において(A37−1 ≡ 1)、この位数は確かに q−1 の約数。 6∣q−1 つまり q ≡ 1 (mod 6) なので、新しい 6k+1 型素数 q = 37 が見つかったことになる。

補題の証明 mod q では q の倍数は ≡ 0 なので:
  (A + q) ≡ A
  (A + q)2 = A2 + 2Aq + q2 ≡ A2
  (A + q)3 = A3 + 3A2q + 3Aq2 ≡ A3
  一般に (A + q)n = An + (q の倍数たち) ≡ An

従って、
  多項式 h(x) = anxn + an−1xn−1 + ··· + a1x + a0
に関して、 h(A) と h(A + q) の対応する(同じ次数の)項は、それぞれ合同。よって h(A) の値と h(A + q) の値、つまり「前者の各項の和」と「後者の各項の和」も、合同。∎

〔参考文献〕 Sury, “Cyclotomy and Cyclotomic Polynomials”
https://web.archive.org/web/20220812085623/https://www.ias.ac.in/describe/article/reso/004/12/0041-0053

✿ ✿ ✿


2025-01-31 「ソフィー・ジェルマン素数」の連鎖

#遊びの数論 #(37) #ベルヌーイ数

2 以上の整数のうち、 1 と自分自身でしか割り切れないものは素数と呼ばれる(例: 5, 7, 19)。

p が素数のとき、 2p は 1 と自分自身の他 2 と p でも割り切れるので、約数を 4 個、持つ(例: p = 5 のとき 2p = 10 の約数は 1, 2, 5, 10)。それでは 2p+1 はどうか。今の例では 2p+1 = 11 は素数。このように 2p+1 も素数になるような素数 p は、 Sophie Germain (ソフィ・ジェゥメ、ソフィー・ジェルマン)素数と呼ばれる(以下、単に Germain 素数と記す)。

p が Germain 素数なら 2p+1 も素数だが、この 2p+1 という素数が再び Germain 素数になるケースもある。例えば 5 → 11 は、どちらも Germain 素数(なぜなら 2⋅11 + 1 = 23 も素数)。さらに素数 23 も Germain 素数(なぜなら 2⋅23 + 1 = 47 も素数)。このような「Germain 素数の連鎖」は、どのくらい長く続き得るものだろうか?

✿

§22. 本題である「分母が 6 の Bernoulli 数」との関係。

p が 3 以上の素数のとき、 Bernoulli 数 B2p の分母は 2p の約数 1, 2, p, 2p の性質によって決まる: 約数に 1 を足したものが「素数」なら、その「素数」が分母の因子となるのであった(§13)。約数に 1 を足したものは、順に 2, 3, p+1, 2p+1。そのうち 2, 3 は素数だが、偶数 p+1 は非素数。ここまでは p の値によらず、共通。問題は、 2p+1 が素数か否か。もし 2p+1 が非素数なら、分母の因子は 2 と 3 だけ。つまり分母は 6 になる。 p = 7 のときの B14 = 7/6 のように(2p+1 = 15 は非素数)。一方、もし 2p+1 が素数なら(言い換えると p が Germain 素数なら)、 B2p の分母は、因子に 2p+1 が加わって 6(2p+1) になる。 p = 3 のときの B7 = 1/42 のように(2p+1 = 7 は素数)。あるいは p = 5 のときの B10 = 5/66 のように(2p+1 = 11 は素数)。

このことから、「分母が 6 の Bernoulli 数が無限個ある」ことを示すには、「2p+1 が素数でないような素数 p が無限個ある」こと、言い換えれば「Germain 素数でない素数が無限個ある」ことを示せばいい。

その第一の方法は、「6k+1 型の素数が無限個ある」ことに基づく。 p が 6k+1 型なら 2p+1 = 2(6k+1)+1 = 12k+3 は 3 の倍数なので、非素数。つまり 6k+1 型の素数はどれも非 Germain の素数(Germain 素数以外の素数)であり、その型の素数が無限にあることを示せば、非 Germain の素数も無限にあることになる。

しかし「6k+1 型の素数が無限個ある」ことの証明は、意外と面倒(§20)。 Knuth たちは、そのような証明が必要ないような、第二の方法を提示した。 2p+1 が素数になってしまうケース(つまり p が Germain 素数のケース)でも、もし q = 2p+1 が非 Germain の素数なら、その q によって分母が 6 の B2q が構成される。もし q もまた Germain 素数だとしても、 r = 2q+1 = 4p+3 が非 Germain の素数なら、その r によって分母が 6 の B2r が構成される。素数 p を出発点として、このように「2 倍して 1 を足す」操作を次々と続けた場合、 Germain 素数の連鎖が無限に続くことは不可能で、必ずどこかで非 Germain の素数に行き当たる。こうして得られた特定の非 Germain の素数を基準に、もっと大きい素数は無限個あるので、その一つを任意に選んで、再び同じ操作をすれば、新しい非 Germain の素数が見つかる。この処理は無限に反復可能。

要するに Knuth たちは、「6k+1 型素数の無限性」と無関係に、直接「非 Germain の素数の無限性」を考えた。結論は、
  p → 2p+1 → 4p+3 → 8p+7 → 16p+15 → 32p+31 → ···
という連鎖において、全部の数が素数にはなり得ないことに基づく。実際、 Fermat の小定理から、
  2p−1 ≡ 1 つまり 2p−1 − 1 ≡ 0 (mod p)  《て》
なので、「2 倍して 1 を足す」操作を p−1 回、繰り返した結果の数、
  (2p−1)p + (2p−1 − 1)  《と》
は p で割り切れすなわち素数ではない。

† 《と》の第1項 (2p−1)p が p で割り切れることは明白。《て》によって、第2項 2p−1 − 1 も p で割り切れる。

《と》が素数でないのだから、どんなに長く連鎖が続くとしても、「2 倍して 1 を足す」を p−2 回、繰り返して得られる (2p−2)p + (2p−2 − 1) は、もはや Germain 素数になり得ない!

ゆえに p から始まる Germain 素数の連鎖の長さは、出発点の p 自身をカウントに含めなければ、最大 p−3 であり、出発点の p もカウントに含めると、最大 p−2 だ(以下では出発点も連鎖の長さに含める。つまり p が Germain 素数なら、連鎖の長さは少なくとも 1)。

〔例1〕 p = 5 の場合。 5 → 11 → 23 → 47 → 95 のうち、最初の三つは Germain 素数だが、四つ目の s = 47 は非 Germain の素数。 p = 5 からの連鎖の長さは、決して p−2 = 3 を超えない(この場合、長さ 3 なので、理論上可能な最大の長さの連鎖となっている)。 B2s = B94 の分母は 6。ちなみに、もしも素数 2 から始めれば長さ 4 の連鎖 2 → 5 → 11 → 23 が得られるが、ここでは「p は 3 以上の素数」と仮定している。

〔例2〕 p = 17 の場合。 17 → 35 には Germain 素数が一つも含まれない。連鎖の長さ 0。 B2p = B34 の分母は 6。

〔例3〕 p = 29 の場合。 29 → 59 → 119 において 29 は Germain 素数だが q = 59 は非 Germain の素数(119 = 7 × 17 は非素数)。連鎖の長さ 1。 B2q = B118 の分母は 6。

✿

この方法は、確かに 6k+1 型素数の無限性を利用するよりは簡単だし、それ自体として興味深いことでもあるが、依然として、いささかトリッキー。実は、さらにシンプルな第三の証明法がある。「q = 7a のとき(a: 任意の正の整数)、 B2q の分母は 6」ということを容易に示すことができ、それだけでも「分母が 6 の Bernoulli 数は無限個」という証明になる。

✿ ✿ ✿


2025-02-04 約数の個数とベルヌーイ数 98 には約数が何個?

#遊びの数論 #(37) #ベルヌーイ数

250 には約数が何個あるか? 小学生の算数の問題のようだが、その発想を応用することで、「Bernoulli 数の中には、分母が 6 のものが無限個あること」を簡単に証明できる。

画像: 関いわく(抜粋)「六分之一…加」「三十分之一…減」「四十二分之一…加」。Bernoulliは同じことをA=1/6, B=−1/30, C=1/42のように記した。

画像・上部は、関孝和(せき・ただかず、せき・こうわ)の『括要算法』(1712年)。下部は Bernoulli(ベルヌリ、ベルヌーイ)の『Ars conjectandi』(1713年)。日本とスイスで、ほとんど同時に B2 = 1/6, B4 = −1/30, B6 = 1/42, B8 = −1/30 等々が記述されたのは、不思議なことだ。「関の本の方が1年早いので、これらの数は Bernoulli 数でなく Seki 数と呼ばれるべきだ」と考える人もいる。関の名を冠することは、関孝和にとっては名誉かもしれないが、現実的に、漢字で「関数」と書いたら「かんすう」と紛らわしく、話が混乱するだろう。「関孝和数」と書いても、どうも読みにくい。

二項係数と Bernoulli 数を組み合わせることで、例えば 12 + 22 + ··· + n2 や 14 + 24 + ··· + n4 を(一般に 1m + 2m + ··· + nm を)統一的に理解し、効率的に計算できる。どちらの著者も、経験的にそれに気付いたらしい。

https://wikiless.privacyredirect.com/wiki/File:Seki_Kowa_Katsuyo_Sampo_Bernoulli_numbers.png?lang=en
https://archive.org/details/jacobibernoulli00bern/page/98/mode/1up

✿

§23. m を 2 以上の偶数とする。 m 番目の Bernoulli 数 Bm は、ある「整数」から「m の約数 + 1」の形の各素数の逆数を引き算したものに等しい(§13)。 m が小さい場合、この「整数」とは 1 だ。

〔例1〕 m = 2 の約数を d とすると d = 1, 2 で、 d+1 = 2, 3 はどちらも素数。それらの逆数を 1 から引くと:
  B2 = 1 − 1/2 − 1/3 = 1/6

〔例2〕 m = 4 の約数 d = 1, 2, 4 について、 d+1 = 2, 3, 5 はどれも素数。それらの逆数を 1 から引くと:
  B4 = 1 − 1/2 − 1/3 − 1/5 = 1/6 − 1/5 = −1/30
ところで m = 8 の約数 d = 1, 2, 4, 8 について d+1 = 2, 3, 5, 9 だが、素数でない 9 を無視すると、 B8 の値は上記 B4 と全く同じ計算になる!

〔例3〕 m = 6 の約数 d = 1, 2, 3, 6 について、 d+1 = 2, 3, 4, 7 のうち 2, 3, 7 が素数。それらの逆数を 1 から引くと:
  B6 = 1 − 1/2 − 1/3 − 1/7 = 1/6 − 1/7 = 1/42

1 と 2 は常に m の約数なので(そして、それらに 1 を足した 2 と 3 は素数なので)、上記の原理によると Bm では、少なくとも 1/2 と 1/3 が整数から引き算される。言い換えると、整数から少なくとも 1/2 + 1/3 = 5/6 が引き算される。よって Bm の分母は最小でも 6。一般には 2, 3 以外の素数(または素数たち)の逆数も引き算されるので、分母はもっと複雑になる。例2・例3のように、引き算される分数が 1/2, 1/3 の他にもう一つある場合、そのもう一つを 1/p とすると、 Bm の分母は 6p に。なぜなら:
  整数 − (1/2 + 1/3 + 1/p) = 整数 − (5/6 + 1/p)
   = 整数 − ((5p)/(6p) + 6/(6p)) = 整数 − (5p + 6)/(6p)

同様に、もし引き算される分数が 1/2, 1/3, 1/p, 1/q の四つなら、 Bm の分母は 6pq になるし、引き算される分数が 1/2, 1/3, 1/p, 1/q, 1/r の五つなら、 Bm の分母は 6pqr になる。等々。大ざっぱに m がでかくなればなるほど m の約数 d は、個数もサイズも増大、それにつれて d+1 の中で素数になる数の個数もサイズも増え、従って Bm の分母はますます大きく、複雑になる傾向がある。

〔例4〕 m = 10 の約数 d = 1, 2, 5, 10 について、 d+1 = 2, 3, 6, 11 のうち 2, 3, 11 が素数なので:
  B10 = 1 − 1/2 − 1/3 − 1/11 = 1/6 − 1/11 = 5/66 ← 分母が前より複雑

〔例5〕 m = 12 の約数 d = 1, 2, 3, 4, 6, 12 について、 d+1 のうち 2, 3, 5, 7, 13 が素数なので:
  B12 = 1 − 1/2 − 1/3 − 1/5 − 1/7 − 1/13 = −691/2730 ← 分母がますます複雑
この分母は 2⋅3⋅5⋅7⋅13 = (2⋅3⋅5)⋅(7⋅13) = 30⋅91 = 2730 に等しい。

〔注〕 上記 B12 の引き算について。 1 − 1/2 − 1/3 − 1/5 = −1/30 までは B4 = B8 と同じ。そこから 1/7 と 1/13 を順々に引き算してもいいのだが、 1/7 + 1/13 = 13/91 + 7/91 = 20/91 をまとめて引いた方が楽。すると、通分して分母が 30 × 91 = 2730 になる。通分後の分子は −1 × 91 − 20 × 30 = −91 − 600 = −691。

一般的傾向としてはそうなのだが、にもかかわらず、 m がどんなに大きくなっても Bm の分母が一番シンプルな 6 になるケースが時々ある。

〔例6〕 m = 14 の約数 d = 1, 2, 7, 14 について、 d+1 = 2, 3, 8, 15 のうち素数は 2, 3 だけなので:
  B14 = 整数 − 1/2 − 1/3 = 整数 − 5/6 ← 分母は 6

B12 までは、「整数マイナス分数たち」の「整数」は常に 1 だったが、 B14 以降では、この「整数」は複雑に変化する。実は B14 の場合の「整数」は 2 で、従って B14 = 2 − 5/6 = 7/6 となる。

§24. 今 p を 3 以上の素数とする。 m = 2p 番目の Bernoulli 数 B2p は、「整数」から「2p の約数 + 1」の形の各素数の逆数を引き算したものに等しい。 2p の約数 d には、どんなものがあるか?

偶数 2p は、もちろん 1 と自分自身(2p)で割り切れる。明らかに 2 でも p でも割り切れ、それ以外の約数はない。よって 2p の約数は d = 1, 2, p, 2p の四つだが、 d+1 = 2, 3, p+1, 2p+1 のうち、 p+1 は絶対に素数ではない(p は 3 以上の素数なので p+1 は 4 以上の偶数であり、 2 で割り切れてしまう)。従って、もし 2p+1 も素数でないなら、 d+1 の中に素数は 2 と 3 の二つしかなく、 B2p の分母は 6 になる。

p = 7, m = 2p = 14 の場合の例6がその例: 2p の約数は 1, 2, p=7, 2p=14 の四つだが、それぞれ 1 を足すと、最初の二つ(2, 3)は常に素数だが、三つ目の p+1 = 8 は決して素数ではなく、四つ目の 2p+1 = 15 も、この場合、素数ではない。

この現象は m が 2p の形なら(p: 3 以上の素数)、常に起きるか? そうとも限らない。 p = 3 の場合 2p+1 = 7 は素数になり、従って B6 の分母は 6 にならない(6⋅7 = 42 になる)。 p = 5 の場合 2p+1 = 11 は素数になり、従って B10 の分母は 6 にならない(6⋅11 = 66 になる)。例3・例5参照。 B2p の分母が 6 になるためには 2p+1 が素数でないこと――言い換えれば、素数 p が Germain 素数でないこと――が必要だ(それは、この形の Bernoulli 数の分母が 6 になるための十分条件でもある)。それで前回は、非 Germain の素数が無限個あることを示し、それによって 分母 6 の Bernoulli 数も無限個あることを証明した。しかしその証明は Fermat の小定理に依存するなど、微妙にトリッキーだった。

代わりに p が 6k+1 型の素数であることを条件としてもいい。 p = 6k+1 なら 2p+1 = 12k+3 は 3 で割り切れ、決して素数にならないから。 p = 7, m = 14 は、このケースだった。これは「非 Germain の素数」より強い(過剰な)条件で必要条件ではないが、十分条件には違いない(例えば p = 17, m = 34 のように、 p が 6k+1 型でない場合でも、 2p+1 = 35 は非素数になり得るので、本来 p を 6k+1 型素数に限定する必要はない)。前々回、 6k+1 型素数が無限にあることを示すことで、分母 6 の Bernoulli 数も無限にあることを示した。その証明は、少し面倒だった。

今回は、前々回とも前回とも違う下記の命題を使って、分母 6 の Bernoulli 数も無限にあることを証明する。

命題 p を 6k+1 型の素数とする。任意の正の整数 a について m = 2pa 番目の Bernoulli 数の分母は 6 に等しい。例えば p = 7 とすると、 2⋅71 = 14 番目、 2⋅72 = 98 番目、 2⋅73 = 686 番目···の Bernoulli 数の分母は、どれも 6 に等しい。

これが証明されれば、 2⋅7a 番目の Bernoulli 数だけでも無限にあるので(なぜなら a = 1, 2, 3, ··· は任意の正整数)、 6k+1 型素数が無限にあることを示すまでもなく、分母 6 の Bernoulli 数が無限にあることが確定する。しかも、この証明は易しい。おまけに、この方法なら m = 2⋅71 番、 m = 2⋅72 番···の Bernoulli 数が「分母 6」なのだ、と無限個の番号を具体的に指定できる(比較として、非 Germain の素数 p ないし 6k+1 型素数 p が無限にあることに基づく証明では、「無限にある」という抽象的事実は分かるものの、無限個の m = 2p を具体的に表す式が得られない)。

例えば 250 は 2 で 1 回割り切れるが、 2 で割った商 125 は、もう 2 で割り切れない。一方、 250 を 5 で割った商 50 は、再び 5 で割り切れ、その商 10 は、さらに再び 5 で割り切れるが、その商 2 は、もう 5 で割り切れない。要するに 250 は 2 で 1 回割り切れ、 5 で 3 回割り切れる。実際、
  250 = 21⋅53
と素因数分解される。従って 250 は、 2 で最大 1 回割り切れ、 5 で最大 3 回割り切れ、より一般的に、その回数制限の範囲内なら 2e⋅5f で割り切れる(e は 0 以上 1 以下の整数、 f は 0 以上 3 以下の整数)。例えば 21⋅51 = 10 や 21⋅52 = 50 や 21⋅53 = 250 はどれも 250 の約数だが(制限範囲内)、 21⋅54 = 1250 や 22⋅51 = 20 は 250 の約数ではない(範囲外)。

2e⋅5f が 250 の約数であるとするなら、 e は e = 1 という最大値の他、 e = 0 という値を取ることができ、 f は 1, 2, 3 の三つの値の他、 f = 0 という値を取ることができる。つまり e の選択肢が二つ、 f の選択肢が四つあるので、 250 は合計 8 個の約数を持つ。次のように:
  e = 0 のとき 20⋅50 = 1, 20⋅51 = 5, 20⋅52 = 25, 20⋅53 = 125;
  e = 1 のとき 21⋅50 = 2, 21⋅51 = 10, 21⋅52 = 50, 21⋅53 = 250

より一般的に p と q が異なる素数なら、(正の)整数 paqb は (a + 1)(b + 1) 個の約数を持つ。 p, q, r が異なる素数なら、整数 paqbrc は (a + 1)(b + 1)(c + 1) 個の約数を持つ。整数の因子が四つ以上でも同様。

特に 2⋅7a の形の整数は (1 + 1)(a + 1) = 2(a + 1) 個の約数を持ち、その内訳は次の通り。
  (ア)因子 2 を 0 個含むもの 70 = 1, 71, 72, ···, 7a
  (イ)因子 2 を 1 個含むもの 2⋅70 = 2, 2⋅71, 2⋅72, ···, 2⋅7a
  どちらもそれぞれ a + 1 個

§25. 命題の証明。 m = 2⋅7a の約数を d として、 d+1 が素数になるのは d = 1 or 2 の場合(言い換えれば d+1 = 2 or 3 の場合)に限られることを示す。

d = 1 なら d+1 = 2 が素数であることは、論をまたない。一方、もし m の約数 d が上記(ア)のどれかで(つまり d = 7e の形で)、しかも d ≠ 1 とすると、その d は 7 以上の奇数なので(なぜなら奇数は何乗しても奇数)、 d+1 は 8 以上の偶数であり、 2 で割り切れるから、素数ではない。

d = 2 なら d+1 = 3 が素数であることも、論をまたない。一方、もし m の約数 d が上記(イ)のどれかで(つまり d = 2⋅7e の形で)、しかも d ≠ 2 とすると、その d は 3 の倍数より 1 小さいので(理由は下記)、 d+1 は 15 以上の 3 の倍数であり、 3 で割り切れるから、素数ではない。

要するに、この条件では「m の約数 d に 1 を足したものが素数になる」という事態は、 d+1 = 2 または d+1 = 3 のときに発生し、それ以外のときには発生しない。よって Bm = 整数 − 1/2 − 1/3 = 整数 − 5/6 の分母は 6 に等しい。

7e を 3 で割ると 1 余ること(e は 0 以上の整数)。 x = 3u + 1 と y = 3v + 1 をそれぞれ「3 で割ると 1 余る」ような、任意の整数とする(u, v は整数。 x と y は等しくても構わないし、等しくなくても構わない)。 x と y の積、
  xy = (3u + 1)(3v + 1) = 9uv + 3u + 3v + 1 = 3(3uv + 3u + 3v) + 1
を 3 で割ると 1 余る。すなわち:
  「3 で割ると 1 余る整数」と「3 で割ると 1 余る整数」の積は、再び「3 で割ると 1 余る整数」 (☆)

さて 7 は「3 で割ると 1 余る整数」なので、(☆)から、 72 = 7 × 7 = 49 も「3 で割ると 1 余る」。 49 と 7 に関して(☆)を再び使うと、
  73 = 72 × 7 = 49 × 7 = 343
も、「3 で割ると 1 余る」。以下同様に進めると 71, 72, 73, 74, ··· は、どれも「3 で割ると 1 余る整数」。

2⋅7e が 3 の倍数より 1 小さいこと。 7e は 3 の倍数より 1 大きいので、 7e = 3w + 1 と書くことができる(w: 整数)。このとき、
  2⋅7e = 2⋅(3w + 1) = 3(2w) + 2
は、 3 の倍数より 1 小さい。実際、この数に 1 を足すと、
  3(2w) + 2 + 1 = 3(2w) + 3 = 3(2w + 1)
となって、 3 の倍数になる(3 の 2w + 1 倍に等しい)。

以上は算数的な証明で、回りくどい。数論では、通常、同じことを次のように表現する。
  7 ≡ 1 (mod 3) なので 7a ≡ 1a = 1 (mod 3)
  ∴ 2⋅7a ≡ 2⋅1 ≡ 2 ≡ −1 (mod 3)

任意の 6k+1 型素数 p は ≡ 1 (mod 3) なので、上記の 7 ≡ 1 等の「7」という文字を「p」に置き換えても、結論は変わらない。そのことから、 p が 7 でなくても 6k+1 型の素数でさえあれば、任意の正整数 a について 2⋅pa 番目の Bernoulli 数は、分母が 6。∎

✿

「分母が 6 の Bernoulli 数は無限にある」という存在証明の中では、この方法は簡単で、しかも構成的。半面、この方法で構成した例はすぐ巨大になってしまい、扱いにくい。 B14 = 7/6 はいいとして、 B98, B686 となると――確かに分母は 6 なのだが――分子がそれぞれ 77 桁、 1104 桁もある。このような分数を具体的に記すことは、やればできるとはいえ、数値例として便利ではない。

✿ ✿ ✿


<メールアドレス>