📂정수론

메르센 소수

정의 ¹

$M_{n} = 2^{n} - 1$ 가 소수면 $M_{n}$ 를 메르센 소수^{mersenne Prime}라 한다.

설명

메르센 소수의 발견은 $p=x^{n}-1$ 꼴이 소수인지에 대한 탐구로부터 시작된다. 수식을 보자마자 단박에 알아챌 수 있는 것은 $x$ 가 홀수인 경우 $p=2$ 를 제외하면 소수가 될 수 없다는 것이다. 또한 $$ x^{n}-1 = (x-1) ( x^{n-1} + x^{n-2} + \cdots + x^2 + x + 1 ) $$ 이므로, $( x^{n-1} + x^{n-2} + \cdots + x^2 + x + 1 )$ 이 무슨 수가 되든 적어도 $(x-1)$ 은 반드시 $1$ 이어야 소수라고 할 수 있다. 즉 $x$ 는 짝수인 정도가 아니라 정확히 $2$ 여야만 하고, 따라서 우리는 $p= 2^{n} - 1$ 꼴만 신경쓰면 된다.

2018년 5월까지 발견된 메르센 소수는 총 $50$ 개로, 가장 큰 메르센 소수는 $M_{77,232,917}$ 이다. 이는 자리수만 해도 $23,249,425$ 에 이르는 큰 수다. 한편 처음으로 등장하는 메르센 소수 몇 개를 살펴보면 흥미로운 점을 발견할 수 있다.

$$ \begin{align*} M_{2} &= 2^{2} - 1 = 3 \\ M_{3} &= 2^{3} - 1 = 7 \\ M_{5} &= 2^{5} - 1 = 31 \\ M_{7} &= 2^{7} - 1 = 127 \\ M_{13} &= 2^{13} - 1 = 8191 \end{align*} $$

정리

메르센 소수 $M_{n}$ 에 대해 $n$ 은 소수다.

증명

메르센 소수 $M_{n} = 2^{n} - 1$ 에 대해 $1$ 이 아닌 두 정수 $a,b$ 에 대해 $n=ab$ 이라고 가정해보면 $$ 2^{ab} - 1 = (2^{a} - 1) ( 2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^{a} + 1 ) $$ 즉 $2^{ab} - 1$ 는 합성수인데, 이는 가정에 모순이다.

■

역이 성립하지 않음을 보이는 반례로는 $n=11$ 인 경우가 있다. $M_{11} : = 2^{11} - 1 = 2047$ 은 $23$ 과 $89$ 의 곱으로, $M_{11}$ 은 메르센 소수가 아니다.