정수론(Number theory)

정수론은 1, 2, 3, …과 같은 정수의 성질을 묻는 수학입니다. 질문은 초등학생도 알아들을 만큼 쉽습니다. 어떤 수가 어떤 수로 나누어떨어지는가, 더 쪼갤 수 없는 수는 얼마나 많고 어떻게 흩어져 있는가, 나눗셈의 나머지는 어떤 규칙을 따르는가, 어떤 방정식이 정수 해를 갖는가. 그런데 답을 찾는 데 수백 년이 걸린 질문이 많고, 그 과정에서 수학의 큰 도구들이 태어났습니다. 가우스는 "수학은 과학의 여왕이고, 정수론은 수학의 여왕"이라고 말했다고 전해집니다.

출발점은 나누어떨어짐입니다. b = a × k를 만족하는 정수 k가 있으면 "a가 b를 나눈다"고 하고 a를 b의 약수라 합니다. 12의 약수⁠(divisor)⁠는 1, 2, 3, 4, 6, 12입니다. 1과 자기 자신 말고는 약수가 없는 2 이상의 수가 소수이고, 2 이상의 모든 자연수⁠(natural number)⁠는 소수의 곱으로 단 한 가지 방법으로 쪼개집니다. 예를 들어 $360 = 2^3 \cdot 3^2 \cdot 5$이고, 순서를 바꾸는 것 말고 다른 분해는 없습니다(소인수분해⁠(prime factorization)⁠, 산술의 기본정리⁠(fundamental theorem of arithmetic)⁠). 기원전 300년 무렵 유클리드의 『원론』 7–9권에 이미 두 수의 최대공약수⁠(greatest common divisor)⁠를 구하는 유클리드 호제법⁠(Euclidean algorithm)⁠과, 소수가 끝없이 많다는 증명이 실려 있습니다. 분해가 하나뿐이라는 사실을 오늘날의 형태로 분명하게 증명한 사람은 가우스입니다.

둘째 기둥은 나머지입니다. a − b가 m으로 나누어떨어지면 "a와 b는 m을 법으로 합동⁠(congruence)⁠"이라 하고 $a \equiv b \pmod m$로 씁니다. 시계가 13시를 1시로 적는 것이 12를 법으로 한 셈입니다(모듈러 연산⁠, modular arithmetic⁠). 이 기호는 가우스가 1801년, 스물네 살에 펴낸 『산술 연구』(Disquisitiones Arithmeticae)에서 처음 썼습니다. 나머지만 보면 끝없이 많은 정수가 m개의 칸으로 줄어들고, 덧셈과 곱셈은 칸 사이의 계산이 됩니다. 페르마가 1640년 편지에 적은 정리(페르마의 소정리⁠, Fermat's little theorem⁠)에 따르면 p가 소수일 때 $a^p \equiv a \pmod p$입니다. 실제로 $2^7 = 128 = 7 \cdot 18 + 2$이니 128을 7로 나누면 2가 남습니다. 오일러는 이 정리를 소수가 아닌 법으로 넓혔고(오일러 피 함수⁠, Euler's totient function⁠), 가우스는 오일러와 르장드르가 추측한 이차 상호 법칙⁠(quadratic reciprocity)⁠을 1796년에 처음 증명해 이 책에 실었습니다.

