1. 정수의 기본성질

1. 정수의 기본성질

*여기서 자연수를 양의 정수라고 하겠다.

정수의 정렬성(well-ordering property)

양의 정수 전체의 집합 \(\mathbb{N}\)의 부분집합 \(S(\neq\phi)\)는 최소원소를 갖는다. 즉 \(a\in S\)가 존재해서 모든 \(b\in S\)에 대해 \(a\leq b\)이다.

(아르키메데스의 원리(Archimedean property)) \(a,\,b\in\mathbb{N}\)이면, 적당한 \(n\in\mathbb{N}\)이 존재해서 \(na\geq b\)이다.

증명: 이 정리가 거짓이라고 하면, 적당한 \(a,\,b\in\mathbb{N}\)에 대하여 임의의 \(n\in\mathbb{N}\)에 대해 \(na\geq b\)이다.$$S=\{b-na\,|\,n\in\mathbb{N}\}$$라 하면, \(S\)는 \(b-na\)형태의 모든 정수들을 포함하고, \(S\subset\mathbb{N}\cup\{0\}\)이므로, 정수의 정렬성에 의해 최소원소를 갖는다. 그 최소원소를 \(b-ma\)라 하자. \(S\)가 \(b-na\)형태의 모든 정수들을 포함하기 때문에 \(b-(m+1)\in S\)이고,$$b-(m+1)a=(b-ma)-a<b-ma$$인데 이는 \(b-ma\)가 \(S\)의 최소원소라는 사실에 모순이다.

제1 수학적 귀납법(First principle of Finite induction)

\(S\subset\mathbb{N}\)이라 하자.

(a) \(1\in S\)

(b) \(k\in S\)이면, \(k+1\in S\)

이면, \(S=\mathbb{N}\)이다.

증명: \(T(\neq\phi)=\mathbb{N}-S\)라 하자. \(T\neq\phi\)이므로 정수의 정렬성에 의해 최소원소 \(a\)를 갖는다. \(a\in T\)이므로 \(a\notin S\)이고, \(a\neq1\)이므로 \(a>1\)이고 \(0<a-1<a\)이므로 \(a-1\notin T\)이고 \(a-1\in S\)이다. (b)에 의해 \(a\in S\)가 되는데 \(T\cap S=\phi\)이어야 하므로 모순이다.

이 정리의 (a)를 귀납적 기저(basis for the induction), (b)를 귀납적 단계(induction step)라고 한다. 귀납적 기저가 가장 중요한데 그 이유는 (a)를 무시하고 (b)만 고려한다면 다음의 참이 아닌 등식$$1+3+5+\cdots+(2n-1)=n^{2}+3$$은 (b)만으로도 참이라는 결론을 내릴 수 있기 때문이다. 실제로 \(n=k\)일 때$$1+3+5+\cdots+(2k-1)=k^{2}+3$$이 성립한다고 하면$$\begin{align*}1+3+5+\cdots+(2k-1)+(2k+1)&=k^{2}+3+(2k+1)\\&=(k+1)^{2}+3\end{align*}$$이므로 \(n=k+1\)에 대해서도 성립하므로 수학적귀납법에 의해 성립한다고 할 수 있다는 주장이 나올 수 있다.

 

제2 수학적 귀납법(Second principle of Finite induction)

\(S\subset\mathbb{N}\)이라 하자.

(a) \(1\in S\) 

(b) \(1,\,\cdots,\,k\in S\)이면, \(k+1\in S\)

이면, \(S=\mathbb{N}\)이다. 

증명: \(T(\neq\phi)=\mathbb{N}-S\)라 하자. \(T\neq\phi\)이므로 정수의 정렬성에 의해 최소원소 \(a\)가 존재한다. \(a\notin S\)이므로 \(1,\,2,\,\cdots,\,a-1\in S\)이고, (b)에 의해 \(a\in S\)가 되는데 \(T\cap S=\phi\)이어야 하므로 모순이다.

