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$이므로 유한한 시도끝에 종료된다.
이러한 꼴이 유한하지 않다고 하자.
$p_i$와 $q_j$는 모두 소수이므로 증가하는 형태로 정리했을 때,
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$
Comments