정수론 (Number Theory)

정수론은 정수의 성질을 연구하는 수학의 가장 오래된 분야 중 하나입니다. 가우스는 "수학은 과학의 여왕이고, 정수론은 수학의 여왕이다"라고 하였습니다.

이런 곳에 쓰여요

선수 지식: 수와 연산, 대수학 기초

난이도: ★★★☆☆ (고등학교 심화)

약수와 배수

정수 $a$가 정수 $b$로 나누어떨어질 때, $b$는 $a$의 약수(Divisor)이고 $a$는 $b$의 배수(Multiple)라 합니다. 이를 $b \mid a$로 표기합니다.

나눗셈 정리

정수 $a$와 양의 정수 $b$에 대하여, 다음을 만족하는 유일한 정수 $q$(몫)와 $r$(나머지)이 존재합니다.

약수의 성질

• $a \mid b$이고 $b \mid c$이면 $a \mid c$ (추이성)
• $a \mid b$이고 $a \mid c$이면 $a \mid (bx + cy)$ (임의의 정수 $x$, $y$에 대해)
• $a \mid b$이고 $b \mid a$이면 $a = \pm b$
• $a \mid b$이고 $b \neq 0$이면 $|a| \leq |b|$

최대공약수와 최소공배수

• 최대공약수(GCD): $\gcd(a, b)$는 $a$와 $b$의 공약수 중 가장 큰 것
• 최소공배수(LCM): $\operatorname{lcm}(a, b)$는 $a$와 $b$의 공배수 중 가장 작은 양수

GCD와 LCM의 성질

$a = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, $b = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k}$로 소인수분해하면 (지수가 0인 소수도 포함):

이로부터 핵심 관계식이 도출됩니다:

추가 성질:

• $\gcd(a, b) = \gcd(b, a)$ (교환법칙)
• $\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)$ (결합법칙)
• $\gcd(ka, kb) = k \cdot \gcd(a, b)$ ($k > 0$)
• $\gcd(a, b) = 1$이고 $\gcd(a, c) = 1$이면 $\gcd(a, bc) = 1$
• $\gcd(a, b) = 1$이고 $a \mid bc$이면 $a \mid c$

약수 함수

양의 정수 $n$에 대해 다음과 같은 약수 함수가 정의됩니다:

• 약수의 개수 함수 $\tau(n)$ (또는 $d(n)$, $\sigma_0(n)$): $n$의 양의 약수의 개수
• 약수의 합 함수 $\sigma(n)$ (또는 $\sigma_1(n)$): $n$의 양의 약수의 합
• 일반 약수 함수: $\sigma_k(n) = \displaystyle\sum_{d \mid n} d^k$

$n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$일 때:

완전수(Perfect Number)란 $\sigma(n) = 2n$을 만족하는 양의 정수입니다. 예를 들어 $6, 28, 496, 8128, \ldots$이 있습니다. 오일러는 짝수 완전수는 반드시 $2^{p-1}(2^p - 1)$ 꼴임을 보였습니다 ($2^p - 1$이 소수일 때).

소수와 소인수분해

소수(Prime)는 1보다 크고, 1과 자기 자신만을 약수로 가지는 자연수입니다. 소수가 아닌 1보다 큰 자연수를 합성수(Composite)라 합니다.

처음 몇 개의 소수: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, \ldots$

산술의 기본정리

1보다 큰 모든 자연수는 소수의 곱으로 유일하게(순서 무시) 표현됩니다.

소수의 무한성 — 4가지 증명

소수가 무한히 많다는 사실은 수론의 가장 기본적인 정리입니다. 다양한 증명 기법을 통해 이 사실을 확인합니다.

증명 1: 유클리드의 증명 (기원전 300년경)

소수가 유한개, 즉 $p_1, p_2, \ldots, p_n$이 모든 소수의 목록이라고 가정합니다. 다음 수를 구성합니다:

$N > 1$이므로 산술의 기본정리에 의해 $N$은 어떤 소수 $p$로 나누어집니다. 그런데 모든 $p_i$에 대해 $N$을 $p_i$로 나누면 나머지가 1이므로 $p_i \nmid N$입니다. 따라서 $p$는 목록에 없는 새로운 소수이며, 이는 모순입니다. $\blacksquare$

증명 2: 오일러의 해석적 증명

소수의 역수의 합이 발산함을 보입니다. 오일러 곱(Euler product)에서 출발합니다:

$s \to 1^+$로 보내면 좌변의 조화급수는 발산합니다. 만약 소수가 유한개 $p_1, \ldots, p_k$라면 우변은 유한한 곱이므로 유한한 값을 가집니다. 이는 모순입니다.

나아가 오일러는 $\displaystyle\sum_{p \text{ 소수}} \frac{1}{p} = \infty$임을 보였는데, 이는 소수가 무한할 뿐 아니라 "충분히 조밀하게" 분포함을 의미합니다. $\blacksquare$

증명 3: 에르되시의 증명 (1938)

이 증명은 소수가 유한개라면 $N$ 이하의 자연수가 너무 적어진다는 조합론적 논증을 사용합니다.

소수가 $k$개, 즉 $p_1, p_2, \ldots, p_k$뿐이라고 가정합니다. $N$ 이하의 임의의 자연수 $n$을 $n = m^2 \cdot s$로 쓸 수 있는데, 여기서 $s$는 제곱인수 없는 수(square-free)입니다. 그러면:

• $m \leq \sqrt{N}$이므로 $m$의 선택지는 최대 $\sqrt{N}$개입니다.
• $s$는 $\{p_1, \ldots, p_k\}$의 부분집합의 곱이므로 $s$의 선택지는 최대 $2^k$개입니다.

따라서 $N$ 이하의 자연수의 개수에 대해 $N \leq \sqrt{N} \cdot 2^k$, 즉 $\sqrt{N} \leq 2^k$이므로 $N \leq 4^k$입니다. 그런데 $k$는 고정된 유한수이므로 $N$이 $4^k$보다 커지면 모순입니다. $\blacksquare$