다음의 수열은 뤼카 수열(Lucas sequence)이다.$$\begin{cases}a_{1}=1,\,a_{2}=3&\\a_{n+1}=a_{n}+a_{n-1}\,(n\geq3)&\end{cases}$$\(n\geq3\)일 때, 뤼카수열 \(a_{n}\)에 대하여 다음의 부등식이 성립한다.$$a_{n}<\left(\frac{7}{4}\right)^{n}$$이를 귀납법으로 보이자. \(\displaystyle a_{1}=1<\left(\frac{7}{4}\right)^{1}=1+\frac{3}{4},\,a_{2}=3<\left(\frac{7}{4}\right)^{2}=\frac{49}{16}=3+\frac{1}{16}\)이므로,$$a_{3}=a_{2}+a_{1}=1+3=4<\frac{7}{4}+\left(\frac{7}{4}\right)^{2}=\frac{7}{4}\cdot\frac{11}{4}=\left(\frac{7}{4}\right)^{2}\frac{11}{7}<\left(\frac{7}{4}\right)^{3}$$이고 따라서 \(n=3\)일 때, 부등식이 성립한다.

\(n=k\,(k\geq3)\)일 때 부등식 \(a_{k}<\left(\frac{7}{4}\right)^{k}\) 성립한다고 가정하자. 그러면$$a_{k+1}=a_{k}+a_{k-1}<\left(\frac{7}{4}\right)^{k}+\left(\frac{7}{4}\right)^{k-1}=\left(\frac{7}{4}\right)^{k-1}\frac{11}{4}<\left(\frac{7}{4}\right)^{k-1}\left(\frac{7}{4}\right)^{2}=\left(\frac{7}{4}\right)^{k+1}$$이므로 \(n=k+1\)일 때도 성립한다. 따라서 귀납법에 의해 부등식 \(\displaystyle a_{n}<\left(\frac{7}{4}\right)^{n}\)이 성립한다.

