完全数を定義する準備として, ｢約数の和｣から始めましょう｡ 整数\(n\)の約数とは\(n\)を割り切る整数のことでした｡ 今回の話では負の約数は出てきませんので, 約数と言ったら正の約数ということを約束しておきます｡
例えば\(12\)の約数は\(1, 2, 3, 4, 6, 12\)ですね｡
さて唐突ですが約数をすべて足してみましょう｡ \(12\)の場合は\(1+2+3+4+6+12=28\)となります｡ この和のことを約数の総和, またはもっと単純に約数の和といいます｡ 整数論では\(n\)の約数の総和のことを\(\sigma(n)\)と表現します｡ \(\sigma\)はシグマと読みます｡ (和の記号に使われる\(\Sigma\)もシグマでしたね｡ \(\sigma\)は小文字で\(\Sigma\)は大文字です｡) 例えば, \(\sigma(12)=28\)となります｡
自然数\(n\)が完全数であるとは約数の総和\(\sigma(n)\)が\(2n\)と等しいことである｡
ここでコメントを加えておきましょう｡ 自然数\(n\)の約数には常に\(n\)自身が含まれています｡ これを踏まえると, 完全数の定義は次のように言い換えることができます｡
自然数\(n\)が完全数であるとは自分自身を除いた約数の和が\(n\)に等しいことである｡
自分自身以外の約数のことを真の約数と言います｡ 先ほどのシグマ記号を使うと\(\sigma(n)-n\)が真の約数の和です｡ \(\sigma(n)-n=n\)と\(\sigma(n)=2n\)は同値なので, どちらの定義も一致することがわかります｡
では完全数を探してみましょう｡ 完全数を探すには, 真の約数の和を計算して, それが元の数と一致しているような自然数を見つけなくてはいけません｡
探し始める前に少しだけ知恵を絞って探す対象を狭めてみます｡ 素数は完全数にはなれないことを証明したいと思います｡
\(p\)を素数だとします｡ \(p\)は素数なので真の約数は\(1\)のみです｡ \(p\)の真の約数の和は\(1\)となり, それは\(p\)自身よりも小さいので\(p\)は完全数ではありません｡ これで証明終わりです｡
\(1\)の真の約数の和は\(0\), つまり\(1\)は完全数ではない｡
\(2\)と\(3\)は素数だから完全数ではない｡
\(4\)の真の約数は\(1\)と\(2\)で真の約数の和は\(3\)となり, 元の数\(4\)と一致しないので\(4\)は完全数ではない｡
\(5\)は素数なので完全数ではない｡
\(6\)の真の約数は\(1, 2, 3\)で真の約数の和は\(1+2+3=6\)となり元の数\(6\)と一致する｡ ゆえに\(6\)が最小の完全数となることがわかった｡
この調子で順に完全数か否かを調べて次の完全数を見つけてもいいが, 少し手間がかかりそうなのでPythonを使って完全数を発見するプログラムを書いてみよう｡
まずは自然数\(n\)の約数の総和\(\sigma(n)\)を返す関数を書いてみよう｡ 実は, 前回使ったSymPyにも約数の総和の関数が含まれているが今回はPythonの練習も兼ねて自分たちで書いてみましょう｡
def sigma(n):
sum = 0 # これに約数を足していく
for d in range(1, n + 1): # 1とnの間の自然数が約数か確かめていく
if n % d == 0: # dがnの約数なら
sum += d # sumにdを加える
return sum試しに
## 4
## 12
## 13
## 28sigma(n)は\(n\)自身も含めたすべての約数の和だということを覚えて置きましょう｡
約数の総和を求める関数sigma(n)を定義できたので, 与えられた自然数が完全数かどうかを調べるのは簡単です｡ sigma(n) == 2 *nかどうか調べていけばいいのです｡ 試しに100までの自然数にどのくらい完全数があるか調べてみましょう｡
## 6は完全数です｡
## 28は完全数です｡すると\(6\)の他に\(28\)が得られました｡ 実際, \(28=1+2+4+7+14\)と真の約数の和になっていることが確かめられます｡ 100以下に2つしか存在しないとなると完全数はあまりなさそうですね｡ 200までではどうでしょうか?
## 6は完全数です｡
## 28は完全数です｡同じ結果ですね｡ 200までにはすでに発見した2つの完全数しかないことがわかりました｡ もっと多くの数を調べてみましょう｡ \(l\)の値を変えて何度も確かめてもいいのですが, 同じことを繰り返すなら関数にしてしまいましょう｡
def perfects(l): # lまでの完全数を出力する
for i in range(1, l + 1):
if sigma(i) == 2 * i:
print(f"{i}は完全数です｡")この関数を使って
## 6は完全数です｡
## 28は完全数です｡
## 496は完全数です｡でようやく次の完全数\(496\)を発見できました｡ さらに
## 6は完全数です｡
## 28は完全数です｡
## 496は完全数です｡
## 8128は完全数です｡を実行すると, 少し計算を終えるのに時間がかかるかもしれませんが, 新しい完全数\(8128\)が見つかりました｡
Pythonの力を借りて1万までに4つの完全数を発見しました｡ もちろんこのプログラムを使えば次の完全数も発見できます｡ しかし, ここで用いているアルゴリズムはとても効率の良いものとは言えません｡ 次の完全数を見つけるには, このプログラムを相当長い時間走らせなければいけません｡ なにせ, 次の完全数は33550336なのですから｡
完全数を探すためには, がむしゃらに約数の和を計算していくのでは時間がかかり過ぎてしまいます｡ なにか数学的な完全数の特徴を見つけて, それをアルゴリズムに利用しなければなりませんね｡
さて, これまで完全数を見つけるためのPythonコードを書き, 実際にいくつか発見しました｡ でもどうして次の新しい完全数があるとわかるのでしょうか? 2018年11月の時点では50個しか完全数は知られていません｡ 完全数がとても人気のない数字で, 誰も探したがらないからではありません｡ 世界中でたくさんの人が新しい完全数を探し出そうとしています｡ 中にはとてもパワフルなコンピューターを使っている人もいます｡ それでも50個しか発見できていないのです｡ そして現在51個目を探し出そうとして稼働しているコンピューターは世界中に数多くあることでしょう｡ それにもかかわらず, 実は, 世界中の誰ひとりとして51個目の完全数が存在することすら知らないのです｡ もしかしたら50個しか完全数がない可能性もあるのです｡ そう, 完全数が無限個あるかどうかは未解決問題なのです｡ ただ多くの数学者は完全数は無限個あるだろうと予想しています｡
完全数に関するもうひとつの未解決問題を紹介します｡ 今まで私たちが見つけた完全数も, 世界中の人々が発見した50の完全数もすべて偶数です｡ 奇数の完全数は今のところ発見されていません｡ そして奇数の完全数が存在するかどうかは未解決問題です｡ 奇数の完全数が満たさなければいけない条件はいくつか発見されていますが, 存在の有無について言えるような結果はまだありません｡
完全数に関する数学的性質を調べてみましょう｡ まず, これまでに発見した完全数6, 28, 496, 8128を素因数分解してみましょう｡ SymPyのfactorintを使って素因数分解します｡
from sympy import factorint
for n in [6, 28, 496, 8128]:
dec = factorint(n)
print(f"{n}の素因数分解は{dec}")## 6の素因数分解は{2: 1, 3: 1}
## 28の素因数分解は{2: 2, 7: 1}
## 496の素因数分解は{2: 4, 31: 1}
## 8128の素因数分解は{2: 6, 127: 1}結果を表にしてみます｡
| 完全数\(n\) | \(n\)の素因数分解 |
|---|---|
| 6 | \(2\cdot 3\) |
| 28 | \(2^2\cdot 7\) |
| 496 | \(2^4\cdot 31\) |
| 8128 | \(2^6\cdot 127\) |
さて, この表から完全数の性質を予想してみましょう｡ まず, どの完全数も\(2\)のべき乗と, もう一つの奇素数の積になっています｡ もう少し観察してみましょう｡ これら奇素数がある特別なパターンを持っていることに気がつくかもしれません｡ それはこれらの奇素数に1を足すと2のべき乗になるということです｡ 例えば\(3+1=2^2\)や\(7+1=2^3\)となっています｡ これらの情報を表に加えてみましょう｡
| 完全数\(n\) | \(n\)の素因数分解 | 奇素数+1 |
|---|---|---|
| 6 | \(2\cdot 3\) | \(2^2\) |
| 28 | \(2^2\cdot 7\) | \(2^3\) |
| 496 | \(2^4\cdot 31\) | \(2^5\) |
| 8128 | \(2^6\cdot 127\) | \(2^7\) |
この新しい表をもう一度観察してみましょう｡ すると完全数の素因数分解の\(2\)の指数と奇素数+1の\(2\)の指数が, どれも\(1\)しか違わないことが見てとれます｡
さらに奇素数+1のほうの指数はどれも素数となっています｡
これらの観察をまとめると次のような性質があるのではないかと予想できます｡
完全数は奇素数\(2^p-1\)を使って\(2^{p-1}(2^p-1)\)と書ける｡ そして\(p\)は素数｡
Pythonで得たデータから推測したこの予想は, 実は偶数の完全数に関して正しいことが知られています｡ そして逆に, もし\(2^p-1\)が素数であるなら\(2^{p-1}(2^p-1)\)は完全数ということも知られています｡ つまり, 偶数の完全数は\(2^p-1\)の形をした素数によって特徴づけられていることがわかるのです｡ この形の素数はメルセンヌ素数と呼ばれています｡ メルセンヌ素数についてはまた後で詳しく説明します｡ 以下ではこの定理の証明をしたいと思います｡
ここでは上の定理を証明するための補題を証明します｡
任意の数\(x\)に対して \[ x^k – 1 =(x-1)(1+x+x^2+\cdots x^{k-1})\] が成り立つ｡
左辺の式を展開していきます｡ \[\begin{align*}
&(x-1)(1+x+x^2+\cdots x^{k-1}) \\
&=x+x^2+x^3+\cdots+x^k-1-x-x^2-\cdots-x^k\\
&=x^k – 1.
\end{align*}\] 最後の式を得るのに, \(x^k\)と\(-1\)以外の項はすべてキャンセルし合うことを使いました｡ よって証明したかった式を得ることができました｡ これで証明を終わりにしたいと思います｡
\(M_p=2^p-1\)の形をした素数のことをメルセンヌ素数と呼ぶのでした｡ ここではメルセンヌ素数から完全数を作る方法を証明したいと思います｡
\(M_p=2^p-1\)を素数とする｡ すると\(n=2^{p-1}M_p=2^{p-1}(2^p-1)\)は完全数である｡
完全数の定義に従って\(\sigma(n)=2n\)となることを示す｡ ここで\(\sigma(n)\)は\(n\)の約数の総和を表すことを思い出そう｡
\(M_p\)が素数と仮定しているので\(n\)の約数は\(1, 2, 2^2, \cdots, 2^{p-1}, M_p, 2M_p, 2^2M_p, \cdots, 2^{p-1}M_p\)となります｡ すると
\[\begin{align*}
\sigma(n)&=1 + 2+ 2^ 2+ \cdots+ 2^{p-1 }+ M_ p+ 2M_ p+ 2^2M_ p+ \cdots+ 2^{p-1}M_p\\
&= (1 + 2+ 2^ 2+ \cdots+ 2^{p-1 }) +(1 + 2+ 2^ 2+ \cdots+ 2^{p-1 })M_p\\
&= (1 + 2+ 2^ 2+ \cdots+ 2^{p-1 })(1+M_p).
\end{align*}\] ここで上の補題を\(x = 2\)として用いると \[1 + 2+ 2^ 2+ \cdots + 2^{p-1 } = 2^p – 1 = M_p\] となるので上の式に代入して \[\sigma(n) = M_p(1+M_p)=M_p2^{p}=2(2^{p-1}M_p)=2n\] となり\(n\)が\(\sigma(n)=2n\)を満たすことが証明されたので, \(n\)が完全数であることがわかりました｡ これで証明を終わりにしたいと思います｡
さて, 上で証明したことは, もし\(2^p-1\)が素数であるならば\(n=2^{p-1}(2^p-1)\)は完全数になるということでした｡ 逆に, どんな偶数の完全数も\(2^{p-1}(2^p-1)\)とかけ\(2^p-1\)が素数になることを証明しましょう｡
\(n\)を偶数の完全数とする｡ すると, あるメルセンヌ素数\(M_p=2^p-1\)が存在して\(n=2^{p-1}M_p\)となる｡
まず, \(n\)を偶数部分と奇数部分に分けて\(n=2^km\)と書きます｡ ここで\(m\)は奇数です｡ また\(n\)が偶数なので\(k\geq 1\)です｡ 次に, \(n\)の約数の総和も偶数と奇数に分けて考えます｡ \(S\)を\(n\)の奇数の約数の総和としましょう｡ つまり\(S\)は\(m\)の約数の総和です｡ \(S\)に含まれる奇数の約数ひとつひとつに\(2^i\), \(i=1, 2, \dots, k\)を掛けたものが\(n\)の偶数の約数となります｡ そうすると\(n\)の約数の総和は \[\begin{align*}
\sigma(n) &= S + 2S + 2^2S + \cdots + 2^kS \\
&=(1+2+2^2+\cdots2^k)S\\
&= (2^{k+1}-1)S.
\end{align*}\] ここで最後の変形は上の補題を\(x=2\)として使いました｡
さて, 仮定より\(n\)は完全数なので\(\sigma(n)=2n=2^{k+1}m\)が成り立っています｡ 上の\(\sigma(n)\)の式と比べると \[ (2^{k+1}-1)S = 2^{k+1}m\] となります｡ これを\(S\)について解くと \[\begin{align*}
S &= \frac{2^{k+1}m}{(2^{k+1}-1)}\\[6pt]
&= \frac{(2^{k+1}-1 + 1)m}{(2^{k+1}-1)}\\
&= m+\frac{m}{(2^{k+1}-1)}.
\end{align*}\]
それでは最後の式に注目してみましょう｡ \(S\)は\(n\)の奇数の約数の総和でしたので, もちろん\(S\)は整数です｡ また\(m\)も整数であることから最後の項\(\frac{m}{(2^{k+1}-1)}\)も整数でなければいけません｡ よって, この項も\(m\)の約数, つまり\(n\)の奇数の約数だということがわかります｡ そして\(k\geq 1\)だったので, この約数は\(m\)より小さいことがわかります｡ すると\(S\)は\(n\)のたった2つの奇数の約数の和で書けていることになります｡ \(S\)が\(m\)のすべての約数の和であることから\(m\)は2つの約数しか持たないことがわかります｡ これは\(m\)が素数であることを示しています｡ さらに\(m\)の約数は\(1\)と\(m\)であることから \[ \frac{m}{(2^{k+1}-1)} = 1\] でなければなりません｡ ゆえに \[ m = 2^{k+1} – 1\] が素数となり \[ n = 2^k (2^{k+1} – 1)\] と書けることが証明されました｡ 定理の記号に合わせるには\(p=k+1\)と置けばいいことがわかります｡ これで定理の証明を終わりにしたいと思います｡
上で得た結果をまとめると次の定理を得ます｡
もしメルセンヌ素数\(M_p=2^p-1\)があれば\(n=2^{p-1}M_p\)は偶数の完全数である｡ 逆に任意の偶数の完全数\(n\)に対し, メルセンヌ素数\(M_p=2^p-1\)が存在して\(n=2^{p-1}M_p\)と書ける｡
これによって偶数の完全数を探すという問題はメルセンヌ素数を探すことと同値になりました｡ 奇数の完全数は未だに一つも見つかっていない(あるかもわからない)ので今の所発見されている完全数の個数とメルセンヌ素数の個数は一致しています｡ そして, メルセンヌ素数が無限個あることがわかれば完全数も無限個あることになりますが, まだメルセンヌ素数が無限個存在するかどうかも未解決問題です｡
完全数を定義するために紹介した正の約数の総和を与える関数$\sigma(n)$の重要な性質をひとつ紹介します｡
$m$と$n$を互いに素な自然数とします｡ (互いに素とは$\gcd(m,n)=1$となることです｡) このとき次の等式が成り立ちます｡
\[\sigma(mn) = \sigma(m) \sigma(n)\]
この定理の証明は練習問題とします｡ 他の練習問題でもこの定理を使う場面があります｡ この定理の性質を満たす関数のことを乗法的な関数といいます｡
次回はさらにメルセンヌ素数について知っていきましょう｡
前回はPythonでモジュールをインストールして使用する方法を学びました｡ 例として、mathモジュールを使って平方根などの計算を行いました｡ 今回は整数論の勉強に役立つモジュールSymPyを使ってみましょう｡ これまでに紹介した素数に関するデータをSymPyモジュールに入ってる関数を用いて取得する方法も紹介します｡
続きを読む
素数にも“種族”というものがあって, 色々な名前がついた素数があります｡ \(4x+3\)型の素数が無限個あることは前に証明しました｡ この\(4x+3\)型の素数よりも遥かにレアな素数の種族を今回は扱っていきます｡
続きを読む