증명 4: 퓌르스텐베르크의 위상적 증명 (1955)

정수 $\mathbb{Z}$ 위에 등차수열 위상을 정의합니다. 기본 열린 집합을 $U(a, b) = \{a + nb : n \in \mathbb{Z}\}$ ($b > 0$)로 놓습니다. 이 집합들은 동시에 닫힌 집합이기도 합니다 (보집합이 유한 개의 등차수열의 합집합).

각 소수 $p$에 대해 $p$의 배수 전체의 집합 $U(0, p) = p\mathbb{Z}$는 열린 동시에 닫힌 집합입니다. 이제:

만약 소수가 유한개라면 좌변은 유한 개의 닫힌 집합의 합집합이므로 닫힌 집합입니다. 그러면 $\{-1, 1\}$이 열린 집합이어야 하는데, 유한 집합은 이 위상에서 열린 집합이 될 수 없습니다 (모든 비공 열린 집합은 무한). 이는 모순입니다. $\blacksquare$

소수 정리

$\pi(x)$를 $x$ 이하의 소수의 개수라 하면:

즉, $\displaystyle\lim_{x \to \infty} \frac{\pi(x)}{x / \ln x} = 1$입니다. 이 정리는 1896년 아다마르와 드 라 발레 푸생이 독립적으로 증명하였습니다.

보다 정밀한 근사로는 로그 적분 함수가 사용됩니다:

소수 판정법

시행 나눗셈법

$n$이 소수인지 판정하려면 $\sqrt{n}$ 이하의 모든 소수로 나누어 봅니다. 만약 어떤 소수로도 나누어지지 않으면 $n$은 소수입니다.

이유: $n = ab$에서 $a \leq b$이면 $a \leq \sqrt{n}$이기 때문입니다.

에라토스테네스의 체

$N$ 이하의 모든 소수를 구하는 고전적 알고리즘입니다:

1. $2$부터 $N$까지의 수를 나열합니다.
2. 아직 지워지지 않은 가장 작은 수 $p$를 소수로 선택합니다.
3. $p^2, p^2 + p, p^2 + 2p, \ldots$ ($\leq N$)를 모두 지웁니다.
4. $p^2 > N$이 될 때까지 2~3을 반복합니다.

시간 복잡도는 $O(N \log \log N)$이며, 매우 효율적입니다.

밀러-라빈 소수 판정법

큰 수의 소수 판정에 사용되는 확률적 알고리즘입니다. $n - 1 = 2^s \cdot d$ ($d$ 홀수)로 쓸 때, $n$이 소수이면 임의의 $a$ ($1 < a < n$)에 대해 다음 중 하나가 성립합니다:

이 조건을 만족하지 않으면 $n$은 확실히 합성수이고, 만족하면 $n$은 "아마도 소수"입니다. $k$번 반복하면 오류 확률은 $4^{-k}$ 이하입니다.

유클리드 호제법

유클리드 호제법(Euclidean Algorithm)은 두 정수의 최대공약수를 구하는 효율적인 알고리즘입니다. 핵심 원리는 $\gcd(a, b) = \gcd(b, a \bmod b)$입니다.

알고리즘

$\gcd(a, b)$를 구하려면 ($a > b > 0$):

나머지가 0이 될 때까지 반복하면, 마지막 0이 아닌 나머지가 GCD입니다.

예시

$\gcd(252, 198)$을 구합니다.

따라서 $\gcd(252, 198) = 18$입니다.

확장 유클리드 호제법

