3. 소수와 그 분포, 합동

3. 소수와 그 분포, 합동

양의 정수 \(p\)의 양의 약수가 \(1\)과 \(p\)뿐이면, \(p\)를 소수(prime)라고 한다. 1보다 큰 소수가 아닌 수를 합성수(composite)라고 한다.(1은 소수도 합성수도 아니다)

\(p\)가 소수이고 \(p|ab\)이면, \(p|a\) 또는 \(p|b\)이다.

증명: \(p|a\)이면 자명하고, \(p\not|a\)이면, \(p\)가 소수이므로 \(\text{gcd}(a,\,p)=1\)또는 \(\text{gcd}(a,\,p)=p\)이고, 따라서 \(\text{gcd}(a,\,p)=1\,(\because\,p\not|a)\)이므로 유클리드의 보조정리에 의해 \(p|b\)이다.

위의 정리로부터 다음의 따름정리들을 얻는다.

따름정리1: \(p\)가 소수이고 \(p|a_{1}\cdots a_{n}\,(a_{i}\in\mathbb{Z})\)이면, 적당한 \(k\)에 대하여 \(p|a_{k}\)이다. 

따름정리2: \(p,\,q_{1},\,\cdots,\,q_{n}\)이 소수이고 \(p|q_{1}\cdots q_{n}\)이면, 적당한 \(k\)에 대하여 \(p=q_{k}\)이다.

증명: 위 따름정리1에 의해 적당한 \(k\)에 대하여 \(p|q_{k}\)이므로 \(p=q_{k}\)이어야 한다.

산술의 기본정리(Fundamental Theorem of Arithmetic)

모든 양의 정수 \(n>1\)은 소수이거나 소수들의 곱이며, 유일하게 표현된다(순서를 고려하지 않음).

증명: \(n\)이 소수이면 자명하다.

\(n\)을 합성수라고 하자. \(d\in\mathbb{Z}\,(1<d<n)\)가 존재해서 \(d|n\)이다.$$S=\{d\in\mathbb{Z}\,|\,1<d<n,\,d|n\}$$이라 하자. \(n\)이 합성수이므로 \(S\neq\phi\)이고, 정수의 정렬성에 의해 \(S\)의 최소원소 \(p_{1}\)이 존재한다. \(p_{1}\)이 소수임을 보이자.

\(p_{1}\)이 합성수이면, \(q\in\mathbb{Z}\,(1<q<p_{1})\)가 존재해서 \(q|p_{1}\)이고 \(q|n\)이므로 \(q\in S\)가 되는데 \(q<p_{1}\)이므로 이는 \(p_{1}\)이 \(S\)의 최소원소라는 사실에 모순이다. 그러므로 \(p_{1}\)은 소수이어야 한다.

따라서 \(n=n_{1}p_{1}\)이고 여기서 \(p_{1}\)은 소수, \(1<n_{1}<n\)이다.

\(n_{1}\)이 소수이면 \(n\)은 소수들의 곱이고, 합성수이면 위와 같은 방법으로 소수 \(p_{2}\)가 존재하여 \(n_{1}=n_{2}p_{2}\,(1<n_{2}<n_{1})\)이다.

이 과정을 반복하면$$n_{1}>n_{2}>\cdots>1$$이고 이 과정은 유한하므로, \(n_{k-1}\)은 소수가 된다. \(p_{k}=n_{k-1}\)이라 하면$$n=p_{1}p_{2}\cdots p_{n}$$이다.

표현의 유일성을 보이기 위해$$n=p_{1}p_{2}\cdots p_{r}=q_{1}q_{2}\cdots q_{s}\,(p_{1}\leq p_{2}\leq\cdots\leq p_{r},\,q_{1}\geq q_{2}\geq\cdots\geq q_{s})$$(\(p_{i},\,q_{i}\)는 소수)라 하자. \(p_{1}|q_{1}\cdots q_{s}\)이므로 적당한 \(k\)에 대해 \(p_{1}=q_{k}\)이어야 하고, \(q_{1}\leq p_{1}\)이다. 비슷한 방법으로 \(q_{1}|p_{1}\cdots p_{r}\)이므로 적당한 \(k\)에 대하여 \(q_{1}\geq p_{1}\)이고 따라서 \(q_{1}=p_{1}\)이다. 그러면 \(p_{2}p_{3}\cdots p_{r}=q_{2}q_{3}\cdots q_{s}\)이고, 앞의 과정을 반복할 때 \(s>r\)이면,$$1=q_{r+1}\cdots q_{s}$$이고 이는 모순이다. 따라서 \(s=r\)이어야 하고, 모든 \(i\)에 대하여 \(p_{i}=q_{i}\)이다.

