2014/10/19

完全数の一覧と性質

分野: 整数問題  レベル: マニアック

完全数:
正の整数 $n$ について,約数の総和 $S(n)$ が $n$ の二倍となるとき,$n$ を完全数という。

完全数の例

・ $6$ は完全数
約数は $1,\:2,\:3,\:6$ で全て足すと $12$ となる。

・ $496$ は完全数
約数は $1,\:2,\:4,\:8,\:16,\:31,\:62,\:124,\:248,\:496$ で全て足すと $992$ となる。

・素数 $p$ は完全数でない
約数は $1$ と $p$ だが,$1+p=2p$ となる素数は存在しない。

偶数の完全数

1:$2^{N}-1$ が素数であるような正の整数 $N$ に対して,$n=2^{N-1}(2^{N}-1)$ は完全数である。
2:逆に,偶数の完全数は,$2^{N}-1$ が素数であるような正の整数 $N$ を用いて $n=2^{N-1}(2^{N}-1)$ という形で表される。

証明はこの記事の最後に(1は簡単,2は少し大変)。

$2^{N}-1$ という形の数をメルセンヌ数といい,素数のメルセンヌ数をメルセンヌ素数といいます。上記の定理によりメルセンヌ素数と偶数の完全数が一対一に対応していることが分かります。

例えば $N=2$ のとき,$2^{N}-1=3$ はメルセンヌ素数なので $n=2\cdot 3=6$ が完全数となります。

ちなみに奇数の完全数は存在するかどうかすら分かっていません。

完全数一覧

1000桁以下の完全数を一覧にしてみました。全部で $15$ 個あります。

上記の議論により,偶数の完全数は $N$ で表すことができます。桁数が大きくなると表記が大変なので大きい部分は $N$ のみ示します。また,1500桁以下の奇数の完全数は存在しないことが確認されているそうです。

$N$,対応する完全数
$2,\:6\\
3,\:28\\
5,\:496\\
7,\:8128\\
13,\:33550336\\
17,\:8589869056\\
19,\:137438691328$

以下 $N$ のみ示す。
$31,\:61,\:89,\:107,\:127,\:521,\:607,\:1279$

List of perfect numbersを参照しました。

偶数の完全数についての定理の証明

おまたせしました,整数問題として面白い部分です。
まずは簡単な1から証明します。

1:メルセンヌ素数→完全数の証明

$2^{N}-1$ が素数のとき,$n=2^{N-1}(2^N-1)$ の約数の総和は,
$S(n)=(1+2+\cdots +2^{N-1})\{1+(2^{N}-1)\}$
である。一つ目のカッコは等比数列の公式から $2^{N}-1$ である。
よって,$S(n)=(2^{N}-1)\cdot 2^N=2n$ となるので $n$ は完全数。

2は非常に面白いです。最初に証明したのはオイラーです。

2:完全数→メルセンヌ素数の証明

偶数の完全数 $n$ が $2$ で$(m-1)$ 回割り切れるとする(ただし $m$ は $2$ 以上の整数)。つまり,$n=2^{m-1}A\:\:$($A$ は奇数)と表す。約数の和は,
$S(n)=(1+2+\cdots +2^{m-1})S(A)=(2^{m}-1)S(A)$
ここで,$n$ が完全数であるので,
$2^{m}A=2n=S(n)=(2^{m}-1)S(A)$
これを $S(A)$ について解くと,
$S(A)=A+\dfrac{A}{2^m-1}$
となる。 $S(A),\:A$ は整数なので $\dfrac{A}{2^m-1}$ も整数。よって,
$A$ も $\dfrac{A}{2^m-1}$ も $A$ の約数。また,$m\geq 2$ より $A > \dfrac{A}{2^m-1}$
$S(A)$ が $A$ の異なる約数2つの和で表されているので,
$A$ は素数であり,$\dfrac{A}{2^m-1}=1$

奇数の完全数を発見した方はご一報ください!

分野: 整数問題  レベル: マニアック