셋째 기둥은 정수 해입니다. 3세기 무렵 알렉산드리아의 수학자 디오판토스는 『산술』(Arithmetica)에서 여러 방정식의 유리수⁠(rational number)⁠ 해를 구했고, 그래서 오늘날 정수(또는 유리수) 해만 찾는 방정식을 디오판토스 방정식⁠(Diophantine equation)⁠이라 부릅니다. $x^2 + y^2 = z^2$의 해 (3, 4, 5), (5, 12, 13), …은 피타고라스 세 쌍⁠(Pythagorean triples)⁠입니다. $x^2 - 2y^2 = 1$은 (3, 2), (17, 12), (99, 70), …처럼 끝없이 많은 해를 갖고, 이런 꼴의 펠 방정식⁠(Pell equation)⁠을 628년 인도의 브라마굽타가 체계적으로 다루었습니다. 그는 $x^2 - 92y^2 = 1$의 해 (1151, 120)을 1년 안에 찾는 사람은 수학자라 할 만하다고 적었습니다. 페르마는 1637년 무렵 바셰가 펴낸 『산술』 라틴어판의 여백에, n이 3 이상이면 $x^n + y^n = z^n$을 만족하는 양의 정수 x, y, z는 없으며 놀라운 증명을 찾았지만 여백이 좁아 적지 않는다고 썼습니다. 이 페르마의 마지막 정리⁠(Fermat's Last Theorem)⁠는 1994년 영국의 앤드루 와일스가 리처드 테일러의 도움을 받아 완성한 증명으로 350여 년 만에 풀렸습니다.

디오판토스 방정식은 하나하나가 제각각이라 어렵습니다. 힐베르트는 1900년에 발표한 문제 목록의 10번째로, 정수 계수 다항 방정식이 정수 해를 갖는지 판정하는 일반적인 절차를 찾으라고 했습니다. 1970년 소련의 유리 마티야세비치는 마틴 데이비스, 힐러리 퍼트넘, 줄리아 로빈슨의 작업을 이어받아 그런 절차가 있을 수 없음을 증명했습니다. 이 판정 불가능성은 정지 문제⁠(halting problem)⁠와 뿌리가 같습니다.

작은 예: 두 제곱수의 합

세 기둥이 한꺼번에 움직이는 예를 봅시다. 어떤 수가 두 제곱수⁠(perfect square)⁠의 합일까요? 5 = 1 + 4, 13 = 4 + 9, 25 = 9 + 16인데 3, 7, 11, 19는 아무리 해도 안 됩니다. 이유는 나머지에 있습니다. 짝수의 제곱은 4로 나누어떨어지고 홀수의 제곱은 4로 나누면 1이 남으니, 두 제곱수의 합을 4로 나눈 나머지⁠(remainder)⁠는 0, 1, 2 가운데 하나이고 3은 될 수 없습니다. 그러니 4로 나누어 3이 남는 수는 두 제곱수의 합이 될 수 없습니다. 거꾸로 페르마는 1640년 크리스마스에 메르센에게 보낸 편지에서, 4로 나누어 1이 남는 소수는 언제나 두 제곱수의 합이라고 주장했습니다. 페르마는 증명을 남기지 않았고, 알려진 첫 완전한 증명은 1740년대 말 오일러가 내놓았습니다.

n = .

완전한 규칙은 이렇습니다. n을 소인수분해했을 때 4로 나누어 3이 남는 소수가 모두 짝수 번씩 들어 있으면, 그리고 그때에만 n은 두 제곱수의 합입니다. 방법의 수도 셀 수 있습니다. (a, b)의 순서와 부호를 따진 개수 r(n)은, n의 약수 가운데 4로 나누어 1이 남는 것의 개수 $d_1(n)$에서 3이 남는 것의 개수 $d_3(n)$를 뺀 값의 4배입니다(1829년 야코비). 지금 n에서는

이제 n 하나가 아니라 1부터 N까지를 한꺼번에 봅시다. r(1) + r(2) + ⋯ + r(N)은 반지름 √N인 원 안(경계 포함, 원점 제외)의 격자점 개수이고, 격자점 하나가 넓이⁠(area)⁠ 1인 칸 하나를 차지하니 이 합은 원의 넓이 πN에 가깝습니다. 그림에서는 그러니 N이 커질수록 r(1)부터 r(N)까지의 평균⁠(mean)⁠은 원주율⁠(pi)⁠ π에 다가갑니다. 같은 합을 위의 약수 공식으로 세면 사정이 달라 보입니다. 4로 나누어 1이 남는 수 d는 N 이하에서 약 N/d번 약수로 나타나 +4씩, 3이 남는 d는 −4씩 보태므로 합은 약 $4N(1 - \tfrac13 + \tfrac15 - \cdots)$입니다. 두 셈을 맞추면 $1 - \tfrac13 + \tfrac15 - \tfrac17 + \cdots = \tfrac{\pi}{4}$가 나옵니다. 14세기 인도의 마다바가 찾고 17세기에 라이프니츠가 다시 찾은 급수⁠(series)⁠가 정수의 나눗셈 속에 숨어 있던 셈입니다. 격자점 개수와 πN의 차이가 얼마나 작은지는 가우스의 원 문제라 불리며, 아직 완전히 풀리지 않았습니다.

해석적 정수론과 대수적 정수론

이렇게 넓이, 극한⁠(limit)⁠, 적분⁠(integral)⁠, 복소함수⁠(complex function)⁠ 같은 연속적인 도구로 정수의 평균적인 모습을 재는 갈래를 해석적 정수론이라 합니다. 오일러는 1737년, s > 1일 때 모든 자연수에 대한 합이 모든 소수에 대한 곱과 같다는 오일러 곱⁠(Euler product)⁠ $\sum_{n} n^{-s} = \prod_{p} (1 - p^{-s})^{-1}$을 찾았습니다. 곱을 풀면 소인수분해가 하나뿐이라는 사실 때문에 각 $n^{-s}$가 꼭 한 번씩 나오기 때문입니다. s를 1로 줄이면 왼쪽은 한없이 커지는데 소수가 유한 개라면 오른쪽은 유한하니, 이것으로 소수가 끝없이 많다는 사실을 새 방법으로 보였습니다(리만 제타 함수⁠(Riemann zeta function)⁠, 바젤 문제⁠(Basel problem)⁠). 디리클레는 1837년 같은 생각을 나머지별로 쪼개어, a와 m의 최대공약수가 1이면(서로소⁠(coprime)⁠이면) 수열 a, a + m, a + 2m, … 가운데 소수가 끝없이 많다는 것을 증명했습니다. 리만은 1859년의 짧은 논문에서 소수의 개수를 제타 함수⁠(zeta function)⁠의 영점⁠(zero)⁠과 잇는 식을 내놓았고, 그 영점의 위치에 대한 추측(리만 가설⁠, Riemann hypothesis⁠)은 지금도 풀리지 않았습니다. x 이하의 소수 개수와 $x/\ln x$의 비가 x가 커질수록 1에 다가간다는 소수 정리⁠(prime number theorem)⁠는 1896년 자크 아다마르와 샤를장 드 라 발레 푸생이 이 길로 증명했습니다.

디리클레의 정리를 눈으로 확인해 봅시다. 소수를 m = 으로 나눈 나머지별로, $N = 10^e$(e = ) 이하에서 세었습니다.

m = 4로 두면 흥미로운 일이 보입니다. 나머지 3 쪽이 거의 언제나 조금 앞섭니다. 체비쇼프가 1853년 편지에서 처음 지적한 이 치우침은 N = 26,861에 이르러서야 처음 뒤집힙니다. 비율은 결국 반반으로 가고, 1914년 리틀우드는 선두가 끝없이 여러 번 바뀐다는 것도 증명했습니다. 그래도 3 쪽이 앞서는 x가 압도적으로 많습니다. 1994년 루빈스타인과 사낙은 리만 가설의 일반화와 또 하나의 가설을 받아들이면, 로그 눈금으로 잰 비율로 약 99.6%의 x에서 3 쪽이 앞선다는 것을 보였습니다.

다른 갈래는 수의 세계 자체를 넓힙니다. 가우스는 1832년, a와 b가 정수인 a + bi 꼴의 복소수(가우스 정수⁠, Gaussian integer⁠)에서도 소인수분해가 한 가지뿐임을 보였습니다. 이 세계에서는 $5 = (2 + i)(2 - i)$처럼 4로 나누어 1이 남는 소수가 더 쪼개지고, 그 쪼개짐을 풀어 쓰면 $5 = 2^2 + 1^2$입니다. 일반적으로 소수 p가 $(a + bi)(a - bi)$로 쪼개지는 것과 $p = a^2 + b^2$은 같은 말이고, 4로 나누어 1이 남는 소수가 바로 이렇게 쪼개지는 홀수 소수입니다. 두 제곱수 정리가 이렇게 설명됩니다. 그런데 $a + b\sqrt{-5}$ 꼴의 수에서는 $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$처럼 더 쪼갤 수 없는 수로의 분해가 두 가지나 됩니다. 1840년대 독일의 에른스트 쿰머는 페르마의 마지막 정리를 공격하다 이 문제에 부딪혀 '이상수⁠(ideal number)⁠'를 도입했고, 데데킨트는 1871년 이를 아이디얼⁠(ideal)⁠이라는 개념으로 다듬었습니다. 이렇게 새 수 체계⁠(number system)⁠의 산술을 군이나 환 같은 대수 구조로 다루는 갈래가 대수적 정수론입니다. 와일스의 증명도 타원곡선⁠(elliptic curve)⁠과 모듈러 형식⁠(modular form)⁠이라는 두 세계를 잇는 대수적 정수론⁠(algebraic number theory)⁠의 결과입니다.

쓸모없던 수학에서 암호로

20세기 초 케임브리지의 하디와 리틀우드는 해석적 정수론⁠(analytic number theory)⁠을 정교한 기술로 만들었고, 1913년 인도에서 편지를 보낸 라마누잔과 함께 분할수⁠(partition number)⁠ p(n)의 놀랍도록 정확한 근사식을 찾았습니다(1918). 하디는 1940년 『어느 수학자의 변명』에, 정수론이나 상대성 이론이 전쟁에 쓰일 곳은 아직 아무도 찾지 못했고 앞으로 오랫동안 찾지 못할 것 같다고 적었습니다. 그 예상은 빗나갔습니다. 1976년의 디피–헬먼 키 교환⁠(Diffie–Hellman key exchange)⁠과 1977년의 RSA는 큰 수의 거듭제곱을 어떤 수로 나눈 나머지는 빨리 계산되고 소수 판정⁠(primality test)⁠도 빠르지만, 큰 수를 소인수분해하거나 거꾸로 지수를 알아내는 일은 지금까지 알려진 방법으로는 매우 느리다는 비대칭에 기댄 암호입니다. 이 어려움은 증명된 것이 아니라 오랜 시도가 뒷받침하는 믿음입니다. 오늘날 인터넷의 보안 연결 대부분이 이런 정수론 위에 서 있습니다. 상대성 이론 역시 일반 상대성 이론⁠(general relativity)⁠의 시계 보정으로 GPS를 움직입니다.

풀리지 않은 질문도 쉽게 말할 수 있습니다. 차가 2인 소수 쌍은 끝없이 많은가(쌍둥이 소수⁠, twin primes⁠), 4 이상의 모든 짝수는 두 소수의 합인가(1742년 골드바흐와 오일러가 주고받은 편지에서 나온 추측), 리만 가설은 참인가. 울람 나선⁠(Ulam spiral)⁠처럼 소수를 늘어놓기만 해도 아직 다 설명되지 않은 무늬가 보입니다.

이어지는 곳. 나누어떨어짐의 길은 유클리드 호제법, 소인수분해, 연분수⁠(continued fraction)⁠로, 나머지의 길은 모듈러 연산, 중국인의 나머지 정리⁠(Chinese remainder theorem)⁠, 원시근⁠(primitive root)⁠, 오일러 피 함수, 원 위의 곱셈표⁠(times tables on a circle)⁠로, 소수의 길은 소수, 소수 정리, 리만 제타 함수, 쌍둥이 소수, 소수 판정으로 이어집니다. 정수 해의 길에는 피타고라스 세 쌍, 피보나치 수열⁠(Fibonacci sequence)⁠, 황금비⁠(golden ratio)⁠가 있고, 정수와 실수⁠(real number)⁠의 경계에는 무리수⁠(irrational number)⁠와 대수적 수와 초월수⁠(algebraic and transcendental numbers)⁠가 있습니다. 세는 문제와 만나는 곳이 분할수, 파스칼의 삼각형⁠(Pascal's triangle)⁠, 생성함수⁠(generating function)⁠이고, 1의 거듭제곱근⁠(roots of unity)⁠은 나머지 계산을 원 위의 회전⁠(rotation)⁠으로 바꿉니다. 수를 적는 방법은 자리값 기수법에, 자연수에서 실수까지의 전체 그림은 수 체계에, 새 수 체계의 대수는 군과 다항식⁠(polynomial)⁠에 있습니다. 모든 자연수가 네 제곱수의 합이라는 1770년 라그랑주의 정리는 사원수⁠(quaternion)⁠의 곱셈과 같은 식으로 이어집니다.