$\gcd(a, b) = d$일 때, $ax + by = d$를 만족하는 정수 $x$, $y$를 구할 수 있습니다. 이를 베주 항등식(Bezout's Identity)이라 합니다.

단계별 풀이 예시

$\gcd(252, 198) = 18$이므로 $252x + 198y = 18$을 만족하는 $x$, $y$를 구합니다.

유클리드 호제법의 각 단계를 역순으로 대입합니다:

따라서 $x = 4$, $y = -5$이고, 검산: $252 \times 4 + 198 \times (-5) = 1008 - 990 = 18$. $\checkmark$

유클리드 호제법의 시간 복잡도

라메(Lame)의 정리에 의하면, 유클리드 호제법이 $n$번 이상의 나눗셈을 수행하려면 $b \geq F_{n+1}$ (피보나치 수)이어야 합니다. 따라서 나눗셈 횟수는 $O(\log b)$입니다.

합동식과 모듈러 산술

$a$와 $b$를 $m$으로 나눈 나머지가 같으면 합동(Congruent)이라 하며 다음과 같이 표기합니다.

합동의 성질

• 반사성: $a \equiv a \pmod{m}$
• 대칭성: $a \equiv b$이면 $b \equiv a \pmod{m}$
• 추이성: $a \equiv b$이고 $b \equiv c$이면 $a \equiv c \pmod{m}$
• 덧셈: $a \equiv b$이고 $c \equiv d$이면 $a + c \equiv b + d \pmod{m}$
• 곱셈: $a \equiv b$이고 $c \equiv d$이면 $ac \equiv bd \pmod{m}$
• 거듭제곱: $a \equiv b$이면 $a^n \equiv b^n \pmod{m}$

모듈러 역원

$\gcd(a, m) = 1$일 때, $ax \equiv 1 \pmod{m}$을 만족하는 $x$를 $a$의 모듈러 역원이라 하며 $a^{-1} \pmod{m}$으로 표기합니다. 확장 유클리드 호제법으로 구할 수 있습니다.

선형 합동식

$ax \equiv b \pmod{m}$의 풀이:

1. $d = \gcd(a, m)$을 구합니다.
2. $d \nmid b$이면 해가 없습니다.
3. $d \mid b$이면, 양변을 $d$로 나누어 $\frac{a}{d} x \equiv \frac{b}{d} \pmod{\frac{m}{d}}$를 풀면 됩니다. 이때 $\gcd(\frac{a}{d}, \frac{m}{d}) = 1$이므로 모듈러 역원이 존재합니다.
4. 해는 $\bmod m$에서 정확히 $d$개 존재합니다.

중국인의 나머지 정리 (CRT)

$m_1, m_2, \ldots, m_k$가 쌍마다 서로소이면 연립합동식

은 모듈로 $M = m_1 m_2 \cdots m_k$에서 유일한 해를 가집니다.

CRT 해의 구성법

$M_i = M / m_i$로 놓으면 $\gcd(M_i, m_i) = 1$이므로 $M_i y_i \equiv 1 \pmod{m_i}$인 $y_i$가 존재합니다. 그러면:

CRT 상세 예시

다음 연립합동식을 풉니다:

풀이:

• $M = 3 \times 5 \times 7 = 105$
• $M_1 = 105/3 = 35$, $M_2 = 105/5 = 21$, $M_3 = 105/7 = 15$
• $35 y_1 \equiv 1 \pmod{3}$: $35 \equiv 2 \pmod{3}$이고 $2 \times 2 = 4 \equiv 1$이므로 $y_1 = 2$
• $21 y_2 \equiv 1 \pmod{5}$: $21 \equiv 1 \pmod{5}$이므로 $y_2 = 1$
• $15 y_3 \equiv 1 \pmod{7}$: $15 \equiv 1 \pmod{7}$이므로 $y_3 = 1$
• $x \equiv 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 140 + 63 + 30 = 233 \equiv 23 \pmod{105}$

검산: $23 = 3 \times 7 + 2$, $23 = 5 \times 4 + 3$, $23 = 7 \times 3 + 2$. $\checkmark$

합동식 풀이 — 세 가지 방법 비교

$7x \equiv 3 \pmod{31}$을 세 가지 방법으로 풀어 비교합니다.

방법 1: 확장 유클리드 호제법

$7x \equiv 3 \pmod{31}$은 $7x + 31y = 3$의 정수 해를 구하는 것과 같습니다. 먼저 $\gcd(7, 31) = 1$을 확인합니다:

역대입하면 $1 = 7 - 2 \times 3 = 7 - 2(31 - 4 \times 7) = 9 \times 7 - 2 \times 31$이므로 $7 \times 9 \equiv 1 \pmod{31}$, 즉 $7^{-1} \equiv 9 \pmod{31}$입니다.

검산: $7 \times 27 = 189 = 6 \times 31 + 3$. $\checkmark$

방법 2: 오일러 정리 이용

$31$은 소수이므로 페르마 소정리에 의해 $7^{30} \equiv 1 \pmod{31}$입니다. 따라서:

거듭제곱을 빠르게 계산합니다: $7^2 = 49 \equiv 18$, $7^4 \equiv 18^2 = 324 \equiv 14$, $7^8 \equiv 14^2 = 196 \equiv 10$, $7^{16} \equiv 10^2 = 100 \equiv 7$.

따라서 $x \equiv 9 \times 3 = 27 \pmod{31}$. 같은 결과입니다.

방법 3: CRT를 이용한 모듈러 분해

법이 합성수인 경우 CRT가 강력합니다. 예를 들어 $7x \equiv 3 \pmod{30}$을 풀 때, $30 = 2 \times 3 \times 5$로 분해합니다:

CRT로 결합하면 $x \equiv 9 \pmod{30}$을 얻습니다.

페르마 소정리

정리

소수 $p$와 $\gcd(a, p) = 1$인 정수 $a$에 대하여:

동치인 형태: 임의의 정수 $a$에 대하여 $a^p \equiv a \pmod{p}$

증명 — 4가지 방법

증명 1: 재배열 논증 (고전적 증명)

$\gcd(a, p) = 1$일 때, $\{a, 2a, 3a, \ldots, (p-1)a\}$를 $\bmod p$로 환원하면 $\{1, 2, 3, \ldots, p-1\}$의 재배열이 됩니다.

(이유: $ia \equiv ja \pmod{p}$이면 $p \mid (i-j)a$이고 $\gcd(a,p) = 1$이므로 $p \mid (i-j)$, 즉 $i = j$.)

따라서 양변의 곱을 비교하면:

$\gcd((p-1)!, p) = 1$이므로 양변을 $(p-1)!$로 나누면 $a^{p-1} \equiv 1 \pmod{p}$. $\blacksquare$

증명 2: 수학적 귀납법

$a^p \equiv a \pmod{p}$를 $a$에 대한 귀납법으로 증명합니다.

기저: $a = 0$이면 $0^p = 0 \equiv 0 \pmod{p}$. $\checkmark$

귀납 단계: $a^p \equiv a \pmod{p}$를 가정하고 $(a+1)^p$를 이항 전개합니다:

$0 < k < p$일 때, $\binom{p}{k} = \frac{p!}{k!(p-k)!}$에서 분자에 $p$가 있고 분모의 어떤 인수도 $p$를 나누지 못하므로 $p \mid \binom{p}{k}$입니다. 따라서:

$a \geq 0$에 대해 성립하고, 음의 정수에 대해서도 $(-a)^p = -a^p$ (소수 $p$는 홀수이거나 $p=2$)로부터 확장됩니다. $\blacksquare$

증명 3: 군론적 증명

$(\mathbb{Z}/p\mathbb{Z})^{\times} = \{1, 2, \ldots, p-1\}$은 곱셈에 대한 군이며, 그 위수는 $p-1$입니다. 라그랑주 정리에 의하면 유한군의 원소의 위수는 군의 위수를 나눕니다. 따라서 $\gcd(a, p) = 1$인 $a$에 대해 $a$의 위수 $d$는 $d \mid (p-1)$을 만족하고, $a^{p-1} = (a^d)^{(p-1)/d} = 1^{(p-1)/d} = 1$입니다. $\blacksquare$

증명 4: 목걸이 세기 (조합적 증명)

$p$개의 구슬을 원형으로 배열하되 $a$가지 색을 사용하는 경우의 수를 셉니다.

• 일렬 배열의 수: $a^p$가지
• 그중 모든 구슬이 같은 색인 것: $a$가지
• 나머지 $a^p - a$가지의 일렬 배열은 원형으로 만들면 $p$개씩 동일한 목걸이가 됩니다. ($p$가 소수이므로 비자명한 순환 대칭이 없기 때문입니다.)

따라서 목걸이의 수 $= \frac{a^p - a}{p}$가 정수가 되어야 하므로 $p \mid (a^p - a)$, 즉 $a^p \equiv a \pmod{p}$. $\blacksquare$

응용

• 거듭제곱 계산: $2^{100} \pmod{13}$을 구할 때, $2^{12} \equiv 1 \pmod{13}$이므로 $2^{100} = 2^{12 \times 8 + 4} \equiv 2^4 = 16 \equiv 3 \pmod{13}$
• 모듈러 역원: $a^{-1} \equiv a^{p-2} \pmod{p}$
• 페르마 소수 판정: $a^{n-1} \not\equiv 1 \pmod{n}$이면 $n$은 합성수 (대우 이용). 단, 역은 성립하지 않음 (카마이클 수)

오일러 정리와 오일러 함수

오일러 피 함수

오일러 피 함수(Euler's Totient Function) $\phi(n)$은 $1$부터 $n$까지의 정수 중 $n$과 서로소인 것의 개수입니다.

계산 공식

$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$일 때:

오일러 함수의 성질

• 소수 $p$에 대해 $\phi(p) = p - 1$
• 소수 거듭제곱: $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$
• 곱셈적 함수: $\gcd(m, n) = 1$이면 $\phi(mn) = \phi(m)\phi(n)$
• 약수 합 공식: $\displaystyle\sum_{d \mid n} \phi(d) = n$

오일러 정리

$\gcd(a, n) = 1$이면:

페르마 소정리는 $n$이 소수일 때($\phi(p) = p-1$)의 특수한 경우입니다.

증명

페르마 소정리의 증명과 동일한 아이디어를 사용합니다. $n$과 서로소인 $\phi(n)$개의 수 $r_1, r_2, \ldots, r_{\phi(n)}$에 대해 $ar_1, ar_2, \ldots, ar_{\phi(n)}$도 $\bmod n$에서 같은 집합의 재배열입니다. 양변의 곱을 비교하면:

$\gcd(r_1 r_2 \cdots r_{\phi(n)}, n) = 1$이므로 $a^{\phi(n)} \equiv 1 \pmod{n}$. $\blacksquare$

이차잉여

홀수 소수 $p$와 $\gcd(a, p) = 1$인 정수 $a$에 대해, $x^2 \equiv a \pmod{p}$가 해를 가지면 $a$를 $p$에 대한 이차잉여(Quadratic Residue)라 하고, 그렇지 않으면 이차비잉여(Quadratic Non-Residue)라 합니다.

르장드르 기호

르장드르 기호(Legendre Symbol)는 다음과 같이 정의됩니다:

오일러 판정법

증명 스케치: 페르마 소정리에서 $a^{p-1} \equiv 1$이므로 $(a^{(p-1)/2} - 1)(a^{(p-1)/2} + 1) \equiv 0 \pmod{p}$. $a$가 이차잉여이면 $a = x^2$이므로 $a^{(p-1)/2} = x^{p-1} \equiv 1$. 이차비잉여이면 나머지 경우인 $-1$이 됩니다.

이차 상호법칙

서로 다른 홀수 소수 $p$, $q$에 대하여:

즉, $p \equiv q \equiv 3 \pmod{4}$인 경우에만 부호가 바뀌고, 나머지 경우에는 $\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$입니다.

보충 법칙:

이차 상호법칙의 증명

가우스는 이 정리를 6가지 이상의 방법으로 증명하였습니다. 여기서는 두 가지 핵심 증명을 소개합니다.

증명 1: 가우스의 보조정리(Gauss's Lemma)를 이용한 증명

가우스의 보조정리: 홀수 소수 $p$와 $\gcd(a, p) = 1$에 대해, $a, 2a, 3a, \ldots, \frac{p-1}{2}a$의 $\bmod p$ 환원값 중 $\frac{p}{2}$보다 큰 것의 개수를 $\nu$라 하면:

증명 (보조정리): $S = \{a, 2a, \ldots, \frac{p-1}{2} \cdot a\}$의 원소를 $\bmod p$로 환원합니다. 이들 중 $\frac{p}{2}$보다 작은 것을 $r_1, \ldots, r_s$, 큰 것을 $t_1, \ldots, t_{\nu}$라 합니다. 그러면 $\{r_1, \ldots, r_s, p - t_1, \ldots, p - t_{\nu}\}$는 $\{1, 2, \ldots, \frac{p-1}{2}\}$의 재배열입니다. 양변의 곱을 비교하면:

한편 $r_1 \cdots r_s \cdot t_1 \cdots t_{\nu} \equiv a^{(p-1)/2} \cdot \left(\frac{p-1}{2}\right)! \pmod{p}$이므로:

상호법칙 증명 (가우스의 보조정리 이용): $\nu$의 값을 격자점 세기로 계산합니다. 직사각형 $\{(x, y) : 1 \leq x \leq \frac{p-1}{2}, \, 1 \leq y \leq \frac{q-1}{2}\}$ 내에서 $qx - py > 0$인 점과 $qx - py < 0$인 점의 개수가 각각 $\left(\frac{q}{p}\right)$와 $\left(\frac{p}{q}\right)$의 부호를 결정하며, 격자점의 총 개수는 $\frac{p-1}{2} \cdot \frac{q-1}{2}$이므로 상호법칙이 도출됩니다.

증명 2: 아이젠슈타인의 증명 (1844)

아이젠슈타인의 증명은 삼각함수를 사용하는 우아한 방법입니다. 핵심은 다음 항등식입니다:

이를 $a = q$에 대해 적용하고, $p$와 $q$의 역할을 바꾸어 곱하면:

정밀한 계산을 수행하면 이 곱이 $(-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$와 같음을 보일 수 있습니다.

야코비 기호

르장드르 기호를 합성수로 확장한 것이 야코비 기호(Jacobi Symbol)입니다. 홀수 양의 정수 $n = p_1^{e_1} \cdots p_k^{e_k}$에 대해:

야코비 기호는 이차 상호법칙이 그대로 성립하므로 $n$의 소인수분해 없이도 유클리드 호제법과 유사한 방식으로 빠르게 계산할 수 있습니다.

연분수

연분수(Continued Fraction)는 다음과 같은 형태의 표현입니다:

간략히 $[a_0; a_1, a_2, a_3, \ldots]$로 표기합니다. 여기서 $a_0$은 정수이고 $a_i \geq 1$ ($i \geq 1$)은 양의 정수입니다.

유리수의 연분수 전개

유리수의 연분수 전개는 유한합니다. 유클리드 호제법과 직접 대응됩니다.

예시: $\frac{43}{19}$를 연분수로 전개합니다.

따라서 $\frac{43}{19} = [2; 3, 1, 4]$입니다.

무리수의 연분수 전개

무리수의 연분수 전개는 무한합니다. 이차 무리수의 연분수는 결국 순환합니다.

• $\sqrt{2} = [1; 2, 2, 2, \ldots] = [1; \overline{2}]$
• $\sqrt{3} = [1; \overline{1, 2}]$
• $e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, \ldots]$ (규칙적이나 순환은 아님)
• 황금비 $\varphi = [1; \overline{1}] = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cdots}}$

수렴자

연분수 $[a_0; a_1, a_2, \ldots]$의 $n$번째 수렴자(Convergent) $\frac{p_n}{q_n} = [a_0; a_1, \ldots, a_n]$는 다음 점화식으로 구합니다:

초기값: $p_{-1} = 1$, $p_{-2} = 0$, $q_{-1} = 0$, $q_{-2} = 1$.

유클리드 호제법과의 관계

유리수 $\frac{a}{b}$의 연분수 전개는 $\gcd(a, b)$를 구하는 유클리드 호제법과 정확히 동일한 과정입니다. 유클리드 호제법의 각 단계에서 나오는 몫이 연분수의 부분 몫(partial quotient)이 됩니다.

이 대응에 의해 확장 유클리드 호제법에서 구하는 베주 계수 $(x, y)$도 수렴자와 직접 관련됩니다: $\frac{a}{b} = [a_0; a_1, \ldots, a_n]$이면 $p_{n-1} q_n - p_n q_{n-1} = (-1)^n$이므로 $b \cdot p_{n-1} - a \cdot q_{n-1} = (-1)^n \cdot \gcd(a, b)$입니다.

펠 방정식

펠 방정식(Pell's Equation) $x^2 - Dy^2 = 1$ ($D$는 완전제곱수가 아닌 양의 정수)의 양의 정수 해는 $\sqrt{D}$의 연분수 전개로 구합니다.

정리: $\sqrt{D} = [a_0; \overline{a_1, a_2, \ldots, a_r}]$ (순환 마디의 길이가 $r$)일 때:

• $r$이 짝수이면 기본해는 $(x_1, y_1) = (p_{r-1}, q_{r-1})$
• $r$이 홀수이면 기본해는 $(x_1, y_1) = (p_{2r-1}, q_{2r-1})$

일반해는 다음과 같이 재귀적으로 생성됩니다:

예시: $x^2 - 7y^2 = 1$

$\sqrt{7} = [2; \overline{1, 1, 1, 4}]$이므로 순환 마디의 길이는 $r = 4$ (짝수)입니다. $[2; 1, 1, 1]$의 수렴자를 구합니다:

기본해: $(x_1, y_1) = (8, 3)$. 검산: $8^2 - 7 \times 3^2 = 64 - 63 = 1$. $\checkmark$

다음 해: $(x_2, y_2) = (8^2 + 7 \times 3^2, \, 2 \times 8 \times 3) = (127, 48)$. 검산: $127^2 - 7 \times 48^2 = 16129 - 16128 = 1$. $\checkmark$

디오판토스 방정식

디오판토스 방정식(Diophantine Equation)은 정수 해만을 구하는 방정식입니다.

일차 디오판토스 방정식

$ax + by = c$ ($a, b, c$는 정수)의 정수 해:

• $d = \gcd(a, b)$로 놓으면, $d \mid c$일 때만 해가 존재합니다 (베주 항등식).
• 특수해 $(x_0, y_0)$를 확장 유클리드 호제법으로 구하면, 일반해는:

피타고라스 세 쌍

$x^2 + y^2 = z^2$의 양의 정수 해 $(x, y, z)$를 피타고라스 세 쌍(Pythagorean Triple)이라 합니다.

$\gcd(x, y, z) = 1$인 원시 피타고라스 세 쌍은 (순서 무시) 다음과 같이 매개변수화됩니다:

단, $m > n > 0$, $\gcd(m, n) = 1$, $m - n$은 홀수.

페르마 하강법

무한 하강법(Method of Infinite Descent)은 페르마가 고안한 증명 기법으로, "양의 정수 해가 존재하면 더 작은 해가 존재함"을 반복하여 모순을 이끌어냅니다.

예시: $x^4 + y^4 = z^2$은 양의 정수 해가 없습니다

이 결과로부터 $x^4 + y^4 = z^4$도 해가 없음이 따릅니다 (페르마의 마지막 정리 $n = 4$ 경우).

증명 (하강법): 양의 정수 해 $(x, y, z)$가 존재하되 $z$가 최소라고 가정합니다. $\gcd(x, y) = 1$로 놓을 수 있습니다.

1. $(x^2, y^2, z)$가 피타고라스 세 쌍을 이루므로 매개변수 표현에 의해 $x^2 = m^2 - n^2$, $y^2 = 2mn$, $z = m^2 + n^2$ (또는 $x$, $y$ 교환).
2. $y^2 = 2mn$이고 $\gcd(m, n) = 1$이므로 $m = s^2$, $n = 2t^2$ (또는 반대).
3. $x^2 = m^2 - n^2 = s^4 - 4t^4$에서 $x^2 + 4t^4 = s^4$, 즉 $x^2 + (2t^2)^2 = (s^2)^2$.
4. 다시 매개변수화하면 더 작은 해를 얻어 $z' = s^2 \leq m < m^2 + n^2 = z$, 이는 $z$의 최소성에 모순됩니다.

따라서 해가 존재하지 않습니다. $\blacksquare$

모듈러 산술을 이용한 불가능성 증명

디오판토스 방정식이 해를 갖지 않음을 보이는 다른 방법은 적절한 법으로 합동식을 검사하는 것입니다.

예시: $x^2 + y^2 = 4k + 3$ 꼴의 수는 두 제곱의 합이 될 수 없습니다

$\bmod 4$에서 제곱수는 $0$ 또는 $1$만 가능합니다. 따라서 $x^2 + y^2 \bmod 4$의 가능한 값은 $\{0, 1, 2\}$이고, $3$은 불가능합니다. 예를 들어 $x^2 + y^2 = 7$은 정수 해가 없습니다.

페르마의 두 제곱 정리

홀수 소수 $p$가 두 정수의 제곱의 합 $p = a^2 + b^2$으로 표현될 필요충분조건은 $p \equiv 1 \pmod{4}$입니다.

한 줄 증명 (자고에): 유한 집합 $S = \{(x, y, z) \in \mathbb{N}^3 : x^2 + 4yz = p\}$ 위의 자기역변환(involution)을 구성하여 증명합니다.

페르마의 마지막 정리

$n \geq 3$인 정수에 대하여 다음 방정식은 양의 정수 해를 갖지 않습니다:

페르마는 1637년경 자신의 산술 사본 여백에 "경이로운 증명을 발견했으나 여백이 좁아 적지 못한다"고 기록하였습니다. 이 정리는 약 358년 후인 1995년 앤드루 와일스가 타니야마-시무라 추측(현재 모듈러 정리)의 준안정적(semistable) 경우를 증명함으로써 해결하였습니다.

RSA 암호

오일러 정리는 RSA 공개키 암호 시스템의 수학적 기초입니다. 1977년 리베스트(Rivest), 샤미르(Shamir), 에이들먼(Adleman)이 제안하였습니다.

키 생성

1. 서로 다른 두 큰 소수 $p$, $q$를 선택합니다.
2. $n = pq$를 계산합니다.
3. $\phi(n) = (p-1)(q-1)$을 계산합니다.
4. $\gcd(e, \phi(n)) = 1$인 정수 $e$를 선택합니다 (보통 $e = 65537$).
5. $ed \equiv 1 \pmod{\phi(n)}$인 $d$를 확장 유클리드 호제법으로 구합니다.
6. 공개키: $(n, e)$ / 비밀키: $(n, d)$

암호화와 복호화

메시지 $M$ ($0 \leq M < n$)에 대하여:

정확성 증명

$C^d \equiv (M^e)^d = M^{ed} \pmod{n}$. $ed = 1 + k\phi(n)$이므로:

(오일러 정리에 의해, $\gcd(M, n) = 1$일 때. $\gcd(M, n) \neq 1$인 경우도 CRT를 이용하면 성립합니다.)

구체적 예시

1. 키 생성: $p = 61$, $q = 53$으로 놓으면 $n = 3233$, $\phi(n) = 60 \times 52 = 3120$
2. $e = 17$ 선택 ($\gcd(17, 3120) = 1$)
3. $17d \equiv 1 \pmod{3120}$에서 $d = 2753$ (확인: $17 \times 2753 = 46801 = 15 \times 3120 + 1$)
4. 공개키: $(3233, 17)$, 비밀키: $(3233, 2753)$
5. 암호화: 메시지 $M = 65$이면 $C = 65^{17} \bmod 3233 = 2790$
6. 복호화: $2790^{2753} \bmod 3233 = 65$ $\checkmark$

산술 함수

산술 함수(Arithmetic Function)는 양의 정수에서 복소수로의 함수입니다. 특히 $f(mn) = f(m)f(n)$ ($\gcd(m,n) = 1$)을 만족하면 곱셈적 함수(Multiplicative Function)라 합니다.

주요 산술 함수

뫼비우스 함수

뫼비우스 함수(Mobius Function) $\mu(n)$은 다음과 같이 정의됩니다:

핵심 성질:

이를 $\mu * \mathbf{1} = \varepsilon$ (디리클레 합성곱)로 표현합니다.

뫼비우스 반전 공식

산술 함수 $f$와 $g$에 대하여:

뫼비우스 반전의 다양한 응용

응용 1: 원분 다항식

$n$차 원분 다항식(Cyclotomic Polynomial) $\Phi_n(x)$는 뫼비우스 반전으로 표현됩니다:

예를 들어 $\Phi_6(x) = \frac{(x^6-1)(x-1)}{(x^3-1)(x^2-1)} = x^2 - x + 1$입니다.

응용 2: 제곱인수 없는 수의 밀도

$N$ 이하의 제곱인수 없는 수(square-free numbers)의 개수 $Q(N)$에 뫼비우스 함수를 사용합니다:

$N \to \infty$일 때 $Q(N) \sim \frac{6}{\pi^2} N = \frac{N}{\zeta(2)}$입니다. 즉, 자연수의 약 $60.8\%$가 제곱인수를 갖지 않습니다.

응용 3: $n$ 이하의 기약분수 세기

분모가 $n$ 이하인 $[0, 1]$ 구간의 기약분수의 개수(패리 수열의 길이)는 $|F_n| = 1 + \sum_{k=1}^{n} \phi(k)$이며, 이것은 뫼비우스 함수를 이용한 포함-배제 원리로도 유도됩니다.

응용 4: 가우스의 정수점 세기

$\gcd(a, b) = 1$인 격자점 $(a, b)$의 밀도를 구하는 문제에서도 뫼비우스 반전이 사용됩니다:

디리클레 합성곱

두 산술 함수 $f$, $g$의 디리클레 합성곱(Dirichlet Convolution)은 다음과 같이 정의됩니다:

주요 성질:

• 교환법칙: $f * g = g * f$
• 결합법칙: $(f * g) * h = f * (g * h)$
• 항등원: $\varepsilon(n) = [n = 1]$ (이브슨 괄호)
• 곱셈적 함수끼리의 디리클레 합성곱도 곱셈적

중요한 관계식들 (디리클레 합성곱 표현):

• $\mathbf{1} * \mathbf{1} = \tau$ (약수 개수)
• $\text{id} * \mathbf{1} = \sigma$ (약수 합), 여기서 $\text{id}(n) = n$
• $\mu * \mathbf{1} = \varepsilon$ (뫼비우스 함수는 $\mathbf{1}$의 디리클레 역원)
• $\phi * \mathbf{1} = \text{id}$ (오일러 함수의 약수 합 공식)

원시근과 위수

$\gcd(a, n) = 1$일 때, $a^k \equiv 1 \pmod{n}$을 만족하는 가장 작은 양의 정수 $k$를 $a$의 $n$에 대한 위수(Order)라 하며 $\text{ord}_n(a)$로 표기합니다.

위수의 성질

• $a^m \equiv 1 \pmod{n}$이면 $\text{ord}_n(a) \mid m$
• 특히 $\text{ord}_n(a) \mid \phi(n)$ (오일러 정리에 의해)
• $\text{ord}_n(a^k) = \frac{\text{ord}_n(a)}{\gcd(k, \text{ord}_n(a))}$

원시근

$\text{ord}_n(g) = \phi(n)$인 $g$를 $n$의 원시근(Primitive Root)이라 합니다. 원시근이 존재하면 $\{g, g^2, \ldots, g^{\phi(n)}\}$가 $n$과 서로소인 잉여류 전체를 이룹니다.

원시근이 존재하는 $n$: $1, 2, 4, p^k, 2p^k$ (홀수 소수 $p$, $k \geq 1$).

원시근의 존재성 증명 (소수 $p$인 경우)

소수 $p$에 대해 $(\mathbb{Z}/p\mathbb{Z})^{\times}$가 순환군임을 증명합니다. 핵심은 유한체 위의 다항식의 근의 개수 제한을 사용하는 것입니다.

보조정리: 체 위의 $d$차 다항식은 최대 $d$개의 근을 가집니다.

증명: $p - 1$의 각 소인수 $q$에 대해 $\text{ord}_p(a) = q^{e}$ ($q^e \| (p-1)$)인 원소 $a$가 존재함을 보입니다.

1. $x^{(p-1)/q} - 1 \equiv 0 \pmod{p}$은 최대 $\frac{p-1}{q}$개의 근을 가집니다.
2. $x^{p-1} - 1 \equiv 0 \pmod{p}$은 정확히 $p - 1$개의 근($1, 2, \ldots, p-1$ 전부)을 가집니다.
3. 따라서 $a^{p-1} \equiv 1$이지만 $a^{(p-1)/q} \not\equiv 1$인 원소 $a$가 존재합니다.
4. 이러한 $a$의 위수 $d$는 $d \mid (p-1)$이고 $d \nmid \frac{p-1}{q}$이므로 $q^e \mid d$입니다.
5. $b = a^{d/q^e}$로 놓으면 $\text{ord}_p(b) = q^e$입니다.

$p - 1 = q_1^{e_1} q_2^{e_2} \cdots q_r^{e_r}$의 각 소인수 거듭제곱에 대해 해당 위수의 원소 $b_i$를 구한 뒤, $g = b_1 b_2 \cdots b_r$로 놓으면 $\text{ord}_p(g) = p - 1$입니다 (위수가 쌍마다 서로소인 원소의 곱의 위수는 위수의 곱). $\blacksquare$

원시근을 구하는 알고리즘

소수 $p$의 원시근을 실제로 구하는 방법입니다:

1. $p - 1$을 소인수분해합니다: $p - 1 = q_1^{e_1} q_2^{e_2} \cdots q_r^{e_r}$.
2. $g = 2, 3, 4, \ldots$를 순서대로 시도하며, 각 $g$에 대해 $g^{(p-1)/q_i} \not\equiv 1 \pmod{p}$을 모든 소인수 $q_i$에 대해 확인합니다.
3. 모든 조건을 만족하면 $g$가 원시근입니다.

원시근의 개수

$n$이 원시근을 가지면, 원시근의 개수는 정확히 $\phi(\phi(n))$개입니다. 하나의 원시근 $g$를 알면, $g^k$ ($\gcd(k, \phi(n)) = 1$)가 모든 원시근을 나열합니다.

이산 로그

원시근 $g$가 주어졌을 때, $g^x \equiv a \pmod{p}$를 만족하는 $x$를 $a$의 이산 로그(Discrete Logarithm)라 합니다. $x = \text{ind}_g(a)$로 표기합니다.

이산 로그의 성질은 일반 로그와 유사합니다:

• $\text{ind}_g(ab) \equiv \text{ind}_g(a) + \text{ind}_g(b) \pmod{p-1}$
• $\text{ind}_g(a^k) \equiv k \cdot \text{ind}_g(a) \pmod{p-1}$

이산 로그를 효율적으로 계산하는 것은 매우 어려운 문제이며, 디피-헬만 키 교환 등 암호학의 기초가 됩니다.

$p$-진 수 입문

$p$-진 부치

소수 $p$와 0이 아닌 정수 $n$에 대해, $p$-진 부치(p-adic valuation) $v_p(n)$은 $n$을 나누는 $p$의 최대 거듭제곱입니다:

$p$-진 절댓값은 $|n|_p = p^{-v_p(n)}$으로 정의합니다. $|0|_p = 0$.

$p$-진 절댓값의 성질

• $|ab|_p = |a|_p \cdot |b|_p$ (곱셈적)
• $|a + b|_p \leq \max(|a|_p, |b|_p)$ (강삼각부등식, 초거리 공간)
• $|a + b|_p = \max(|a|_p, |b|_p)$ ($|a|_p \neq |b|_p$일 때)

$p$-진 전개

$p$-진 정수는 형식적 급수 $\sum_{i=0}^{\infty} a_i p^i$ ($0 \leq a_i < p$)로 표현됩니다. 일반 십진법과 달리 "오른쪽으로 무한히" 전개됩니다.

예시: $-1$의 $5$-진 전개

$-1 \equiv 4 \pmod{5}$, $-1 \equiv 24 \pmod{25}$, $-1 \equiv 124 \pmod{125}$이므로:

이것은 등비급수 $\sum_{i=0}^{\infty} 4 \cdot 5^i = \frac{4}{1-5} = -1$과 일치합니다 ($p$-진 수렴).

헨젤의 보조정리

$p$-진 해석학의 핵심 도구인 헨젤의 보조정리(Hensel's Lemma)는 합동식의 해를 "들어 올리는" 방법을 제공합니다:

$f(x) \equiv 0 \pmod{p}$의 단순근 $a$ ($f'(a) \not\equiv 0 \pmod{p}$)가 있으면, 이를 유일하게 $f(x) \equiv 0 \pmod{p^k}$의 해로 확장할 수 있습니다.

암호학의 수학적 기초

현대 공개키 암호학은 정수론의 여러 "쉬운 방향은 있지만 역방향은 어려운" 문제에 기반합니다.

일방향 함수와 수론적 난제

RSA의 수학적 구조 심화

RSA에서 $ed \equiv 1 \pmod{\lambda(n)}$을 사용하면 더 작은 $d$를 얻을 수 있습니다. 여기서 $\lambda(n) = \text{lcm}(p-1, q-1)$은 카마이클 함수입니다.

RSA가 올바르게 작동하는 이유 (CRT 증명)

$\gcd(M, n) \neq 1$인 경우에도 RSA가 정확함을 CRT로 증명합니다. $ed = 1 + k\lambda(n)$이고 $\lambda(n) = \text{lcm}(p-1, q-1)$이므로:

• $\bmod p$: $p \mid M$이면 $M^{ed} \equiv 0 \equiv M$. $p \nmid M$이면 $M^{ed} = M \cdot (M^{p-1})^{k\lambda(n)/(p-1)} \equiv M \cdot 1 \equiv M$.
• $\bmod q$: 마찬가지로 $M^{ed} \equiv M$.

CRT에 의해 $M^{ed} \equiv M \pmod{n}$. $\blacksquare$

RSA에 대한 공격과 방어

• 소인수분해 공격: 일반 수체 체법(GNFS)의 복잡도는 $L_n[1/3, (64/9)^{1/3}] = \exp\left(O\left((\ln n)^{1/3}(\ln \ln n)^{2/3}\right)\right)$
• 위너 공격: $d < \frac{1}{3}n^{1/4}$이면 연분수 공격으로 $d$를 복원할 수 있습니다. $\frac{e}{n}$의 연분수 수렴자 중 하나가 $\frac{k}{d}$가 되기 때문입니다.
• 공통 법 공격: 같은 $n$으로 서로 다른 $e_1, e_2$에 대해 $C_1 = M^{e_1}$, $C_2 = M^{e_2}$를 얻으면, $\gcd(e_1, e_2) = 1$일 때 확장 유클리드로 $M$을 복원 가능합니다.

디피-헬만 키 교환

1976년 디피(Diffie)와 헬만(Hellman)이 제안한 프로토콜로, 안전하지 않은 채널을 통해 비밀 키를 공유할 수 있습니다.

1. 큰 소수 $p$와 원시근 $g$를 공개합니다.
2. 앨리스: 비밀 정수 $a$를 선택하고 $A = g^a \bmod p$를 전송합니다.
3. 밥: 비밀 정수 $b$를 선택하고 $B = g^b \bmod p$를 전송합니다.
4. 공유 비밀키: 앨리스는 $K = B^a = g^{ab} \bmod p$, 밥은 $K = A^b = g^{ab} \bmod p$를 계산합니다.

도청자는 $g^a$와 $g^b$로부터 $g^{ab}$를 구해야 하는데, 이것이 디피-헬만 문제(DHP)이며 이산 로그 문제만큼 어렵다고 추정됩니다.

주요 정리 요약

참고자료

• Hardy, G. H. & Wright, E. M. — An Introduction to the Theory of Numbers, Oxford
• Niven, I. et al. — An Introduction to the Theory of Numbers, Wiley
• Ireland, K. & Rosen, M. — A Classical Introduction to Modern Number Theory, Springer
• Apostol, T. M. — Introduction to Analytic Number Theory, Springer
• Silverman, J. H. — A Friendly Introduction to Number Theory, Pearson
• Koblitz, N. — A Course in Number Theory and Cryptography, Springer
• Gouvêa, F. Q. — p-adic Numbers: An Introduction, Springer
• 추상대수학 — 환과 체의 관점에서 본 정수론
• 이산수학 — 정수론의 응용
• 조합론 — 수론적 함수의 조합적 해석
• 대수적 정수론 — 정수환의 일반화와 이데알 이론