정수론(Number theory)

소수와 에라토스테네스의 체(Primes and the sieve of Eratosthenes)

1과 자기 자신으로만 나누어지는 1보다 큰 자연수⁠(natural number)⁠. 작은 소수⁠(prime number)⁠의 배수⁠(multiple)⁠를 차례로 지우면 남는 수들이다.

p \text{ 소수} \iff p > 1,\ d \mid p \Rightarrow d \in \{1, p\}

먼저 보면 좋은 개념집합

1보다 큰 모든 자연수는 소수들의 곱으로 쪼개집니다(소인수분해⁠, prime factorization⁠). 그래서 소수는 곱셈의 원자이고, 정수⁠(integer)⁠의 성질을 연구하는 정수론⁠(number theory)⁠의 한가운데에 있습니다. 소수를 찾는 가장 오래된 방법은 체입니다. 2부터 시작해 아직 지워지지 않은 가장 작은 수를 소수로 확정하고, 그 수의 배수를 모두 지웁니다. 지금 단계까지 진행했습니다().

노란 칸이 아직 살아남은 수, 초록 칸이 소수로 확정해 그 배수를 지운 수입니다. 지워진 칸은 처음 지운 소수의 색으로 흐리게 남습니다.

1부터 120까지라면 7까지만 체질하면 끝납니다. 1과 자기 자신 말고도 약수⁠(divisor)⁠가 있는 수를 합성수라 합니다. 합성수⁠(composite number)⁠ $n = d \cdot e$ 에서 두 약수가 모두 $\sqrt{n}$ 보다 크면 곱이 $n$ 보다 커지니, 둘 중 하나는 반드시 $\sqrt{n}$ 이하입니다. 그 약수의 가장 작은 소인수도 물론 $\sqrt{n}$ 이하입니다. 그래서 120 이하의 합성수는 모두 $\sqrt{120} \approx 10.95$ 이하의 소수, 곧 2, 3, 5, 7 가운데 하나의 배수로 이미 지워졌습니다. 남은 개가 소수입니다.

이렇게 걸러 낸 소수들은 불규칙하게 흩어져 있습니다. 그런데 한 줄로 늘어놓는 대신 나선으로 감으면 뜻밖의 대각선이 보입니다(울람 나선⁠, Ulam spiral⁠). 멀리서 세면 개수가 $x/\ln x$ 를 따라갑니다. 정확히 말하면 $x$ 이하의 소수 개수를 $x/\ln x$ 로 나눈 비가 $x$ 가 커질수록 1에 다가갑니다(소수 정리⁠, prime number theorem⁠). 차이 자체가 0으로 가는 것은 아닙니다.

소수는 끝이 없습니다. 유클리드의 논증은 이렇습니다. 소수가 $p_1, \dots, p_k$ 뿐이라고 해 봅시다. $N = p_1 p_2 \cdots p_k + 1$ 은 1보다 크니 적어도 하나의 소수로 나누어떨어집니다(1이 아닌 가장 작은 약수는 언제나 소수입니다). 그런데 목록의 어느 $p_i$ 로 나누어도 1이 남습니다. 그러니 목록 밖에 소수가 또 있어야 하고, 모순입니다.

오일러는 더 강한 사실을 보였습니다. 소수의 역수⁠(inverse)⁠의 합 $\tfrac12 + \tfrac13 + \tfrac15 + \cdots$ 도 조화급수⁠(harmonic series)⁠처럼 한없이 커집니다(발산⁠, divergence⁠). 소수가 몇 개뿐이라면 이 합은 유한할 테니, 소수가 무한하다는 것보다 강한 말입니다. 오일러는 모든 자연수 $n$ 에 대한 합을 모든 소수 $p$ 에 대한 곱으로 바꿔 쓰는 식 $\sum 1/n^s = \prod_p (1 - p^{-s})^{-1}$ ( $s \gt 1$ )도 찾았습니다(오일러 곱⁠, Euler product⁠). 이 식은 "모든 자연수는 소수의 곱으로 한 가지로만 쓰인다"는 사실을 식 하나에 담은 것이고, $s = 2$ 를 넣으면 바젤 문제⁠(Basel problem)⁠와 이어집니다.

큰 두 소수를 곱하기는 쉽지만 그 곱을 거꾸로 쪼개기는 어렵다는 사실이 RSA 암호⁠(RSA cryptosystem)⁠의 바탕입니다.

