짝수 완전수(perfect number)와 메르센 소수(Mersenne prime)

완전수(perfect number)

정수론에서, 완전수(perfect number)란 자기 자신을 제외한 양의 약수를 모두 더했을 때 자기 자신이 되는 양의 정수를 말한다. 예를 들어 $6$의 양의 약수는 $1,\,2,\,3,\,6$이고, $1 + 2 + 3 = 6$을 만족하므로, $6$은 완전수의 한 예이다. 또 다른 완전수의 예로는 다음과 같은 수들이 있다.

\[ \begin{align*} 6 &= 1 + 2 + 3 \\[5px] 28 &= 1 + 2 + 4 + 7 + 14 \\[5px] 496 &= 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 \\[5px] 8128 &= 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064 \end{align*} \]

주어진 양의 정수 $n$의 모든 양의 약수를 더해주는 함수를 $\sigma$로 나타내고 약수함수(divisor function)라 부른다. 즉, 약수함수 $\sigma$는 다음과 같이 정의되는 함수이다.

\[ \sigma(n) := \sum_{d \, \mid \, n} d \]

위 정의를 이용하면, 어떤 양의 정수 $n$이 $\sigma(n) = 2n$을 만족할 때 완전수가 됨을 알 수 있다.

$ $

약수함수에 대한 몇 가지 성질을 증명 없이 받아들이도록 하자. (아래의 성질들은 모두 약수함수의 정의를 이용하여 간단히 증명이 가능하다.)

• 주어진 양의 정수 $n$의 소인수분해가 $n=p_1^{a_1}\dots p_k^{a_k}$으로 주어졌다고 하자. 그러면 $\sigma(n)$은
  \[ \sigma(n) = \left( \frac{p_1^{a_1 + 1} - 1}{p_1 - 1} \right) \left( \frac{p_2^{a_2 + 1} - 1}{p_1 - 1} \right) \cdots \left( \frac{p_k^{a_k + 1} - 1}{p_k - 1} \right) \]

  으로 주어진다. 특히 $p$가 소수이면, $\sigma(p) = 1+p$이다.

• 임의의 두 양의 정수 $m,\,n$에 대하여 $\sigma(mn) = \sigma(m)\sigma(n)$이 성립한다. 이러한 성질을 만족하는 $\sigma$와 같은 함수를 곱셉적 함수(multiplicative function)이라 한다.

$ $

메르센 소수(Mersenne prime)

메르센 소수(Mersenne prime)란 $M_n := 2^n - 1$의 형태를 갖는 소수를 말한다.^[각주:1] 첫 몇 개의 메르센 소수는 다음과 같다.

\[ \begin{align*} M_2 &= 2^2 - 1 = 3 \\[5px] M_3 &= 2^3 - 1 = 7 \\[5px] M_5 &= 2^5 - 1 = 31 \\[5px] M_7 &= 2^7 - 1 = 127 \end{align*} \]

1644년 마랭 메르센은 $2^{n}-1$ 형태가 소수가 되는 것은, $n \leq 257$일 때 $n=2$, $3$, $5$, $7$, $13$, $17$, $19$, $31$, $67$, $127$, $257$ 뿐이라고 발표하였다. 그러나 그 주장의 일부는 잘못임이 밝혀졌는데, 목록에 포함되지 않은 $M_{61}$, $M_{89}$, $M_{107}$는 소수이며, 목록에 포함되어 있는 $M_{67}$, $M_{257}$는 합성수이다.

$ $

짝수 완전수(perfect number)와 메르센 소수(Mersenne prime)

언뜻 보면 완전수와 메르센 소수는 별 관련이 없는 것 처럼 보이지만, 놀랍게도 짝수 완전수와 메르센 소수 사이에는 일대일 대응관계가 존재한다. 이 사실은 다음 정리로 부터 얻을 수 있다.

$ $

정리.

만약 $M_n = 2^n - 1$이 메르센 소수이면, $N := 2^{n-1}M_n = 2^{n-1}(2^n - 1)$은 짝수 완전수이다. 반대로 어떤 양의 정수 $N$이 짝수 완전수이면, 메르센 소수 $M_n$이 존재하여 $N = 2^{n-1}M_n = 2^{n-1}(2^n - 1)$과 같이 나타낼 수 있다.^[각주:2]

$ $

증명. 우선 $M_n = 2^n - 1$이 메르센 소수라 가정하자. 우선 $N = 2^{n-1}M_n$이 짝수임은 자명하다. 이제 $\sigma$가 곱셈적(multiplicative)이고 $\sigma(M_n) = M_n + 1 = 2^n$이라는 사실로부터 다음이 성립한다.

\[ \sigma(N) = \sigma(2^{n-1}M_n) = \sigma(2^{n-1})\sigma(M_n) = (2^n-1) 2^n = 2N \]

