ℤ정수론
II. 나눗셈과 소수 · 3/16

산술의 기본정리

소수, 유일인수분해

읽음 0/0 갱신 2026-06-30

개요 — 동기·문제의식

$60$ 을 소인수분해하면 $2^2\cdot3\cdot5$ 다. 다른 방법으로 분해해도(예: $60=6\cdot10=2\cdot3\cdot2\cdot5$) 순서를 무시하면 결국 똑같은 소인수들 $\{2,2,3,5\}$ 로 귀착된다. 너무 당연해 보이는 이 사실 — 소인수분해는 항상 유일하다 — 이 사실은 사실 전혀 자명하지 않다. 정수를 닮은 다른 수 체계(예: $\{1,4,7,10,13,\dots\}$ 처럼 $3$으로 나눈 나머지가 $1$인 자연수만 모은 집합)에서는 유일분해가 깨질 수 있다 — 예를 들어 그 체계 안에서 $100=4\times25=10\times10$ 처럼 "기약원소"로의 분해가 여러 방식으로 나올 수 있다. 정수가 이런 병리를 피하는 이유는 우연이 아니라 나눗셈 정리와 Bezout 항등식(나눗셈과 최대공약수)이라는 구체적인 도구 덕분이다. 산술의 기본정리(FTA)는 "소수가 정수의 곱셈적 원자다"라는 명제를 정확히 증명하며, 이 위키의 거의 모든 후속 결과 — gcd/lcm의 계산, 곱셈적 함수(수론적 함수), Euler $\varphi$(오일러 φ 함수와 정리), RSA의 안전성(모듈러 거듭제곱과 RSA) — 가 이 유일성 위에 서 있다.

직관 — 왜 "원자"라는 비유가 맞는가

화학에서 모든 분자는 원자들의 특정한 조합으로 유일하게 분해된다(물 분자는 항상 정확히 $H_2O$). 정수론에서 소수는 이 원자 역할을 한다 — 모든 정수는 소수들의 곱으로 분해되고, 그 "조성"(어떤 소수가 몇 개씩)은 분해 방법과 무관하게 항상 같다. 이 유일성이 성립하려면 두 가지가 필요하다: (1) 분해가 항상 가능하다(존재성 — 합성수를 계속 쪼개면 결국 소수에 도달해야 한다), (2) 분해 결과가 단 하나다(유일성 — 다른 길로 쪼개도 같은 소인수 목록이 나와야 한다). 존재성은 직관적으로 명백해 보이지만, 유일성은 그렇지 않다 — 그 증명의 핵심 열쇠가 바로 Euclid 보조정리: "소수가 곱을 나누면 인수 중 하나를 나눈다"는, 소수만이 가진 특별한 성질이다. 합성수는 이 성질이 없다 — $6\mid 4\times9=36$ 이지만 $6\nmid4$ 이고 $6\nmid9$ 다. 소수만이 곱을 "뚫고 들어가" 인수 하나를 직접 나눈다는 이 특별함이 유일분해를 가능케 하는 진짜 이유다.

정의

용어 정의
소수(prime) $p$ $p>1$ 이고 양의 약수가 $1$ 과 $p$ 뿐인 정수
합성수(composite) $n>1$ 이고 소수가 아닌 정수(즉 $1<a<n$, $a\mid n$ 인 $a$ 존재)
$1$ 소수도 합성수도 아님(단위원, 약수가 하나뿐)
표준 소인수분해 $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ ($p_1<p_2<\cdots<p_k$ 서로 다른 소수, $e_i\ge1$)

왜 $1$ 을 소수에서 제외하는가. 만약 $1$ 을 소수로 인정하면 $6=2\cdot3=1\cdot2\cdot3=1^{100}\cdot2\cdot3$ 처럼 같은 수가 무한히 많은 "서로 다른" 분해를 갖게 되어, 이 페이지의 핵심 주장인 "유일성"이 정의상 무너진다. $1$ 을 배제하는 관례는 임의적인 게 아니라 정리를 깔끔하게 만들기 위한 필수 장치다.

주요 정리

정리 (Euclid 보조정리).1 $p$ 가 소수이고 $p\mid ab$ 이면 $p\mid a$ 또는 $p\mid b$.

