The sesquicentennial of the prime number $2^{127} - 1$

위대한 숫자의 추적: 소수, 퍼즐, 그리고 체스판의 이야기

당신은 '소수(prime)'라고 불리는 매우 특별한 종류의 숫자를 찾는 탐정이 되었다고 상상해 보십시오. 이 숫자들은 모든 수학의 기초가 되는 건축 블록으로, 1과 자기 자신으로만 나누어떨어지는 숫자들입니다. 수 세기 동안 수학자들은 단순히 소수를 찾는 것이 어려워서가 아니라, 그 숫자들이 숫자의 작동 원리에 대한 비밀을 간직하고 있기 때문에 가장 거대하고 포착하기 어려운 소수를 찾는 데 집착해 왔습니다. 소수를 찾기 위해 당신은 보통 더 작은 숫자들로 하나씩 나누어지는지 확인하는 '시행착오'의 게임을 수행해야 합니다. 하지만 진정으로 거대한 숫자의 경우, 이는 해변의 모래알 하나하나를 직접 집어 올리며 숫자를 세려는 것과 같습니다. 우주의 나이보다 더 오랜 시간이 걸릴 것입니다!

이 논문은 1876년, 지루한 숫자를 세는 게임을 건너뛸 방법을 찾아낸 천재적인 프랑스 수학자 에두아르 루카스(Édouard Lucas)의 이야기를 들려줍니다. 그는 단순히 거대한 소수를 찾아낸 것이 아니라, 숫자가 소수임을 증명하기 위해 모든 약수를 일일이 확인할 필요가 없는 영리한 지름길, 즉 수학적인 '마술적 속임수'를 발명했습니다. 이 논문은 그의 발견 150주년을 기념하며, 루카스가 어떻게 체스판과 특정한 숫자 패턴을 사용하여 불가능해 보였던 퍼즐을 해결했는지 설명합니다. 오늘날 컴퓨터는 루카스가 발견한 바로 그 논리를 사용하여 세상에서 가장 큰 알려진 소수들을 찾아내고 있으며, 이는 19세기의 아이디어가 여전히 현대 수학을 움직이는 엔진임을 증명합니다.

---

39자리의 거인과 체스판의 마법사

2026년은 매우 특별한 숫자인 M127, 즉 2¹²⁷ − 1의 탄생 기념일입니다. 이 숫자를 풀어서 쓰면 다음과 같은 긴 숫자의 나열이 됩니다: 170,141,183,460,469,231,731,687,303,715,884,105,727. 이것은 39자리의 숫자이며, 1876년에 에두아르 루카스는 이것이 소수임을 증명했습니다. 이는 엄청난 사건이었습니다. 이후 75년 동안 이 숫자는 전 세계에서 알려진 가장 큰 소수였습니다. 더욱 놀라운 점은, 루카스가 컴퓨터나 계산기, 혹은 어떤 기계적 도움도 없이 오로지 맨손으로 이 일을 해냈다는 것입니다. 그는 마치 마술 쇼처럼 이 일을 해냈습니다.

루카스는 다재다능한 인물이었습니다. 그는 유명한 '하노이의 탑' 퍼즐을 발명했고, '점과 상자(Dots and Boxes)' 게임도 만들었습니다. 하지만 그의 가장 유명한 기술은 M127이 소수임을 증명하는 방법이었습니다. 보통 어떤 숫자가 소수인지 증명하려면 그 숫자가 더 작은 숫자로 나누어지는지 확인해야 합니다. 하지만 M127은 너무 커서 이 작업을 수행하는 것은 영원히 걸릴 일입니다. 대신, 루카스는 자신이 발견한 특별한 숫자 수열을 사용했는데, 이를 '루카스 수열(Lucas sequence)'이라 불렀습니다(물론 그의 이름을 따서 말이죠). 이 수열을 유명한 피보나치 수열이 성장하는 방식과 비슷하지만 약간의 변형이 가미된 방식으로, 특정 패턴에 따라 성장하는 숫자들의 가족이라고 생각하면 됩니다.

루카스는 이 수열에서 특정 숫자를 가져와 M127로 나누었을 때, 만약 M127이 소수라면 그 결과가 0이 되어야 한다는 사실을 깨달았습니다. 문제는 그가 확인해야 할 숫자가 100자리가 넘을 정도로 너무나 컸다는 점입니다! 종이에 적거나 계산하기에는 너무나 컸습니다. 그래서 루카스는 자신의 거실을 게임판으로 바꾸었습니다. 그는 숫자를 나타내는 1과 빈 칸을 나타내는 0을 사용하여 127 × 127 체스판을 활용했습니다.