따라서 $N$은 (짝수) 완전수이다.

$ $

이제 반대로 양의 정수 $N$이 짝수 완전수라 가정하자. 즉, $\sigma(N) = 2N$이 성립한다. 한 편, $N$이 짝수이므로 적당한 홀수 $M$과 $n \geq 2$가 존재하여, $N = 2^{n-1} M$으로 나타낼 수 있다. 이제 $M$이 메르센 소수임을 보이면 증명이 완료된다. 이를 보이기 위해 우선

\[ \sigma(N) = 2N = 2^n M \tag{1} \]

이 성립함을 확인하자. 또한 $\sigma$가 곱셈적이라는 사실로부터

\[ \sigma(N) = \sigma(2^{n-1} M) = \sigma(2^{n-1})\sigma(M) = (2^n - 1)\sigma(M) \tag{2} \]

이 성립한다. 따라서 $(1)$, $(2)$에 의해

\[ 2^n M = (2^n - 1)\sigma(M) \tag{3} \]

을 얻는다. 위 식으로부터 $2^n - 1$은 $M$의 약수여야만 함을 알 수 있으므로, $M = (2^n - 1)m$으로 나타낼 수 있다. 이제 이를 다시 식 $(3)$에 대입하여 정리하면, $\sigma(M) = 2^n m$를 얻는다. 한 편, $M$과 $m$은 모두 $M$의 양수이므로,

\[ 2^n m = \sigma(M) \geq m + M = m + (2^n - 1)m = 2^n m \]

따라서 $\sigma(M) = m + M$이어야만 한다. 즉, $M$은 두개의 양의 약수만을 갖으므로 $M$은 소수라는 사실을 알 수 있다. 또한 $M$의 두개의 약수는 $1$과 $M$이 되어야 한다는 사실로부터 $m=1$이라는 결론을 얻는다. 따라서 $M = (2^n - 1)m = 2^n - 1$의 꼴로 나타낼 수 있고, $M$이 메르센 소수가 된다..

$ $

위 정리를 이용하면, 모든 짝수 완전수 $N$은 적당한 양의 정수 $M$이 존재하여 $1$부터 $M$까지의 합으로 나타낼 수 있음을 보일 수 있다.

$ $

따름정리.

$N$이 짝수 완전수라 하자. 그러면 양의 정수 $M$이 존재하여,

\[ N = 1 + 2 + \cdots + M \]

으로 나타낼 수 있다.

$ $

증명. $N$이 짝수 완전수이므로 메르센 소수 $M_n$이 존재하여 $N := 2^{n-1}M_n = 2^{n-1}(2^n - 1)$으로 나타낼 수 있다. 이를 정리하면,

\[ N = 2^{n-1}M_n = \frac{2^n M_n}{2} = \frac{(M_n + 1) M_n}{2} = 1 + 2 + \cdots + M_n \]

따라서 $M = M_n$으로 두면 증명이 완료된다..

$ $

위 사실을 첫 몇 개의 짝수 완전수에 적용해 보면 다음과 같다.

\[ \begin{align*} 6 &= 1 + 2 + 3 \\[5px] 28 &= 1 + 2 + 3 + 4 + 5 + 6 + 7 \\[5px] 496 &= 1 + 2 + 3 + \cdots + 30 + 31 \\[5px] 8128 &= 1 + 2 + 3 + \cdots + 126 + 127 \end{align*} \]

$ $

몇 가지 잘 알려진 미해결 문제들

완전수와 메르센 소수에 대한 몇 가지 잘 알려진 미해결 문제들은 다음과 같은 것들이 있다.

• 위 정리에 의하면 짝수 완전수와 메르센 소수 사이에는 일대일 대응이 존재하므로, 만약 짝수 완전수의 개수가 유한/무한 하다면 메르센 소수의 개수 또한 유한/무한하다. 하지만 짝수 완전수 또는 메르센 소수가 무한히 존재하는지의 여부는 둘 다 아직까지 알려져 있지 않다.
• 여태까지 알려진 모든 완전수는 짝수 완전수 뿐인데, 홀수 완전수가 존재하는지에 대한 여부 또한 여전히 미해결 문제이다.
• $2^n - 1$형태의 정수이면서 소수가 아닌 수를 메르센 합성수(Mersenne composite number)라 하는데, 메르센 합성수가 무한히 존재하는지의 여부도 아직까지 알려져 있지 않다.

 

1. http://www.mathstorehouse.com/archives/1500 [본문으로]
2. 위 정리의 앞부분은 유클리드가 증명하였고, 첫부분의 역인 정리의 뒷부분은 후에 오일러에 의해 증명 되었다. [본문으로]