증명 보기

증명. $p\nmid a$ 라 가정하자. $p$ 가 소수이므로 $a$ 와 $p$ 의 공약수는 $1$ 또는 $p$ 뿐인데 $p\nmid a$ 이니 $\gcd(p,a)=1$. Bezout 항등식으로 $1=px+ay$ 인 정수 $x,y$ 존재. 양변에 $b$ 를 곱하면 $b=pbx+aby$. 우변의 첫 항은 명백히 $p$ 의 배수이고, 둘째 항 $aby=(ab)y$ 는 가정 $p\mid ab$ 에 의해 $p$ 의 배수. 따라서 $b=p(\cdots)$, 즉 $p\mid b$. $\blacksquare$ 따름 (세 개 이상으로 확장). $p\mid a_1a_2\cdots a_n$ 이면 어떤 $i$ 에 대해 $p\mid a_i$ (귀납법: $p\mid a_1(a_2\cdots a_n)$ 에 보조정리를 적용해 $p\mid a_1$ 이거나 $p\mid(a_2\cdots a_n)$, 후자면 다시 적용).

정리 (산술의 기본정리, FTA).2 $1$ 보다 큰 모든 정수는 소수들의 곱으로 표현되며, 그 표현은 인수의 순서를 무시하면 유일하다.

증명 보기

증명 — 존재성 (강한 귀납법). $n=2$: 그 자체로 소수이므로 분해 끝. $n>2$ 이고 $2,\dots,n-1$ 까지 모든 정수가 분해 가능하다고 가정(강한 귀납가정). $n$ 이 소수면 끝. 합성수면 $n=ab$ ($1<a,b<n$) 로 쓸 수 있고, 귀납가정에 의해 $a,b$ 각각 소인수분해를 가지므로 그것들을 합치면 $n$ 의 소인수분해를 얻는다.

증명 보기

증명 — 유일성. $n=p_1p_2\cdots p_r=q_1q_2\cdots q_s$ 가 두 소인수분해라 하자($p_i,q_j$ 모두 소수, 중복 허용). $p_1\mid n=q_1\cdots q_s$ 이므로 Euclid 보조정리(확장판)에 의해 $p_1\mid q_j$ 인 $j$ 가 존재 — $q_j$ 가 소수이므로 $p_1=q_j$. 양변에서 이 공통 인수를 하나씩 소거하면 $p_2\cdots p_r=q_1\cdots\widehat{q_j}\cdots q_s$ (모자는 제외 표시). 이 과정을 반복하면 양쪽의 소인수가 하나씩 정확히 짝지어 소거되고, 만약 한쪽이 먼저 다 소거되어 $1$ 이 되는데 다른 쪽에 인수가 남아 있다면 그 잔여 곱이 $1$ 이라는 모순(소수의 곱은 $1$보다 크다)에 도달한다. 따라서 $r=s$ 이고 (순서를 맞추면) $p_i=q_i$ 전부. $\blacksquare$

정리 (소인수 판정 — 시험 나눗셈의 한계).3 $n$ 이 합성수이면 $n$ 을 나누는 소수 $p$ 로서 $p\le\sqrt n$ 인 것이 적어도 하나 존재한다.

증명 보기

증명. $n=ab$ ($1<a\le b<n$). $a\le b$ 이고 $ab=n$ 이므로 $a^2\le ab=n$, 즉 $a\le\sqrt n$. $a$ 의 임의의 소인수 $p$ 는 $p\le a\le\sqrt n$ 을 만족하고 $p\mid a\mid n$ 이므로 $p\mid n$. 실용적 의미. $n$ 이 소수인지 확인하려면 $2$ 부터 $\sqrt n$ 까지의 소수로만 시험 나눗셈을 하면 충분하다 — $\sqrt n$ 을 넘는 소인수가 있다면 반드시 $\sqrt n$ 이하의 짝(공범)이 있어야 하기 때문이다.

예제

예제 1 (소인수분해, 시험 나눗셈). $9105293$: $\sqrt n\approx3017.5$ 까지 시험하면 $9105293=37\cdot43\cdot59\cdot97$. (검산: $37\times43=1591$, $59\times97=5723$, $1591\times5723=9105293$ ✓.)