임의의 \(n\in\mathbb{N}\)과 \(0\leq k\leq n\)인 \(k\in\mathbb{N}\)에 대하여 이항계수(binomial coefficient)를 다음과 같이 정의한다.$$\binom n k=\frac{n!}{k!(n-k)!}$$여기서 \(n!=n(n-1)\cdots3\cdot2\cdot1\)이고, \(0!=1\)이다. \(0!=1\)이므로$$\binom n 0=\binom n n=1$$이고, 다음의 파스칼의 삼각형(Pascal's triangle)$$1\,\,1\\1\,\,2\,\,1\\1\,\,3\,\,3\,\,1\\1\,\,4\,\,6\,\,4\,\,1\\1\,\,5\,\,10\,\,10\,\,5\,\,1\\1\,\,6\,\,15\,\,20\,\,15\,\,6\,\,1\\ \cdots$$으로부터 다음의 등식이 성립한다.$$\binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}\,(1\leq k\leq n)$$이항정리(binomial theorem) 실수(또는 복소수) \(a,\,b\)와 \(n\in\mathbb{N}\)에 대하여 다음 등식이 성립한다.$$(a+b)^{n}=\sum_{k=0}^{n}{\binom{n}{k}a^{n-k}b^{k}}$$이 등식을 귀납법으로 증명하자.

\(n=1\)일 때, \(\displaystyle(a+b)^{1}=\sum_{k=0}^{1}{\binom{1}{k}a^{1-k}b^{k}}=a+b\)이므로 \(n=1\)일 때 성립한다.

\(n=m\)일 때, 등식 \(\displaystyle(a+b)^{m}=\sum_{k=0}^{m}{\binom{m}{k}a^{m-k}b^{k}}\)가 성립한다고 가정하자. 그러면$$\begin{align*}(a+b)^{m+1}&=(a+b)^{m}(a+b)=\left(\sum_{k=0}^{m}{\binom{m}{k}a^{m-k}b^{k}}\right)(a+b)\\&=a^{m+1}+\sum_{k=1}^{m}{\binom{m}{k}a^{m-k+1}b^{k}}+\sum_{k=1}^{m}{\binom{m}{k-1}a^{m-k+1}b^{k}}+b^{m+1}\\&=a^{m+1}+\sum_{k=1}^{m}{\left\{\binom{m}{k}+\binom{m}{k-1}\right\}a^{m-k+1}b^{k}}+b^{m+1}\\&=a^{m+1}+\sum_{k=1}^{m}{\binom{m+1}{k}a^{m-k+1}b^{k}}+b^{m+1}\\&=\sum_{k=0}^{m+1}{\binom{m+1}{k}a^{m+1-k}b^{k}}\end{align*}$$이므로 \(n=k+1\)일 때도 성립하고 따라서 이항정리가 성립한다.

나눗셈 알고리즘(The divisor algorithm)

\(a,\,b\in\mathbb{Z}\,(b>0)\)에 대하여 유일한 \(q,\,r\in\mathbb{Z}\)가 존재하여$$a=qb+r\,(0\leq r<b)$$이다. 여기서의 정수 \(q,\,r\)을 각각 \(a\)를 \(b\)로 나눈 몫(quotient), 나머지(remainder)라고 한다.

증명:$$S=\{a-xb\,|\,x\in\mathbb{Z},\,a-xb\geq0\}$$이라 하자. \(x=-|a|\)로 두면$$a-(-|a|)b=a+|a|b>a+|a|\geq0$$이므로 \(S\neq\phi\)이고 \(a-xb\in S\)이다. \(S\neq\phi\)이므로 \(S\)는 최소원소를 갖는다. 그 최소원소를 \(r\)이라 하자. \(S\)의 정의에 의해 \(q\in\mathbb{Z}\)가 존재해서$$r=a-qb\,(r\geq0)$$이다. \(r<b\)가 성립함을 보이자. \(r\geq b\)라 하면$$a-(q+1)b=(a-qb)-b=r-b\geq0$$이므로 \(a-(q+1)b\in S\)가 되는데 \(a-(q+1)b<a-qb=r\)이 되므로 이는 \(r\)이 \(S\)의 최소원소라는 사실에 모순이다. 그러므로 \(r<b\)이어야 하고 따라서 \(0\leq r<b\)이다.

이렇게 \(q,\,r\)이 존재함을 보였고 이제 유일함을 보여야 한다.

\(a=bq+r=bq'+r'\,(a\leq r,\,r'<b)\)라 하자. 그러면 \(r-r'=b(q'-q)\)이고 \(|r-r'|=b|q'-q|\)가 성립하는데 \(0\leq r<b\), \(-b\leq-r'\leq0\)이므로 \(-b<r-r'<b\)이고 \(|r-r'|<b\)이다. 그러면 \(b|q'-q|<b\)이고 \(|q'-q|<1\)이 되는데 \(q,\,q'\)은 정수이므로 \(|q'-q|=0\)이어야 하고 따라서 \(q=q'\)이고 \(r=r'\)이다.

정수 \(q\)에 대하여 \(a=2q\)형태인 수 \(a\)를 짝수(even), \(a=2q+1\)형태인 수 \(a\)를 홀수(odd)라고 한다. 

\(a\in\mathbb{N}\,(a>1)\)에 대하여 \(\displaystyle\frac{a(a^{2}+2)}{3}\in\mathbb{N}\)이다.

나눗셈 알고리즘으로부터 \(a=3q,\,3q+1,\,3q+2\)이고

\(a=3q\)일 때, \(\displaystyle\frac{a(a^{2}+2)}{3}=q(9q^{2}+2)\),

\(a=3q+1\)일 때, \(\displaystyle\frac{(3q+1)(9q^{2}+6q+3)}{3}=(3q+1)(3q^{2}+2q+1)\)

\(a=3q+2\)일 때, \(\displaystyle\frac{(3q+2)(9q^{2}+12q+6)}{3}=(3q+2)(3q^{2}+4q+2)\)

이므로 따라서 \(\displaystyle\frac{a(a^{2}+2)}{3}\in\mathbb{N}\)이다.  

참고자료:

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

정수론 8판, 김응태, 박승안, 경문사