실제로 \(n\)의 표준형은 \(n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\)(\(p_{i}\)는 소수, \(k_{i}\)는 양의 정수, \(p_{i}<p_{i+1}\))이다.

피타고라스(Pythagoras)

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

증명: \(\sqrt{2}\)를 유리수라고 하자. 그러면 \(a,\,b\in\mathbb{Z}\,(b\neq0)\)가 존재해서$$\sqrt{2}=\frac{a}{b}\,(\text{gcd}(a,\,b)=1)$$이다. \(a^{2}=2b^{2}\)이므로 \(b|a^{2}\)이다.

\(b=1\)이면, \(2=a^{2}\)가 되는데 이 식을 만족하는 정수 \(a\)는 존재하지 않으므로 모순이다.

\(b>1\)이면, 산술의 기본정리로부터 소수 \(p\)가 존재하여 \(p|b\)가 되는데 \(p|a^{2}\)이므로 \(p|a\)이고 \(\text{gcd}(a,\,b)\geq p>1\)이므로 모순이다.

정수계수를 갖는 어떠한 다항식 \(f(n)=a_{k}n^{k}+\cdots+a_{1}n+a_{0}\)도 소수만을 만들어 낼 수 없다.

증명: 소수만을 만들어낼 수 있는 다항식 \(f\)가 존재한다고 하자. \(n_{0}\in\mathbb{N}\)에 대하여 \(f(n_{0})=p\)(소수)이고$$\begin{align*}f(n_{0}+tp)&=a_{k}(n_{0}+tp)^{k}+\cdots+a_{1}(n_{0}+tp)+a_{0}\\&=a_{k}n_{0}^{k}+a_{k-1}n_{0}^{k-1}+\cdots+a_{1}n_{0}+a_{0}+pQ(t)\\&=f(n_{0})+pQ(t)\\&=p(1+Q(t))\end{align*}$$(\(Q(t)\)는 다항식)이므로 \(Q(t)=0\)이어야 하는데 \(t\in\mathbb{N}\)는 임의의 양의 정수이고, \(Q(t)\)는 근이 무한개인 다항식이 되므로 모순이다.

\(a,\,b\in\mathbb{Z}\)와 \(n\in\mathbb{Z}\)에 대하여 \(n|a-b\)이면, \(a\)와 \(b\)는 법(mod) \(n\)에 대해 합동(congruence)이라고 하고$$a\equiv b\,(\text{mod}\,n)$$으로 나타낸다.

예를들어 \(3-24=-21=(-3)7\), \(-31-11=-42=(-6)7\)이므로$$3\equiv24\,(\text{mod}\,7),\,-31\equiv11\,(\text{mod}\,7)$$이다.

\(a,\,b\in\mathbb{Z}\)와 \(n\in\mathbb{N}\)에 대하여 \(a\equiv b\,(\text{mod}\,n)\)일 필요충분조건은 \(a\)와 \(b\)를 \(n\)으로 나눈 나머지가 같다.

증명:

\((\Rightarrow)\): \(a\equiv b\,(\text{mod}\,n)\)이므로 \(n|a-b\)이고 이는 \(a\)와 \(b\)를 \(n\)으로 나눈 나머지가 같음을 뜻한다.

\((\Leftarrow)\): \(a=q_{1}n+r\), \(b=q_{2}n+r\)이라 하자. \(a-b=(q_{1}-q_{2})n\)이므로 따라서 \(n|a-b\)이고 \(a\equiv b\,(\text{mod}\,n)\)이다.

\(n>1\), \(a,\,b\,\,c,\,d\in\mathbb{Z}\)라 하자. 그러면 다음의 성질들이 성립한다.

(a) \(a\equiv a\,(\text{mod}\,n)\)

(b) \(a\equiv b\,(\text{mod}\,n)\)이면, \(b\equiv a\,(\text{mod}\,n)\)(역도 성립)

(c) \(a\equiv b\,(\text{mod}\,n)\)이고 \(b\equiv c\,(\text{mod}\,n)\)이면, \(a\equiv c\,(\text{mod}\,n)\)

(d) \(a\equiv b\,(\text{mod}\,n)\)이고 \(c\equiv d\,(\text{mod}\,n)\)이면, \(a+c\equiv b+d\,(\text{mod}\,n)\)이고 \(ac\equiv bd\,(\text{mod}\,n)\)