예제 2 (약수의 개수, FTA 응용). $n=p_1^{e_1}\cdots p_k^{e_k}$ 의 모든 양의 약수는 각 소수의 지수를 $0$부터 $e_i$ 까지 독립적으로 고르는 것과 일대일 대응 — 약수 개수 $\tau(n)=(e_1+1)(e_2+1)\cdots(e_k+1)$. $360=2^3\cdot3^2\cdot5^1$: $\tau(360)=4\cdot3\cdot2=24$ 개.

예제 3 (gcd·lcm을 인수분해로). $12=2^2\cdot3$, $18=2\cdot3^2$. $\gcd$ = 각 소수의 최소 지수: $2^{\min(2,1)}\cdot3^{\min(1,2)}=2^1\cdot3^1=6$. $\operatorname{lcm}$ = 최대 지수: $2^{\max(2,1)}\cdot3^{\max(1,2)}=2^2\cdot3^2=36$. 검산: $\gcd\cdot\operatorname{lcm}=6\cdot36=216=12\cdot18$ ✓(나눗셈과 최대공약수의 항등식).

예제 4 ($\sqrt2$ 의 무리성 — Euclid 보조정리의 고전 응용). $\sqrt2=a/b$ (기약분수, $\gcd(a,b)=1$) 라 가정. 양변 제곱: $2b^2=a^2$. 좌변이 $2$의 배수이므로 $a^2$도 $2$의 배수 → Euclid 보조정리($p=2$)로 $2\mid a$ → $a=2k$ → $2b^2=4k^2$ → $b^2=2k^2$ → 같은 논리로 $2\mid b$. $a,b$ 모두 짝수이면 $\gcd(a,b)\ge2$, 기약분수 가정에 모순. 따라서 $\sqrt2$ 는 유리수가 아니다.

예제 5 (완전제곱수의 지수 판정). $n$ 이 완전제곱수 $\iff$ 모든 소인수의 지수가 짝수. $n=2^4\cdot3^2\cdot5^6$ 은 지수가 전부 짝수 → 완전제곱($n=(2^2\cdot3\cdot5^3)^2$). $n=2^4\cdot3^3$ 은 $3$의 지수가 홀수 → 완전제곱 아님.

예제 6 (이항계수가 소수로 나뉨, FTA·Euclid 보조정리 응용). $p$ 가 소수, $0<k<p$ 이면 $\binom{p}{k}=\dfrac{p!}{k!(p-k)!}$ 는 항상 $p$ 의 배수다. 왜냐하면 분자 $p!$ 에는 소인수 $p$ 가 정확히 하나 들어 있는데, 분모의 $k!(p-k)!$ 을 이루는 인수들은 전부 $p$ 보다 작아 $p$ 를 소인수로 갖지 않으므로, 나눗셈 후에도 $p$ 가 약분되지 않고 남는다. 예: $\binom73=35=5\cdot7$ — 정확히 $7$의 배수.

흔한 오해와 함정

큰 그림 / 연결

FTA는 이 위키의 진짜 "기초공사"다. Euclid 보조정리는 나눗셈과 최대공약수의 Bezout 항등식에서 직접 나오고, 거꾸로 FTA는 이후 모든 곱셈적 구조의 근거가 된다 — 수론적 함수의 $\tau,\sigma,\varphi$ 가 소수거듭제곱의 곱으로 분해되는 이유, 오일러 φ 함수와 정리의 $\varphi$ 계산 공식, gcd·lcm을 인수분해로 즉시 구하는 트릭(예제 3) 모두 FTA의 직접 응용이다. prime distribution은 "소수가 정확히 무엇인가"를 넘어 "소수가 얼마나 많고 어떻게 퍼져 있는가"를 묻는 다음 단계다. 가장 인상적인 일반화는 가우스 정수 $\mathbb{Z}[i]$ — 복소수 영역으로 정수를 확장해도 (적절히 정의된 "소수"에 대해) 유일인수분해가 살아남는다는 사실이며, 이는 algebra 위키의 euclidean-pid-ufd(유클리드 정역 → 주 이데알 정역 → 유일인수분해 정역이라는 일반 위계)가 다루는 추상적 정리의 가장 구체적인 사례다. 모든 정수환이 유일인수분해를 갖는 것은 아니라는 사실(병리적 반례가 존재)이 이 정리를 더욱 특별하게 만든다.

