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판, 김응태, 박승안, 경문사