왜 p 자체가 소수여야 하나요?

만약 p가 1보다 큰 a와 b의 곱이라면, 2^p - 1은 2^a - 1(그리고 2^b - 1)로 나누어지므로 M_p는 합성수가 됩니다. 그 역은 성립하지 않습니다. 즉, p가 소수라고 해서 M_p가 반드시 소수인 것은 아닙니다. 예를 들어 p = 11은 소수이지만 M_11 = 2047 = 23 곱하기 89로 합성수입니다.

메르센 소수 체커

주어진 지수 p에 대해 2^p − 1이 메르센 소수인지 확인합니다. 애니메이션 반복 추적 기능이 포함된 루카스-레머 소수 판정법, 이진 비트 패턴 시각화, 유클리드-오일러 완전수 쌍 형성, 그리고 알려진 52개의 메르센 소수에 대한 역사적 맥락을 제공합니다.

메르센 소수 체커

Embed 메르센 소수 체커 Widget

메르센 소수 체커 정보

메르센 소수 체커에 오신 것을 환영합니다. 이 도구는 지수 $p$가 5000 이하인 경우 $2^p - 1$이 메르센 소수인지 확인하는 대화형 도구입니다. 이 도구는 유명한 루카스-레머 소수 판정법을 실행하고, 재귀식 $S_i = S_{i-1}^2 - 2 \pmod{M_p}$의 애니메이션 반복 추적을 보여주며, 모든 메르센 수의 고유한 특징인 이진 비트 패턴을 시각화합니다. 또한 결과가 소수인 경우 유클리드-오일러 정리를 통해 그에 대응하는 짝수 완전수를 함께 보여줍니다.

메르센 소수란 무엇인가요?

메르센 수는 $M_p = 2^p - 1$ 형태의 숫자입니다. $M_p$ 자체가 소수일 때 이를 메르센 소수라고 부릅니다. 이 이름은 초기 사례를 분류하고 257까지의 지수 중 어떤 것이 소수를 생성하는지 추측했던 프랑스 수도사 마랭 메르센(Marin Mersenne, 1588-1648)의 이름을 딴 것입니다. 그의 목록은 부분적으로 틀린 것으로 판명되었으나, 이후 3세기에 걸친 연구의 기폭제가 되었습니다.

메르센 소수

$$M_p = 2^p - 1 \;\; \text{은 소수이며, 여기서 } p \text{ 자체도 반드시 소수여야 함}$$

순서대로 나열된 처음 몇 개의 메르센 소수는 다음과 같습니다:

$M_2 = 3$
$M_3 = 7$
$M_5 = 31$
$M_7 = 127$
$M_{13} = 8{,}191$
$M_{17} = 131{,}071$
$M_{19} = 524{,}287$
$M_{31} = 2{,}147{,}483{,}647$ (1772년 오일러가 발견 — 104년 동안 알려진 가장 큰 소수였음)

2024년 현재 정확히 52개의 메르센 소수가 알려져 있습니다. 현재 기록은 2024년 10월 GIMPS 분산 컴퓨팅 프로젝트에 의해 발견된 $M_{136{,}279{,}841}$로, 십진법으로 41,024,320자리에 달하는 숫자입니다.

루카스-레머 판정법

메르센 소수가 기록적인 소수 목록을 독점하는 이유는 에두아르 루카스(1878)가 발견하고 데릭 레머(1930)가 단순화한 전문적이고 매우 빠른 소수 판정법 덕분입니다:

루카스-레머 판정법

$$S_0 = 4, \quad S_i = S_{i-1}^2 - 2 \pmod{M_p}$$

소수 $p \geq 3$에 대해: $\;M_p$가 소수임 $\iff S_{p-2} \equiv 0 \pmod{M_p}$

이 테스트는 $p-2$번의 모듈로 제곱 연산만을 필요로 합니다. 이는 전통적인 곱셈 방식으로 약 $O(p^3)$ 비트 연산, 또는 FFT를 사용하면 $O(p^2 \log p \log\log p)$가 소요됩니다. 수백만 자리에 달하는 $M_p$ 크기의 숫자에 대해 일반적인 소수 판정법을 사용하는 것과 비교하면 비약적으로 빠릅니다. 이 루카스-레머 지름길이 메르센 소수 탐색을 가능하게 합니다.

왜 p가 소수여야 하나요?

