An Intuitionistic Glance at Primes

당신이 거대한 숫자 더미를 세 개의 뚜렷한 상자, 즉 단위수(The Unit), 소수(The Primes), 그리고 **합성수(The Composites)**로 분류하려는 탐정이라고 상상해 보십시오. 대부분의 사람들은 이것이 단순한 수학 게임이라고 생각하지만, 2026년 7월 밀란 로스코(Milan Rosko)가 작성한 이 논문은 더 깊은 질문을 던집니다. 우리는 단순히 추측하는 것이 아니라, 어떻게 한 숫자가 특정 상자에 속한다는 것을 실제로 증명할 수 있는가?

이 논문은 "직관주의 논리"(증명해야 할 것을 단순히 참이라고 말하는 것이 아니라, 반드시 작업 과정을 보여주어야 하는 엄격한 사고 방식)의 세계에서, 어떤 숫자가 "합성수"임을 증명하는 방식은 "소수"임을 증명하는 방식과 완전히 다르다고 주장합니다.

두 가지 탐정 스타일: 발견하기 vs 소진하기

숫자 6을 생각해 봅시다. 이것이 합성수임을 증명하려면, 단지 그것을 만드는 곱셈 쌍 하나만 찾으면 됩니다. 당신은 "아하! 2 곱하기 3은 6이다!"라고 외칩니다. 당신은 **긍정적 증인(positive witness)**을 찾았습니다. 증거를 발견한 것입니다. 이것은 "존재적(existential)" 탐색이라고 논문은 부릅니다. 잃어버린 열쇠를 찾는 것과 같습니다. 일단 발견하면 임무는 끝납니다.

이제 숫자 5를 살펴보십시오. 이것이 소수임을 증명하려면, 단순히 친구를 찾는 것이 아니라, 5를 곱해서 만들 수 있는 모든 가능한 숫자 쌍을 확인하여 그중 어느 것도 작동하지 않음을 증명해야 합니다. 당신은 가능한 모든 용의자 목록을 전부 확인해야 합니다. 당신은 "내적 인수분해의 결여(lack of interior factorization)"를 보여줌으로써 소수를 증명하는 것입니다. 이를 논문에서는 "유한한 반박(bounded refutation)"이라고 부릅니다.

핵심 발견: 이 논문은 당신이 어떤 숫자를 선택하더라도, 그 숫자가 어느 상자에 들어갈지 항상 결정할 수 있다고 증명합니다. 당신은 추측할 필요가 없습니다. 그저 유한한 탐색을 수행하면 됩니다. 만약 인수 쌍을 찾는다면 합성수입니다. 만약 그 숫자까지의 모든 가능한 쌍을 확인했는데 아무것도 없다면 소수입니다. (숫자 1은 이 두 상자 어디에도 속하지 않는 특별한 경우입니다.)

"캐처(Catcher)" 게임과 체(Sieve)

논문은 **"유한 캐처(Finite Catcher)"**라는 재미있는 게임을 소개합니다. 몇 개의 특정 숫자(예: 2와 3)로 만들어진 그물을 상상해 보십시오. 합성수를 그물에 던집니다. 만약 그 숫자가 2와 3으로 만들어졌다면(예: 6 또는 12), 그물에 걸립니다. 하지만 숫자 25를 던진다면 어떻게 될까요? 그물은 놓치고 맙니다! 왜일까요? 25는 5로 만들어졌는데, 당신의 그물에는 5가 없기 때문입니다.

논문은 **"유클리드 탈출(Euclidean Escape)"**이라는 영리한 트릭을 보여줍니다. 당신의 그물이 아무리 크더라도, 그 구멍 사이로 빠져나갈 숫자를 언제나 만들어낼 수 있습니다. 이는 유한한 그물로는 모든 합성수를 다 잡을 수 없다는 것을 증명합니다.

그렇다면 어떻게 그들을 모두 잡을 수 있을까요? 논문은 **"재귀적 체(Recursive Sieve)"**를 설명합니다.

1. 빈 그물에서 시작합니다.
2. 숫자들을 던집니다. 살아남은(그물을 통과한) 첫 번째 숫자는 2입니다.
3. 2가 살아남았으므로, 우리는 2가 소수임을 압니다. 따라서 2를 우리 그물에 추가합니다.
4. 이제 새로운 그물(2의 배수를 잡는 그물)에 숫자를 던집니다. 다음 생존자는 3입니다. 3을 그물에 추가합니다.
5. 계속 진행합니다. 다음은 5, 그다음은 7 등이 됩니다.