차이가 2인 소수 쌍, 곧 쌍둥이 소수⁠(twin primes)⁠가 끝없이 있는지는 아직 아무도 모릅니다. 반면 소수로만 된 등차수열⁠(arithmetic progression)⁠은 원하는 만큼 길게 있다는 것이 증명되었습니다. 등차수열은 5, 11, 17, 23, 29처럼 이웃한 항의 차(여기서는 6)가 일정한 수열입니다. "원하는 만큼 길게"는 어떤 길이 $k$ 를 정하든 그 길이의 수열이 있다는 뜻입니다. 끝없이 이어지는 수열은 없습니다. 첫 항이 $a \gt 1$ , 차가 $d$ 이면 항 $a + ad = a(1+d)$ 가 $a$ 로 나누어떨어지기 때문입니다. 2004년 영국의 벤 그린과 오스트레일리아 출신의 테런스 타오가 증명해 그린–타오 정리라 부릅니다.

이 결과에는 앞선 흐름이 있습니다. 먼저 반 데르 바르던 정리(1927)는 자연수를 유한한 몇 가지 색으로 칠하든 한 색 안에 원하는 길이의 등차수열이 있다고 말합니다. 이어 헝가리의 세메레디 엔드레는 자연수 가운데 일정한 비율 이상을 차지하는 집합⁠(set)⁠이면 반드시 긴 등차수열을 품는다는 것을 보였습니다(1975). 소수는 점점 드물어져 차지하는 비율이 0으로 가기 때문에 이 정리를 바로 쓸 수 없었는데, 그린과 타오가 그 벽을 넘었습니다.

