유클리드 호제법
유클리드 호제법 정수 $a$, $b$, $n$에 대하여 $$(a,b)=(a,b+an)$$이다. 참고로, 유클리드 호제법을 자연수 $a$를 $b$로 나눈 몫을 $q$, 나머지를 $r$라고 할 때 $(a,b)=(b,r)$로 알고 있는 사람들도 많은데, 꼭 몫이나 나머지일 필요도 없고 자연수일 필요도 없습니다. 증명을 위해서 다음 보조정리를 사용합시다. 보조정리 자연수 $p$와 $q$ 에 대하여 $p \mid q$ 이고 $q \mid p$ 이면 $p=q$이다. 증명 최대공약수 $(a,b)=p$, $(a,b+an)=q$라 하자. 먼저 $p \mid a$, $p \mid b$이므로 $p \mid b+an$을 얻는다. 따라서 $p$는 $a$와 $b+an$의 공약수. 어떤 두 수의 공약수는 그 두 수의 최대공약수의 ..
2022. 9. 3.
소수의 무한성 증명
유클리드의 증명 귀류법으로 소수가 $n$개로 유한하다고 가정하고, 그 유한한 소수들의 집합을 $P=\left\{ p_1,\,p_2,\,\cdots,\,p_n \right\}$라 하고, 새로운 수 $N=p_1\,p_2\, \cdots \,p_n+1$을 정의하자. $N$은 $p_k$ ($k$는 $n$ 이하의 자연수)보다 큰 자연수이므로 $N \notin P$이다. 따라서 $N$은 합성수이므로, $\dfrac{N}{p_k} \in \mathbb{N}$이도록 하는 $p_k$가 존재해야 한다. $$\begin{eqnarray} && \dfrac{N}{p_k}=\dfrac{p_1\,p_2\,\cdots\,p_n+1}{p_k} \\ && =p_1\,p_2\,\cdots\,p_{k-1}\,p_{k+1}\,\cdots\..
2022. 8. 23.
