그레이엄 재배열 추측 55년 만에 해결 — 모듈러 연산 뜻과 성질 총정리

📐 수학 이야기

모듈러 연산 위에서 정의된 그레이엄 재배열 추측이 55년 만에 해결됐다. 1971년 문제의 뜻과 네 편의 논문, 무작위 방법의 원리, 그리고 모듈러 연산 뜻과 성질·계산 예제를 고등수학 눈높이로 정리했다.

과학 전문지 콴타 매거진은 9월 28일, 수학자 로널드 그레이엄이 1971년에 던진 '재배열 추측'이 젊은 수학자들의 논문 네 편으로 마침내 해결됐다고 보도했다. 이 문제의 무대는 시계처럼 일정한 수에 이르면 처음으로 되돌아가는 수의 세계, 곧 모듈러 연산이다. 뉴스의 핵심과 함께, 코딩 테스트와 암호에서 매일 쓰이는 모듈러 연산의 뜻과 성질을 정리한다.

그레이엄 재배열 추측, 무엇이 풀렸나?

그레이엄은 미국수학회 회장을 지낸 수학자이자 국제저글러협회 회장을 지낸 저글러였다. 그의 질문은 이렇다. 0이 아닌 서로 다른 수 몇 개를 고른 뒤, 순서를 잘 바꾸면 앞에서부터 차례로 더한 합들이 모두 다르게 만들 수 있을까. 저글링으로 말하면, 공마다 공중에 머무는 시간이 다를 때 두 공이 같은 박자에 떨어지지 않도록 던지는 순서를 찾는 문제다.

모두 양수라면 합이 계속 커지니 답은 당연히 '그렇다'다. 어려운 건 수가 소수 p에서 0으로 되돌아가는 세계에서다. 2022년 뮈예세르와 포크롭스키가 거의 모든 수를 고른 큰 집합의 경우를, 2024년 9월 크라비츠와 베데르트가 아주 작은 집합의 경우를 풀었고, 2025년 8월 다섯 명의 공동 논문이 범위를 넓혔다. 마지막 남은 중간 크기 집합은 2026년 2월 본 대학의 리자 자우어만과 시카고 대학의 후이 투안 팜이 27쪽 논문으로 해결했다.

네 편을 관통하는 열쇠는 무작위성이다. 먼저 순서를 무작위로 섞고, 문제가 생긴 곳만 고친다. 자우어만과 팜은 푸리에 해석으로 '무작위로 더한 합은 어느 한 값에 몰리지 않는다'는 반집중 성질을 보여, 고칠 수 없는 나쁜 사건이 일어날 확률이 충분히 작다는 것을 증명했다. 무작위 순서의 90% 이상을 이런 식으로 고칠 수 있었다. 다만 증명은 p가 아주 큰 경우에 성립하므로, 모든 소수에 대한 완전한 확인은 남은 과제다.

모듈러 연산 뜻 — 나머지로 계산하는 세계

모듈러 연산은 정수를 어떤 양의 정수 n으로 나눈 나머지만 남겨 계산하는 방식이다. 나눗셈 정리에서 출발한다.

$$a = qn + r,\quad 0 \le r < n \quad\Longrightarrow\quad a \bmod n = r$$

몫 q는 버리고 나머지 r만 남기는 것이 모듈러 연산의 정의

가장 친숙한 예가 시계다. 9시에서 5시간 뒤는 \(14 \bmod 12 = 2\), 즉 2시다. 요일도 같다. 오늘이 금요일이면 100일 뒤는 \(100 \bmod 7 = 2\)이므로 금요일에서 이틀 뒤인 일요일이다. 음수도 정의대로 처리한다. \(-7 = (-3)\times 3 + 2\)이므로 \(-7 \bmod 3 = 2\)다. 주의할 점은 프로그래밍 언어마다 % 연산자가 음수에서 다르게 동작한다는 것이다. 파이썬은 2를, C와 자바는 -1을 돌려준다.

모듈러 연산 성질 — 덧셈·곱셈은 되고 나눗셈은 안 되는 이유

모듈러 연산의 가장 중요한 성질은 '먼저 나머지를 구해도 결과가 같다'는 것이다. \(a = q_1 n + r_1\), \(b = q_2 n + r_2\)라 하면 다음이 성립한다.