수가 크면 체를 쓸 수 없습니다. 대신 소수 판정⁠(primality test)⁠으로 빠르게 가립니다. 많은 판정법의 출발점은 페르마 소정리⁠(Fermat's little theorem)⁠입니다. 소수 $p$ 와 $p$ 의 배수가 아닌 $a$ 에 대해 $a^{p-1}$ 을 $p$ 로 나눈 나머지⁠(remainder)⁠는 언제나 1이라는 정리입니다. 그래서 나머지가 1이 아니면 그 수는 확실히 합성수입니다. 거꾸로 나머지가 1이라고 소수라는 보장은 없습니다. 합성수 $561 = 3 \cdot 11 \cdot 17$ 도 $2^{560}$ 을 561로 나누면 1이 남습니다. 실제 판정법은 이런 가짜를 걸러 내도록 검사를 보강합니다.

이 개념이 나오는 큰 생각무한을 다루는 법

이 개념이 나오는 긴 글

소수 소수를 세는 사람들 소수는 제멋대로 흩어져 있는 것 같다. 그런데 멀리서 세어 보면 로그가 보인다. 정수론과 암호 나머지로 지키는 비밀 한 번도 만난 적 없는 두 사람이 모두가 엿듣는 통신망에서 비밀 열쇠를 맞출 수 있을까? 답은 시계의 산수와 1640년 페르마의 정리에 있다. 집합론 무한에도 크기가 있다 자연수와 짝수는 어느 쪽이 많을까? 칸토어는 무한을 세는 법을 찾았고, 무한이 하나가 아님을 보였다. 삼각함수 원에서 파동으로 별의 위치를 재던 현의 표가 사인이 되고, 열의 흐름을 풀던 푸리에가 모든 파동을 사인으로 쪼갰다. 비유클리드 기하 평행선의 반란 유클리드의 다섯 번째 공준은 2,000년 동안 증명되지 않았다. 증명을 포기한 사람들이 찾은 것은 새로운 우주였다. 계산 이론 기계가 풀 수 없는 문제 모든 수학 문제를 기계적으로 풀 수 있을까? 러셀의 역설에서 괴델과 튜링까지, 그 질문에 대한 답은 '아니오'였고, 그 증명이 컴퓨터를 낳았다. 램지 이론 완전한 무질서는 없다 여섯 명이 모이면 서로 아는 세 사람이나 서로 모르는 세 사람이 반드시 있다. 충분히 크면 어디에나 질서가 숨어 있다는 이론과, 그것을 동전 던지기로 증명한 에르되시.

이 개념 위에 세워진 것

소인수분해 소수 정리 울람 나선 소수 판정 쌍둥이 소수 정수론

이 개념을 언급하는 페이지

자연로그
… 자랍니다(둘의 차이는 약 0.577로 다가갑니다). 소수 정리에 따르면 큰 수 x 근처의 수들 가운데소수가 차지하는 비율은 약 1/\ln x 입니다. 나눗셈의 나머지만 보는 세계(모듈러 연산)에도 로그가 …
집합
… 일어날 수 있는 결과 전체가 집합(표본공간)이고 사건은 그 부분집합입니다(확률). 소수를 모은소수 집합, 나머지가 같은 수끼리 묶는 동치류도 모두 집합입니다. 아무 조건이나 모아 집합을 만들어도 된다고 …
포함배제 원리
… 방식으로 두 수를 뽑을 때 서로소일 확률은 6/\pi^2 \approx 0.608 에 다가갑니다. 모든소수p 에 대해 "둘 다 p 의 배수"인 경우(확률 1/p^2 )를 포함배제로 끝까지 빼면 곱 \prod_p …
소인수분해
… 더 작은 두 수의 곱으로 쪼갤 수 있고, 쪼갠 조각이 또 합성수면 다시 쪼갭니다. 더 쪼갤 수 없는 조각이소수입니다. n = 을 쪼개 봅시다: . 왼쪽으로 떨어지는 초록 잎이 소수, 오른쪽으로 내려가는 흰 마디가 …
파스칼의 삼각형
… 의 분자에는 p 가 있지만, 분모의 인수는 모두 p 보다 작아 이 p 를 지우지 못하니까요(소수). 그래서 (a+b)^p 를 전개하면 양 끝 항만 남고, (a+b)^p \equiv a^p + b^p …
모듈러 연산
… 수 없습니다. g = 1 이면 확장 유클리드 호제법이 ax + ny = 1 인 x 를 찾아 줍니다. n 이소수이면 0이 아닌 모든 줄이 빈틈없이 채워집니다. 곱셈을 원 위의 화살표로 그리면 카디오이드가 …
오일러 피 함수와 페르마 소정리
… 입니다( \equiv 는 n 으로 나눈 나머지가 같다는 뜻). 이것이 오일러 정리이고, n = p 가소수이면 \varphi(p) = p - 1 이라 p 의 배수가 아닌 모든 a 에 대해 a^{p-1} …
RSA 암호
두소수p = , q = 를 몰래 고르고, 곱 n = pq 와 지수 e = 를 세상에 공개합니다. 누구든 메시지 …
소수 정리
소수는 하나하나 보면 불규칙하게 흩어져 있지만, 개수를 세어 멀리서 보면 매끄러운 곡선을 따라갑니다. x …
울람 나선
… 몬테카를로 방법을 함께 고안했습니다)은 지루한 학회 발표를 듣다가 공책에 1부터 나선으로 수를 적고소수에만 동그라미를 쳤다고 전해집니다. 한 변 칸의 나선에 담긴 수 중 소수는 개입니다. 모양은 , 가운데 …
바젤 문제
… 라서, 원운동의 \pi 가 이 합으로 흘러들어옵니다. 오일러는 더 놀라운 것을 보았습니다. 모든 자연수는소수로 한 가지로만 분해되니, \sum 1/n^2 은 소수마다 등비급수 1 + p^{-2} + p^{-4} …
조화급수
… 때문입니다. 반면 제곱의 역수 합은 π²/6으로 수렴하고, 비율이 일정한 등비급수도 수렴합니다.소수의 역수만 골라 더한 \tfrac12 + \tfrac13 + \tfrac15 + \tfrac17 + …
원시근
… \equiv 1 이고, 1로 돌아오는 지수는 모두 위수의 배수이기 때문입니다. n 이소수p 이면 원시근이 반드시 있고, 개수는 \varphi(p-1) 입니다. 이유를 세 걸음으로 봅니다. 핵심은 …
중국인의 나머지 정리
… 서로소이기만 하면 됩니다. 이어지는 곳. 이 정리 덕분에 합성수를 법으로 하는 계산은 소인수분해의 각소수거듭제곱에 대한 계산으로 쪼개집니다. 서로소인 m, n 에 대해, mn 과 서로소인 나머지는 ' m 과 …
디피–헬먼 키 교환
… 만난 적 없는 두 사람이 모두가 엿듣는 통로로만 이야기해서 같은 비밀 열쇠를 가질 수 있을까요? 공개된소수p = , 밑 g = (가장 작은 원시근)에서 시작합니다. 두 사람은 각자 비밀 수를 하나씩 고릅니다. …
소수 판정
… 것입니다. n = d \cdot e 이면 두 인수 중 하나는 \sqrt n 이하이니 \sqrt n 까지의소수로만 나눠 보면 됩니다. 하지만 RSA에 쓰는 300자리 수라면 \sqrt n 이 150자리입니다. …
쌍둥이 소수
소수를 늘어놓고 이웃한 두 소수의 차이(소수 간격)를 재 봅시다. 2를 빼면 소수는 모두 홀수이니 3부터는 …
리만 제타 함수
… N까지의 합, 청록 계단은 N 이하 소수에 대한 곱, 노란 점선은 ζ(s)입니다. 오일러는 이 합이소수들에 대한 곱과 같다는 것을 알았습니다. 소수마다 등비급수 1 + p^{-s} + p^{-2s} + …
이항계수
… \binom{2n}{n} \approx 4^n/\sqrt{\pi n} 같은 어림을 줍니다. 이어지는 곳.소수p에 대해 \binom pk ( 0 \lt k \lt p )는 모두 p의 배수입니다. 분자 p!에는 p가 …
가우스 소거법
… 모자라게 되는 값입니다. 0이 아닌 수로 언제나 나눌 수 있는 수 체계(체)라면 어디서든 쓸 수 있어서,소수p 로 나눈 나머지의 세계(모듈러 연산)에서도 그대로 통합니다. 마르코프 연쇄의 정상 분포, 곧 한 …
괴델의 불완전성 정리
… 열쇠는 식을 수로 바꾸는 괴델 수 입니다. 기호마다 번호를 붙이고, 기호열의 j번째 기호 번호를 j번째소수의 지수로 올려 모두 곱합니다. 위의 기호를 누르면 식 끝에 붙고, 식의 기호를 누르면 지워집니다. 지금 …
정지 문제
… 판정할 수 없다는 것이 막연한 말이 아님을 보여 주는 예가 있습니다. 4 이상의 짝수를 차례로 보며 두소수의 합으로 쓸 수 없는 수를 찾으면 멈추는 짧은 프로그램은, 골드바흐 추측이 거짓이면 멈추고 참이면 영원히 …
P 대 NP 문제
… 어렵다는 보장은 되지 않습니다. 소인수분해가 NP 완전이라는 증명이 없기 때문입니다. 반면 수가소수인지 판정하는 문제는 2002년 인도의 아그라왈·카얄·삭세나가 내놓은 AKS 알고리즘으로 P에 속함이 …
반 데르 바르던 정리
… 적어도 한 색이 이런 조건을 만족하므로, 반 데르 바르던 정리가 여기서 따라 나옵니다. 소수 속 등차수열.소수는 N 이하에 약 N/\ln N 개뿐이라(소수 정리) 비율이 0으로 줄어들고, 세메레디 정리를 쓸 수 …
수 체계: 자연수에서 실수까지
… 넓히면 상수가 아닌 모든 다항식이 1차식의 곱으로 쪼개집니다. 정수 안에서의 나눗셈은 정수론(소수, 모듈러 연산)으로 갑니다. 역원이 있게 하려고 수를 넓혀 온 이 이야기는 군의 이야기이기도 …
군
… 원소가 셋인 부분군이 없습니다. 이 정리를 1, 2, …, p − 1과 'p로 나눈 나머지의 곱셈'(p는소수)에 적용하면, p의 배수가 아닌 모든 a에 대해 페르마의 소정리 a^{p-1} \equiv 1 …
정수론
… 12의 약수는 1, 2, 3, 4, 6, 12입니다. 1과 자기 자신 말고는 약수가 없는 2 이상의 수가소수이고, 2 이상의 모든 자연수는 소수의 곱으로 단 한 가지 방법으로 쪼개집니다. 예를 들어 360 = …

이 페이지가 가리키는 개념

소인수분해 정수론 울람 나선 소수 정리 유클리드 레온하르트 오일러 조화급수 급수의 수렴과 발산 리만 제타 함수 바젤 문제 RSA 암호 쌍둥이 소수 반 데르 바르던 정리 소수 판정 오일러 피 함수와 페르마 소정리