(e) \(a\equiv b\,(\text{mod}\,n)\)이면, \(a+k\equiv b+k\,(\text{mod}\,n)\)이고 \(a^{k}\equiv b^{k}\,(\text{mod}\,n)\)이다.(\(k\in\mathbb{N}\))

\(41\)은 \(2^{20}-1\)의 배수이다. 그 이유는 \(2^{5}=32\equiv-9\,(\text{mod}\,41)\)이므로$$2^{20}\equiv(-9)^{4}\equiv81^{2}\equiv(-1)^{2}\equiv1\,(\text{mod}\,41)$$이고 따라서 \(2^{20}\equiv1\,(\text{mod}\,41)\)이다.

\(\displaystyle\sum_{k=1}^{100}{k!}\)을 \(12\)로 나눈 나머지를 구하자. \(3!=6\), \(4!=24\)이므로 \(n\geq4\)일 때, \(12|n!\)이고 따라서 \(\displaystyle\sum_{k=1}^{100}{k!}\)을 \(12\)로 나눈 나머지는 \(1!+2!+3!=1+2+6=9\)이다.

\(ca\equiv cb\,(\text{mod}\,n)\)이면, \(\displaystyle a\equiv b\,\left(\text{mod}\,\frac{n}{d}\right)\,(d=\text{gcd}(c,\,n))\)이다.  

증명: \(n|ca-cb\)이므로 \(k\in\mathbb{Z}\)가 존재해서 \(ca-cb=kn\)이고, \(r,\,s\in\mathbb{Z}\)가 존재해서 \(c=dr,\,n=ds\,(\text{gcd}(r,\,s)=1)\)이다. 그러면$$dr(a-b)=kds$$이고 \(ks=r(a-b)\)이므로 \(s|r(a-b)\)가 되는데 \(\text{gcd}(r,\,s)=1\)이므로 \(s|a-b\)이고 따라서 \(a\equiv b\,(\text{mod}\,s)\)\(\displaystyle\left(s=\frac{n}{d}\right)\)이다.

위의 결과로부터 다음의 따름정리들을 얻는다.

따름정리1: \(ca\equiv cb\,(\text{mod}\,n)\)이고 \(\text{gcd}(c,\,n)=1\)이면, \(a\equiv b\,(\text{mod}\,n)\)

따름정리2: \(p\)가 소수이고 \(p\not|c\), \(ca\equiv cb\,(\text{mod}\,n)\)이면, \(a\equiv b\,(\text{mod}\,p)\)

\(33\equiv15\,(\text{mod}\,9)\)에서 \(\text{gcd}(3,\,9)=3\)이므로 \(11\equiv5\,(\text{mod}\,3)\)이다.

\(-35\equiv45\,(\text{mod}\,8)\)에서 \(\text{gcd}(5,\,8)=1\)이므로 \(-7\equiv9\,(\text{mod}\,8)\)이다.

\(c=0\)이면, \(\text{gcd}(c,\,n)=n\)이고, \(c=0\)인 상황에서 \(ca\equiv cb\,(\text{mod}\,n)\)이면, \(a\equiv b\,(\text{mod}\,1)\)이 되는데, 이 식은 모든 \(a,\,b\in\mathbb{Z}\)에 대하여 자명한 식이다.(지수함수의 밑조건에 \(a\neq1\)이 붙은 것과 같다고 보면 된다)

\(4\not\equiv0\,(\text{mod}\,12)\)이고 \(3\not\equiv0\,(\text{mod}\,12)\)이나 \(4\cdot3=12\equiv0\,(\text{mod}\,12)\)이다. 이러한 수 \(3,\,4\)를 \(0\)의 약수(divisor of zero)라고 한다.

앞의 예는 명제 \(ab\equiv0\,(\text{mod}\,n)\)이면, \(a\equiv0\,(\text{mod}\,n)\) 또는 \(b\equiv0\,(\text{mod}\,n)\)이 성립하지 않음을 보여준다. 이 명제가 참이 되려면 \(\text{gcd}(a,\,n)=1\)이어야 한다.

소수 \(p\)에 대하여 \(ab\equiv0\,(\text{mod}\,p)\)이면, \(a\equiv0\,(\text{mod}\,p)\) 또는 \(b\equiv0\,(\text{mod}\,p)\)가 성립한다.

참고자료:

Elementary Number Theory 7th edition, Burton, McGraw-Hill