소수와 소인수분해

1보다 크고 1과 자기 자신만으로 나누어떨어지는 수를 소수라 한다. 소수는 곱셈의 ‘원자’이다. 모든 자연수는 소수의 곱으로 단 한 가지 방법으로 분해되며, 소수는 무한히 많다.

핵심 개념

  • 소수: $2,3,5,7,11,\dots$ 소수가 아닌 $2$ 이상의 수는 합성수, $1$은 소수도 합성수도 아니다.
  • 에라토스테네스의 체: $2$부터 차례로 소수의 배수를 지워 나가면 남는 수가 소수이다. $n$이 합성수이면 $\sqrt n$ 이하의 소인수를 가지므로, $\sqrt N$까지의 소수의 배수만 지우면 된다.
1부터 100까지의 수 중 소수 25개를 표시한 표
100 이하의 소수는 25개이다

핵심 정리

  • 유클리드 보조정리: 소수 $p$가 $ab$를 나누면 $p\mid a$ 또는 $p\mid b$이다.
  • 산술의 기본정리: 2 이상의 모든 자연수는 소수의 곱으로 나타낼 수 있고, 그 방법은 순서를 무시하면 하나뿐이다.
  • 유클리드의 정리: 소수는 무한히 많다.
증명 보기

유클리드 보조정리. $p\nmid a$이면 $p$와 $a$는 서로소이므로 베주 항등식(최대공약수 단원)에 의해 $ax+py=1$인 정수 $x,y$가 있다. 양변에 $b$를 곱하면 $abx+pby=b$이다. $p\mid ab$이므로 왼쪽의 두 항이 모두 $p$의 배수이고, 따라서 $p\mid b$이다.

존재. 가장 작은 반례 $n$이 있다고 하자. $n$은 소수가 아니므로 $n=ab$ ($1<a,b<n$)이고, $a$와 $b$는 $n$보다 작으므로 소수의 곱으로 쓸 수 있다. 그러면 $n$도 소수의 곱이 되어 모순이다.

유일성. $p_1p_2\cdots p_r=q_1q_2\cdots q_s$라 하자. $p_1$이 오른쪽을 나누므로 유클리드 보조정리를 반복하면 $p_1$은 어떤 $q_j$를 나누고, $q_j$는 소수이므로 $p_1=q_j$이다. 양변에서 지우고 같은 과정을 반복하면 두 분해가 같음을 알 수 있다.

소수의 무한성. 소수가 $p_1,\dots,p_n$뿐이라고 가정하고 $N=p_1p_2\cdots p_n+1$을 생각하자. $N$을 어느 $p_i$로 나누어도 나머지가 $1$이므로, $N$의 소인수는 목록에 없는 새로운 소수이다. 모순이므로 소수는 무한히 많다. $\blacksquare$

예제

  • $360=2^3\cdot3^2\cdot5$이므로 약수의 개수는 $(3+1)(2+1)(1+1)=24$, 약수의 합은 $(1+2+4+8)(1+3+9)(1+5)=15\cdot13\cdot6=1170$
  • $\sqrt2$는 무리수: $\sqrt2=\frac ab$이면 $a^2=2b^2$이다. 소인수분해에서 왼쪽의 $2$의 지수는 짝수, 오른쪽은 홀수이므로 유일성에 모순이다.

더 알아보기: 소수는 얼마나 많을까

소수는 무한히 많지만 점점 드물어진다. $x$ 이하의 소수의 개수 $\pi(x)$는 대략 $\frac{x}{\ln x}$이며, 이를 소수 정리라 한다(1896년 아다마르, 드라 발레푸생 증명).

x 이하의 소수의 개수 π(x)와 x/ln x 그래프
$\pi(x)$와 $\frac{x}{\ln x}$: 비율이 $1$에 가까워진다

확인 문제

$n^2+n+41$은 $n=0,1,\dots,39$에서 모두 소수이다. 모든 자연수 $n$에서 소수일까?

풀이 보기

아니다. $n=40$이면 $1600+40+41=1681=41^2$이다. ($n=41$이면 $41\times43$) 몇 개의 예에서 성립한다고 모든 경우에 성립하는 것은 아니며, 이것이 수학에서 증명이 필요한 이유이다.

정리

  • 소인수분해는 유일하다 (산술의 기본정리).
  • 소수는 무한히 많다.
알림: 보호된 콘텐츠입니다.