그의 '게임'은 다음과 같이 진행되었습니다: 그는 체스 폰(pawn)을 숫자 1로, 빈 칸을 0으로 사용했습니다. 그는 숫자를 이진법으로 인코딩하여 체스판 위에 폰을 배치했습니다. 그런 다음, 그는 컴퓨터가 하는 방식과 똑같이 숫자를 '제곱'하고 크기를 줄여나가는 규칙에 따라 폰을 움직였습니다. 그는 아무것도 적지 않았습니다. 그저 폰을 움직였을 뿐입니다. 약 120번의 폰 이동과 제곱 과정을 거친 후, 그는 마지막 행을 확인했습니다. 만약 폰들이 딱 맞게 정렬되어 있다면(즉, 결과가 0이라면), M127은 확실히 소수입니다. 그리고 실제로 그랬습니다! 그는 종이에 단 하나의 숫자도 적지 않고 이를 증명해 냈습니다.

현대의 엔진: 체스판에서 슈퍼컴퓨터까지

이 논문은 루카스의 방법이 단순한 일회성 기술이 아니라, 오늘가 우리가 가장 큰 소수를 찾는 기초가 되었음을 설명합니다. 이 방법은 현재 **루카스-레머 테스트(Lucas–Lehmer test)**라고 불립니다. 루카스는 폰을 사용하여 이 작업을 수행했지만, 현대의 컴퓨터는 이와 동일한 테스트를 사용하여 수천만 자리의 숫자를 가진 소수를 찾아냅니다. 2024년 10월에 발견된 현재의 기록 보유자는 41,024,320개의 십진수 자리를 가진 숫자입니다. 이는 사람이 소리 내어 읽는 데만 몇 년이 걸릴 정도로 긴 숫자입니다.

이 테스트의 핵심 비결은 **체비쇼프 다항식(Chebyshev polynomial)**이라는 특별한 수학적 도구입니다. 이 다항식을 숫자를 받아 제곱하고 2를 빼는 기계라고 생각할 수 있습니다. 만약 이 기계에 숫자 4를 넣고 이 과정을 계속 반복한다면, 다음과 같은 수열을 얻게 됩니다: 4, 14, 194, 37,634 등등. 루카스-레머 테스트는 만약 소수 p가 있을 때, 이 수열의 **(p-2)**번째 숫자를 계산하여 그것이 2ᵖ − 1로 나누어떨어진다면, 2ᵖ − 1은 소수라고 말합니다.

논문은 이 과정이 왜 작동하는지를 보여주기 위해 수학적 과정을 따라갑니다. 여기에는 숫자가 시계처럼 순환하는 '유한체(finite fields)'라는 일종의 '가상의' 숫자 영역이 포함됩니다. 저자는 이 과정이 특별한 원 안에서 바퀴를 돌리는 것과 같다고 보여줍니다. 만약 바퀴가 정확한 횟수만큼 돌아 특정 지점에 착륙한다면, 그것은 그 숫자가 소수임을 증명합니다. 이 수학적 과정은 엄격하게 검증되고 재검증되었기에, 우리는 이 테스트가 정확하다는 것을 절대적으로 확신할 수 있습니다.

이것이 중요한 이유

논문은 도구는 변했을지라도 수학은 변하지 않았음을 상기시키며 결론을 맺습니다. 1876년에 에두아르 루카스는 39자리의 숫자가 소수임을 증명하기 위해 체스판 위에서 폰을 움직였습니다. 오늘날 '거대 인터넷 메르센 소수 탐색(GIMPS)'의 슈퍼컴퓨터들은 수백만 자리의 소수를 찾기 위해 정확히 동일한 알고리즘을 실행하고 있습니다. 숫자를 제곱하는 것, 특별한 다항식 x² − 2, 그리고 이러한 유한체에서 숫자가 행동하는 방식 사이의 관계가 루카스의 체스판과 우리의 현대 디지털 발견을 모두 움직이는 엔진입니다.

이는 19세기의 영리한 아이디어가 여전히 21세기의 가장 진보된 기술을 움직일 수 있다는 아름다운 증거입니다. 루카스는 단순히 숫자를 찾아낸 것이 아니라, 숫자의 숨겨진 구조를 보는 방법, 즉 오늘날 수학의 경계를 넓히는 데 여전히 사용되고 있는 방법을 찾아낸 것입니다. 그리고 이 모든 것은 한 명의 프랑스 수학자, 하나의 체스판, 그리고 매우 호기심 많은 마음에서 시작되었습니다.