メルセンヌ素数と完全数の関係

メルセンヌ素数と完全数には面白い関係がある。

1. メルセンヌ素数とは？

　メルセンヌ素数とは、メルセンヌ数かつ素数であるような数のこと。メルセンヌ数とは、2^k-1という形で表される数のことで、2進数で表したときに、1のみで構成される数のことである。

2. 完全数とは？

完全数とは、その数のproper divisor（自分以外の約数）の和が自分自身と等しいような数のこと。

6 = 1 + 2+ 3

28 = 1 + 2 + 4 + 7 + 14

が最初の2つの完全数である。

3. 面白い関係って？

　メルセンヌ素数と完全数の間には以下の定理が成り立つ。

メルセンヌ数2^k-1が素数であるとき、2^k-1(2^k-1)は完全数である。逆に、すべての偶数の完全数は、2^k-1(2^k-1)という形（2の冪乗とメルセンヌ素数の積）で表現できる。（※注意）

　証明のために関数σを導入します。σ(n)は、nの約数（properな約数ではなく、自分自身も含むことに注意）の和を表します。例えば、

σ(6) = 1 + 2 + 3 + 6 = 12

です。nが完全数の場合は、σ(n) = 2nです。

　

　この関数σについて以下の補題を考えます。

N = ab（a, bは互いに素）と表せるとき、σ(N) = σ(a) * σ(b)である。

　証明)　σ(a) * σ(b) = (a1 + a2 + a3 + ... ) * (b1 + b2 + b3 + ... ) = Σ(aの約数 * bの約数)である。ここでa1,a2,..はaの約数、b1,b2,..はbの約数である。よって、（aの約数 * bの約数）がNの約数となることと、Nの任意の約数dがある一組の(i, j)についてd = ai * bjとなることを示せばよい。

　まず前半だが、a, bが互いに素であるため、a x + b y = 1となるような整数(x, y)が存在する。両辺にNをかけると、a x N + b y N = Nとなる。aの約数 | a かつ bの約数 | Nなので、（aの約数 * bの約数）はa x Nを割りきる。同様に（aの約数 * bの約数）はb y Nを割りきる。よって（aの約数 * bの約数）はNを割りきる。

　次に後半を示す。a, bの素因数分解を

a = p₁^k1p₂^k2p₃^k3...p_n^kn

b = q₁^t1q₂^t2q₃^t3...q_m^tm

と表記する。ki > 0, i = 1,2,...n、およびtj > 0, j = 1,2,..mである。また、aとbが互いに素なので、p_i≒q_j, i=1,2,..n, j =1,2,...mである。

N= a * bなので、Nの素因数分解は

N = p₁^k1p₂^k2p₃^k3...p_n^kn q₁^t1q₂^t2q₃^t3...q_m^tm

となる。ここで、Nの任意の約数は、

x = p₁^k'1p₂^k'2p₃^k'3...p_n^k'n q₁^t'1q₂^t'2q₃^t'3...q_m^t'm

と表すことができる。ただし、0 ≦k'i ≦ki, i = 1,2,...n、0 ≦ t'j ≦tj, j=1,2,...,m.である。

Nの任意の約数を選ぶことと、(k'1,k'2, ..., k'n, t'1,t'2,..., t'm)の値を決めることは一対一に対応している。(k'1,k'2, ..., k'n, t'1,t'2,..., t'm)が決まれば、(k'1,k'2, ..., k'n)、(t'1,t'2,..., t'm)が決まり、これは、対応するaの約数、bの約数が一意に決まることを意味する。□

　それでは、メルセンヌ素数と完全数に関する定理の証明に入ります。まず、最初の部分を証明します。

2^k-1は素数なので、σ(2^k-1) = 1 + 2^k-1 = 2^kです。2^k-1は、2のべき乗なので約数は1, 2, 2², .... 2^k-2, 2^k-1である。よって、σ(2^k-1) = 1 + 2 + 2² + ... + 2^k-1 = 2^k-1。2^k-1（2の冪乗）と2^k-1（奇数）は互いに素なので補題より、σ(2^k-1(2^k-1)) = σ(2^k-1) * σ(2^k-1) = (2^k-1) * 2^k = 2 * 2^k-1(2^k-1)となる。

σ(n) = 2nなので、2^k-1(2^k-1)は完全数である。

　次に後半を示す。偶数の完全数を2^k-1mと表記する。ただし、k≧2、mは奇数。

補題よりσ(2^k-1m) = σ(2^k-1) * σ(m) = (2^k-1) σ(m)。

また、2^k-1mは完全数であることから、σ(2^k-1m) = 2 * 2^k-1m = 2^km。

よって、

2^km = (2^k-1) σ(m)。

ここで、(2^k-1) | 2^km、かつ2^kと(2^k-1)は互いに素であることから、(2^k-1) | m。

よって、m = (2^k-1) Mとして先ほどの式に代入すると

2^k (2^k-1) M = (2^k-1) σ(m)となり、両辺を (2^k-1) で割ると、

2^kM = σ(m)。

m + M = (2^k-1) M + M = 2^kMより、σ(m) = m + Mとなるが、これはmが素数で、M=1であることを意味する。よって、m = 2^k-1（素数）となり、もともとの完全数は、2^k-1(2^k-1)と表される。□

（※注意）奇数の完全数が存在するか否かは不明です。現時点で発見されている完全数はすべて偶数です。

参考：

[1] http://primes.utm.edu/notes/proofs/EvenPerfect.html
[2] http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E6%95%B0