$$a + b = (q_1 + q_2)\,n + (r_1 + r_2)$$

$$ab = (q_1 q_2 n + q_1 r_2 + q_2 r_1)\,n + r_1 r_2$$

n의 배수 부분은 나머지에 영향을 주지 않는다

따라서 \((a+b) \bmod n = (r_1 + r_2) \bmod n\), \((ab) \bmod n = (r_1 r_2) \bmod n\)이다. 뺄셈도 같다. 예를 들어 \(123456 \times 789\)를 7로 나눈 나머지는 곱을 직접 계산할 필요 없이 \(123456 \bmod 7 = 4\), \(789 \bmod 7 = 5\)에서 \(4 \times 5 = 20\), \(20 \bmod 7 = 6\)으로 끝난다. 거듭제곱도 쉬워진다. \(2^3 = 8\)을 7로 나눈 나머지가 1이므로 \(2^{99} = (2^3)^{33}\)의 나머지는 1이고, \(2^{100} \bmod 7 = 2\)다. 코딩 테스트에서 큰 답을 1,000,000,007로 나눈 나머지로 출력하게 하는 것도 이 성질 덕분에 중간 계산이 넘치지 않기 때문이다.

모듈러 연산에서 나눗셈은 다르다. 4로 나눈 나머지 세계에서 \(2 \times 3\)과 \(2 \times 1\)은 둘 다 나머지가 2지만, 양변을 2로 나누면 3과 1이 되어 나머지가 다르다. 나눗셈이 가능하려면 나누는 수와 n이 서로소여서 곱셈의 역원이 있어야 한다. n이 소수 p이면 0이 아닌 모든 수가 역원을 가지므로, 그레이엄 추측처럼 소수 p를 쓰는 문제는 깔끔한 구조 위에서 출발한다.

모듈러 연산으로 다시 읽는 그레이엄 추측

고른 수를 순서대로 \(a_1, a_2, \dots, a_k\)라 하고, 부분합을 p로 나눈 나머지로 정의한다.

$$S_j = (a_1 + a_2 + \cdots + a_j) \bmod p,\qquad j = 1, 2, \dots, k$$

$$S_i = S_j\ (i < j) \iff (a_{i+1} + \cdots + a_j) \bmod p = 0$$

부분합이 겹친다는 것은 중간 구간의 합이 p의 배수라는 뜻

p = 7, 고른 수가 2, 3, 4라고 해 보자. 2, 3, 4 순서로 더하면 부분합의 나머지가 2, 5, 2로 겹친다. 3 + 4 = 7이 7로 나누어떨어지기 때문이다. 순서를 3, 2, 4로 바꾸면 3, 5, 2로 모두 다르다. 여섯 가지 순서를 모두 따져 보면 넷이 조건을 만족한다. 그레이엄 추측은 소수 p와 0이 아닌 수의 어떤 집합을 고르더라도 이런 '좋은 순서'가 항상 하나 이상 존재한다는 주장이고, 이번에 충분히 큰 p에 대해 증명이 완성됐다.

나는 이 기사를 읽고 위의 예를 손으로 전부 세어 봤다. 수가 세 개뿐인데도 '어떤 구간의 합이 7의 배수가 되는가'를 일일이 확인해야 했고, 수가 수천 개라면 순서의 개수가 천문학적으로 늘어난다. 그 많은 경우를 하나하나 만들지 않고 '무작위로 고르면 대부분 괜찮다'는 확률 논증으로 존재를 보이는 방식이, 고등학교 수준의 모듈러 연산과 확률이 만나는 지점이라 특히 인상적이었다.

함께 읽으면 좋은 글

페르마의 소정리 증명과 예제 — RSA 암호까지 유클리드 호제법 원리와 증명, 최소공배수까지 정리 김정한 샌드위치 추측 20년 만에 증명 — 그래프 이론 뜻과 랜덤 그래프 총정리

참고 자료

Quanta Magazine — Mathematicians Harness Randomness To Crack a 55-Year-Old Conjecture (2026-09-28) Pham, Sauermann — arXiv:2602.15797 Bedert, Kravitz — arXiv:2409.07403 Müyesser, Pokrovskiy — arXiv:2204.09666