만약 $p = a \cdot b$ (단, $a, b > 1$)라면, 고전적인 항등식에 의해 $2^a - 1$이 $2^{ab} - 1$을 나눈다는 것을 알 수 있습니다:

인수분해 항등식

$$2^{ab} - 1 = (2^a - 1)\left(2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a + 1\right)$$

따라서 지수가 합성수라면 $M_p$는 자동으로 합성수가 됩니다. 그 역은 거짓입니다: $p$가 소수라고 해서 $M_p$가 소수임을 보장하지는 않습니다. 예를 들어, $p = 11$은 소수이지만 $M_{11} = 2047 = 23 \times 89$입니다.

메르센 소수와 완전수 (유클리드-오일러)

유클리드는 기원전 300년경 $2^p - 1$이 소수이면 $2^{p-1}(2^p - 1)$이 완전수(자기 자신을 제외한 진약수들의 합이 자기 자신과 같은 수)임을 발견했습니다. 오일러는 나중에 그 역인 모든 짝수 완전수가 이 형태를 가진다는 것을 증명했습니다.

유클리드-오일러 정리

$$N \text{ 이 짝수 완전수임} \iff N = 2^{p-1}(2^p - 1),\;\; 2^p - 1 \text{ 은 소수}$$

따라서 새로운 메르센 소수를 찾는 것은 즉시 새로운 완전수를 찾는 것과 같습니다. 처음 네 개의 짝수 완전수는 6, 28, 496, 8128로 고대부터 알려져 있었습니다. 홀수 완전수가 존재하는지 여부는 2,300년이 넘도록 해결되지 않은 문제로 남아 있습니다.

이진 비트 패턴

모든 메르센 수는 독특하고 깔끔한 이진수 표현을 가집니다. 이진법으로 $2^p$는 $1$ 뒤에 $p$개의 0이 붙으므로, $2^p - 1$은 정확히 $p$개의 연속된 1 비트입니다:

M_5 = 2^5 − 1 = 11111₂ = 31

M_7 = 2^7 − 1 = 1111111₂ = 127

이것이 도구에서 각 비트를 개별 타일로 시각화하는 이유입니다. 비트 패턴은 숫자의 소수 여부와 관계없이 메르센 수의 시각적 서명입니다.

이 계산기 사용 방법

지수 $p$ 입력: 1에서 5,000 사이의 양의 정수를 입력합니다.
체크(Check) 클릭: 도구는 먼저 $p$가 소수인지 확인합니다. 소수가 아니라면 왜 $M_p$가 합성수여야 하는지 설명합니다.
소수 $p$의 경우: 루카스-레머 재귀식이 $M_p$에 대해 $p - 2$번의 반복을 실행합니다.
결과 탐색: 결과 배너, 6행의 반복 추적(큰 $p$의 경우 생략된 중간 단계는 "..."로 표시), $M_p$의 십진법 및 이진법 형태, 해당되는 경우 유클리드-오일러 완전수 쌍을 확인하세요.

알려진 처음 12개의 메르센 소수

#	지수 $p$	$M_p = 2^p - 1$	자리수	발견
1	2	3	1	고대
2	3	7	1	고대
3	5	31	2	고대
4	7	127	3	고대
5	13	8,191	4	1456년 (익명)
6	17	131,071	6	1588년 Cataldi
7	19	524,287	6	1588년 Cataldi
8	31	2,147,483,647	10	1772년 오일러
9	61	2.3 × 10^18	19	1883년 Pervushin
10	89	6.2 × 10^26	27	1911년 Powers
11	107	1.6 × 10^32	33	1914년 Powers
12	127	1.7 × 10^38	39	1876년 루카스

GIMPS 프로젝트

George Woltman이 1996년에 시작한 GIMPS(Great Internet Mersenne Prime Search)는 자원봉사자들이 CPU 시간을 기부하여 후보 지수에 대해 루카스-레머 테스트를 실행하는 분산 컴퓨팅 프로젝트입니다. 2024년 기준 M_35 = M_{1398269} (1996년) 이후의 모든 메르센 소수는 GIMPS에 의해 발견되었습니다. 현대의 탐색 영역(지수 약 $10^8$)에서 단일 루카스-레머 테스트를 수행하려면 GPU 계산으로도 몇 주가 소요됩니다.

메르센 소수에 관한 흥미로운 사실들