연습문제

  1. $1234$ 와 $5040$ 을 소인수분해하라.
  2. $720$ 의 약수 개수와 약수의 합을 구하라.
  3. Euclid 보조정리로 $\sqrt3$ 이 무리수임을 보여라.
  4. $n$ 이 합성수면 $\sqrt n$ 이하인 소인수가 있음을 (직접 증명을 재구성해) 보여라.
  5. $p$ 가 소수일 때 $\binom{p}{k}$ ($0<k<p$)가 $p$ 로 나뉨을 보여라.
  6. $n=2^6\cdot3^4\cdot5^2$ 이 완전제곱수인지 확인하고, 그렇다면 제곱근을 구하라.
  7. $\gcd(2^3\cdot3^2\cdot7,\ 2\cdot3^3\cdot5)$ 와 $\operatorname{lcm}$ 을 인수분해로 구하라.
  8. $100!$ 의 소인수분해에서 $2$ 의 지수를 구하라(Legendre 공식 $\sum_{i\ge1}\lfloor n/p^i\rfloor$ 사용).
힌트 / 정답
  1. $1234=2\cdot617$ ($617$은 소수); $5040=2^4\cdot3^2\cdot5\cdot7$.
  2. $720=2^4\cdot3^2\cdot5$ → 약수 개수 $5\cdot3\cdot2=30$개; 약수 합 $\sigma(720)=\dfrac{2^5-1}{2-1}\cdot\dfrac{3^3-1}{3-1}\cdot\dfrac{5^2-1}{5-1}=31\cdot13\cdot6=2418$.
  3. $\sqrt3=a/b$ 기약분수 가정 → $3b^2=a^2$ → $3\mid a^2$ → (Euclid 보조정리, $p=3$) $3\mid a$ → $a=3k$ → $3b^2=9k^2$ → $b^2=3k^2$ → $3\mid b$ → $a,b$ 모두 $3$의 배수, 기약 가정에 모순.
  4. $n=ab$ ($1<a\le b<n$)이면 $a^2\le ab=n$ → $a\le\sqrt n$; $a$의 소인수 $p$는 $p\le a\le\sqrt n$이고 $p\mid n$.
  5. $\binom pk=\dfrac{p!}{k!(p-k)!}$ 의 분자에 소인수 $p$가 정확히 한 번 들어있고, 분모의 모든 인수는 $p$보다 작아 $p$를 인수로 갖지 않으므로 약분되지 않고 남는다 → $p\mid\binom pk$.
  6. 모든 지수($6,4,2$)가 짝수 → 완전제곱. $\sqrt n=2^3\cdot3^2\cdot5=8\cdot9\cdot5=360$.
  7. $\gcd=2^{\min(3,1)}\cdot3^{\min(2,3)}\cdot5^{\min(0,1)}\cdot7^{\min(1,0)}=2^1\cdot3^2\cdot5^0\cdot7^0=18$. $\operatorname{lcm}=2^3\cdot3^3\cdot5\cdot7=8\cdot27\cdot5\cdot7=7560$.
  8. $\lfloor100/2\rfloor+\lfloor100/4\rfloor+\lfloor100/8\rfloor+\lfloor100/16\rfloor+\lfloor100/32\rfloor+\lfloor100/64\rfloor=50+25+12+6+3+1=97$.

관련 개념

  1. 원전 소개 — Silverman ch.7 [synthesis] — Euclid 보조정리($p\mid ab\Rightarrow p\mid a$ 또는 $p\mid b$)와 그 증명이 ch.6의 Bezout 항등식에 의존함. ↩

  2. 원전 소개 — Silverman ch.7 [synthesis] — 산술의 기본정리(존재성은 강한 귀납법, 유일성은 Euclid 보조정리의 반복 적용). ↩

  3. 원전 소개 — Silverman ch.7 — "if n is not itself prime, then there must be a prime p ≤ √n that divides n." 시험 나눗셈에 의한 소수 판정의 근거. ↩