Number Theory - 3.1 산술의 기본정리

정수론 3장 소수와 그 분포라는 단원을 알아보자.

---

소수의 정의와 정리

Definition 3.1

정수 $p$의 양의 약수가 $1, p$ 뿐일 때, $1$보다 큰 $p$를 소수 prime라 하고, 1보다 크고 소수가 아닌 수들을 합성수 composite 라 한다.

Theorem 3.1

$p$가 소수이고 $p \mid ab$이면, $p \mid a$ 혹은 $p \mid b$ 이다.

증명

$p \mid a$이면 옳다.

$p \nmid a$라면 $p$의 양의 약수는 $1,p$ 뿐이므로 $gcd(p,a)=1$ 이다.

유클리드 보조정리에 의해 $p \mid ab$ 이고 $gcd(a,p)=1$ 이기 때문에 $p \mid b$ 이다. $\square$

Corollary 1

$p$ 가 소수이고 $p \mid a_1,a_2,\dots,a_n$ 이면, $( 1 \le i \le n)$ 인 $i$에 대해 $p \mid a_i$ 이다.

Corollary 2

$p, q_1, q_2,\dots,q_n$ 이 소수이고, $p \mid q_1q_2\dots q_n$ 이면, $1 \le i \le n$ 인 $i$에 대해 $p=q_i$ 이다.

증명

Corollary 1에 의해 $p$ 는 어떤 $q_i$에 대해 $p \mid q_i$ 이고 소수는 $1$과 자기 자신만을 약수로 가지고 $p>1$ 이므로 $p=q_i$ 이다. $\square$

산술의 기본 정리

산술의 기본 정리는 $1$보다 큰 양의 정수 $n$을 소수들의 곱으로 유일하게 표현이 가능하다는 정리이다.

즉, 소인수분해의 꼴이 유일하다고 할 수 있다.

산술의 기본 정리

모든 $1$보다 큰 양의 정수 $n$은 인수가 나타내는 순서를 고려하지 않을 때, 소수들의 곱으로 유일하게 표현된다.

증명

$n$은 소수 또는 합성수이다. 소수라면 증명이 필요하지 않으므로 $n$이 합성수라고 하자.

$1 < d < n$ 이며 $d \mid n$인 정수 $d$가 존재한다.

이를 만족하는 모든 $d$ 중, 가장 작은 $p_1$를 선택한다.

정렬성의 원리에 의해 가장 작은 $p_1$가 존재한다.

$p_1$가 소수가 아니라고 가정하면 $d \mid p_1$ 이고 $d \mid n$인 정수가 존재해서 가장 작은수를 선택했다는 것에 모순이므로 $p_1$는 소수이다.

이제 $n=p_1n_1$ 이라고 표현한다.

$n_1$이 소수라면 우리가 원하는 결과를 얻는다.

아니라면 같은 과정을 반복해서 $n_1=p_2n_2$ 처럼 진행되어 $n_i$ 가 소수가 나올 때 까지 유한히 반복한다.

$p_i>1$이므로 유한한 시도끝에 종료된다.

$$ n=p_1p_2\cdots p_k $$

이러한 꼴이 유한하지 않다고 하자.

$$ n=p_1p_2\cdots p_r=q_1q_2\cdots q_s $$

$p_i$와 $q_j$는 모두 소수이므로 증가하는 형태로 정리했을 때,

$$ \begin{aligned} p_1 \le p_2 \le \cdots \le p_r\\ q_1 \le q_2 \le \cdots \le q_s \end{aligned} $$

Theorem 3.1-Corollary 2에 의해 $p_1$는 어떤 $q_j$ 임을 알 수 있고, 그 수들을 두 식에서 소거한다.

이런 과정을 반복할 때, $wlog.~r<s$라고 할 때, $1=q_{r+1}q_{r+2}\cdots q_s$이고 $q_i>1$ 이라 이는 모순이다.

따라서 소인수분해의 꼴은 유일하다. $\square$

$\sqrt{2}$는 무리수이다.

이를 이용해서 $\sqrt{2}$이 무리수임을 증명한다.

증명

$\sqrt{2}$이 유리수라 가정하면 $\sqrt{2}=\dfrac ab$ 이고 $gcd(a,b)=1$

$b \sqrt{2}=a$에서 양변을 제곱해서 $2b^2=a^2$

$a^2=b(2b)$이므로 $b \mid a^2$

$b \ne 1$ 일 때

어떤 $p$는 $p \mid b$ 이므로 $p \mid a$이다.

그러면 $gcd(a,b) \ge p$ 여야하는데 $p > 1$이여서 모순이다.

$b=1$

$2=a^2$인데 어떤 정수도 제곱하면 $2$가 될 수 없어 모순이다.

따라서 $\sqrt{2}$는 무리수이다. $\square$