$M_{31} = 2{,}147{,}483{,}647$은 C 언어에서 유명한 $\texttt{INT\_MAX}$인 32비트 부호 있는 정수의 최대값입니다. 이는 우연이 아닙니다. $M_{31}$이 소수이므로 자연스럽게 "오버플로 직전"의 경계값으로 사용된 것입니다.
연속된 메르센 소수 사이에는 알 수 없는 크기의 간격이 존재합니다. 메르센 소수가 무한히 많은지는 아직 알려지지 않았으나, 렌스트라-포머란스-왜그스태프(Lenstra-Pomerance-Wagstaff) 추측은 약 $e^\gamma \log_2 p$ 비율로 무한히 존재할 것이라고 예측합니다.
2008년, Electronic Frontier Foundation은 최초로 1,000만 자리 소수를 발견한 사람에게 미화 10만 달러를 수여했습니다. 상금은 $M_{43112609}$를 발견한 UCLA의 GIMPS 팀에게 돌아갔습니다. 최초의 1억 자리 소수 발견에 대해서는 여전히 15만 달러의 상금이 걸려 있습니다.
$M_{31}$은 오일러의 발견을 기념하는 1811년 러시아 100루블 기념 지폐에 등장합니다. 이는 화폐에 인쇄된 몇 안 되는 소수 중 하나입니다.
모든 메르센 소수가 완전수를 생성하므로, 인류는 현재 정확히 52개의 짝수 완전수 목록을 보유하고 있습니다(알려진 52개의 메르센 소수와 일치).

자주 묻는 질문

메르센 소수란 무엇인가요?

메르센 소수는 $2^p - 1$ 형태의 소수이며, 여기서 $p$ 또한 소수여야 합니다. 처음 몇 개는 3, 7, 31, 127, 8,191입니다. 2024년 기준 52개의 메르센 소수가 알려져 있으며, 가장 큰 알려진 소수($M_{136{,}279{,}841}$)는 4,100만 자리가 넘는 메르센 소수입니다.

루카스-레머 판정법은 어떻게 작동하나요?

소수 지수 $p \geq 3$에 대해, $S_0 = 4$ 및 $S_i = S_{i-1}^2 - 2 \pmod{M_p}$로 정의합니다. 메르센 수 $M_p = 2^p - 1$이 소수일 필요충분조건은 $S_{p-2} \equiv 0 \pmod{M_p}$인 경우입니다. 테스트는 $p - 2$번의 반복으로 실행되며, 각 반복은 단일 모듈로 제곱 연산입니다.

왜 p가 소수여야 하나요?

만약 $p = ab$로 두 인수가 모두 1보다 크면, $2^p - 1$은 $2^a - 1$(및 $2^b - 1$)로 나누어지므로 $M_p$는 합성수가 됩니다. 역은 성립하지 않습니다. $p$가 소수라고 해서 $M_p$가 소수인 것은 아닙니다. 예를 들어 $p = 11$은 소수이지만 $M_{11} = 2047 = 23 \times 89$로 합성수입니다.

메르센 소수와 완전수 사이에는 어떤 관계가 있나요?

유클리드-오일러 정리에 따르면 모든 짝수 완전수는 $2^p - 1$이 메르센 소수일 때 $2^{p-1}(2^p - 1)$ 형태를 가집니다. 따라서 모든 메르센 소수는 정확히 하나의 짝수 완전수를 생성하며, 모든 짝수 완전수는 메르센 소수로부터 생성됩니다. 홀수 완전수가 존재하는지는 수학의 오래된 미해결 문제입니다.

왜 M_p는 이진법으로 p개의 연속된 1 비트를 갖나요?

이진법에서 숫자 $2^p$는 1 뒤에 $p$개의 0이 붙은 형태입니다. 여기서 1을 빼면 모든 $p$개의 하위 0이 1로 바뀝니다. 따라서 이진법으로 $2^p - 1$은 정확히 $p$개의 1이며, 이는 소수 여부와 관계없이 모든 메르센 수의 시각적 특징입니다.

이 도구로 테스트할 수 있는 가장 큰 지수는 무엇인가요?

이 도구는 루카스-레머 반복이 일반적인 웹 요청 내에 완료될 수 있도록 최대 5,000까지의 지수를 테스트합니다. 더 큰 지수($10^8$ 근처의 GIMPS 탐색 영역 포함)의 경우, 단일 테스트에 현대식 GPU로도 몇 주가 걸릴 수 있으므로 Prime95와 같은 전용 소프트웨어가 필요합니다.