이 과정은 소수의 목록을 하나씩 구축합니다. 논문은 처음 $k$개의 소수로 만들어진 그물을 항상 통과하는 첫 번째 합성수는 다음 소수의 제곱(예: $5^2 = 25$)이라고 증명합니다.

이 논문이 배제하는 것들 ("불가 영역")

이 논문은 자신이 주장하지 않는 것에 대해서도 매우 신중합니다.

• 숫자 1에 대해 "소수가 아니다"가 자동으로 "합성수이다"를 의미한다는 생각을 배제합니다. 엄격한 논리에서 1은 그 자체로 특별한 범주입니다. "소수가 아니니 합성수임에 틀림없다"라고 말할 수 없습니다. 1은 둘 다 아닙니다.
• 모든 수학적 진리를 즉각적으로 결정할 수 있는 단 하나의 완벽한 "범용 기계"를 가질 수 있다는 아이디어에 반대합니다. 논문은 **라이스의 정리(Rice's Theorem)**라는 유명한 결과를 사용하여, 우리가 특정 숫자(예: "25는 합성수인가?")를 확인할 수는 있지만, 숫자의 모든 가능한 패턴(예: "쌍둥이 소수는 무한히 존재하는가?")의 진위를 결정하는 단일 기계를 만드는 것은 불가능함을 보여줍니다.
• 수학 시스템 내부에서 소수임을 증명하는 것이 우리가 실생활에서 사용하는 "실제" 숫자와 일치함을 증명하는 것과 같다는 생각을 거부합니다. 논문은 게임의 규칙(구문론, syntax)과 게임의 의미(의미론, semantics)를 구분합니다. 컴퓨터는 규칙을 완벽하게 따라 특정 숫자가 소수임을 증명할 수 있지만, 그것이 자동으로 컴퓨터가 현실 세계에서 "소수"가 무엇인지 이해한다는 것을 의미하지는 않습니다. 그것을 위해서는 추가적인 해석 단계가 필요합니다.

얼마나 확실한가?

이 논문은 단순히 시뮬레이션하거나 제안하는 것이 아니라 수학적으로 증명되었습니다.

• 숫자의 분류(1, 소수, 합성수)는 **결정 가능(decidable)**합니다. 즉, 어떤 숫자를 입력하더라도 항상 정답을 주는 보장된 단계별 레시피가 존재합니다.
• "체(Sieve)" 방법은 **구성적(constructive)**입니다. 단순히 소수가 존재한다고 말하는 것이 아니라, 단계별로 소수를 구축하는 방법을 정확히 보여줍니다.
• 논문이 논하는 한계들(예: 모든 패턴을 결정하는 범용 기계를 가질 수 없음)은 확립된 논리(괴델의 불완전성 정리와 라이스의 정리)에 기반한 엄격한 증명입니다.

소수의 "신기루(Mirage)"

논문은 아름다운 은유로 끝을 맺습니다. 논문은 합성수가 숫자들을 곱하여 만든 견고한 벽과 같다고 말합니다. 소수는 그 벽에 있는 구멍입니다.

• 합성수는 그것을 구성하는 요소(인수)들을 볼 수 있기 때문에 쉽게 식별됩니다.
• 소수는 그것이 아닌 것에 의해 정의됩니다. 그것은 어떤 벽돌도 맞지 않는 구멍입니다.

논문은 우리가 단 하나의 구멍을 확인하여 그것이 구멍인지 쉽게 확인할 수 있지만(탐색이 유한하기 때문), 그 구멍들이 모여 만드는 전체적인 패턴은 미스터리라고 결론짓습니다. 우리는 벽의 작은 부분들을 검증할 수는 있지만, 구멍들이 어디에 있는지에 대한 무한한 패턴은 우리가 단 하나의 단순한 규칙으로 완전히 포착할 수 없는 "신기루"로 남아 있습니다.

요약하자면, 우리에게는 어떤 숫자라도 확인할 수 있는 완벽하고 작동하는 손전등이 있습니다. 하지만 숫자라는 무한한 숲 전체의 지도는 다른 이야기입니다. 이 논문은 우리가 우리의 손전등으로 증명할 수 있는 것과, 아름답지만 증명되지 않은 미스터리로 남겨진 것 사이의 경계를 긋고 있습니다.