컴퓨터 없이 39자리 소수 증명한 19세기 수학자...뤼카-레머 판별법의 비밀

에두아르 뤼카, 20년 연구 끝에 2^127-1이 소수임을 손으로 증명

[한국정보기술신문] 현대 컴퓨터로도 몇 분이 걸릴 소수 판별을 19세기 수학자가 순전히 손으로 증명해낸 놀라운 이야기가 재조명되고 있다. 프랑스 수학자 에두아르 뤼카는 약 20년에 걸친 연구 끝에 39자리 숫자인 170,141,183,460,469,231,731,687,303,715,884,105,727이 소수임을 증명했다. 이 숫자는 2의 127제곱에서 1을 뺀 메르센 소수로, 컴퓨터 없이 증명된 가장 큰 소수로 기록되고 있다.

소수는 1과 자기 자신으로만 나누어지는 수로, 모든 정수는 소수의 곱으로 표현할 수 있어 수학의 주기율표로 불린다. 소수는 수직선상에 일정한 규칙성을 보이지만, 그 출현 양상은 아직 완전히 규명되지 않은 변동성을 특징으로 한다. 이러한 예측 불가능성은 수학자들에게 오랜 연구과제가 되어왔다.

메르센 소수의 특수성

최근 발견되는 기록적인 소수들은 대부분 2의 p제곱에서 1을 뺀 형태인 메르센 소수다. 2025년 10월 기준 현재까지 발견된 가장 큰 소수는 2의 136,279,841제곱에서 1을 뺀 수로, 무려 41,024,320자리에 달한다. 이 숫자를 소리 내어 읽으려면 약 240일이 걸릴 것으로 추정된다.

그러나 메르센 소수에는 함정이 있다. p가 소수라고 해서 2의 p제곱에서 1을 뺀 수가 항상 소수인 것은 아니다. 예를 들어 2의 11제곱에서 1을 뺀 2047은 23과 89의 곱으로 나타낼 수 있다.

뤼카의 독창적 판별법

19세기 중반 뤼카는 2의 127제곱에서 1을 뺀 수가 소수인지 판별하는 어려운 과제에 직면했다. 당시에는 컴퓨터가 없었기 때문에 이 39자리 숫자의 모든 약수를 손으로 확인해야 했다.

전통적인 방법은 해당 숫자보다 작은 모든 소수로 나누어 떨어지는지 확인하는 것이지만, 이는 시간이 매우 오래 걸리고 모든 작은 소수를 알아야 하기 때문에 사실상 불가능했다. 뤼카는 동료 수학자 에바리스트 갈루아의 연구를 바탕으로 훨씬 적은 계산만 필요한 새로운 방법을 개발했다.

뤼카가 개발한 알고리즘은 다음과 같다. 첫 항이 4이고 이후 각 항이 이전 항의 제곱에서 2를 뺀 값인 수열을 만든다. 이 수열은 4, 14, 194, 37634 순으로 이어진다. 2의 p제곱에서 1을 뺀 수가 소수일 필요충분조건은 수열의 p-2번째 항이 해당 메르센 수로 나누어떨어지는 것이다.

유한체 이론의 응용

이 판별법이 작동하는 원리는 갈루아의 유한체 이론에 기반한다. 갈루아는 19세기 초 다양한 수학적 대상의 대칭성을 연구하면서 기하학적 도형뿐만 아니라 방정식이나 수체의 대칭성도 고려했다. 수체란 사칙연산을 적용해도 집합을 벗어나지 않는 수의 집합을 말한다.

특히 0부터 p-1까지의 정수만 포함하는 유한체가 존재하는데, 이들 수는 주기적으로 반복된다. 아날로그 시계에서 12 다음에 1이 오는 것처럼 자연스러운 개념이다. 유한 수 체계가 체가 되는 필요충분조건은 p가 소수인 것으로 밝혀졌다.

뤼카는 2의 127제곱에서 1을 뺀 수가 소수라면 해당 유한체가 특정한 대칭적 성질을 가져야 한다는 원리를 활용했다. 수년간의 치밀한 작업 끝에 뤼카는 이 방법을 적용해 2의 127제곱에서 1을 뺀 수가 실제로 소수임을 증명했다.

다만 뤼카는 자신의 방법이 메르센 소수를 확실히 판별한다는 것을 완전히 증명하지는 못했다. 이는 1930년 수학자 데릭 헨리 레머에 의해 완성되었으며, 이러한 이유로 이 방법은 뤼카-레머 소수 판별법으로 불린다. 컴퓨터의 도움 없이 발견된 가장 큰 소수로 남아있는 뤼카의 업적은 순수 수학적 추론의 힘을 보여주는 기념비적 사례로 평가받고 있다.

한국정보기술신문 정보기술분과 유상헌 기자 news@kitpa.org