Number Theory - 2.2 나눗셈 정리

나눗셈 정리

주어진 정수 $a,\,b$에 대해 $b>0$, 다음을 만족하는 유일한 정수 $q,\,r$이 존재한다.

$$ a=qb+r~~~(0 \le r < b) $$

몫 $q$ 를 quotient, 나머지 $r$ 을 remainder라 부른다.

증명

1- 다음 집합 $S$가 공집합이 아님을 먼저 보인다.

$$ S=\left\{ a-xb~\vert~ x\text{는 정수},\,a-xb \ge 0 \right\} $$

$b \ge 1$ 이므로 $\lvert a \rvert b \ge \lvert a \rvert$ 이기 때문에

$a-(-\lvert a \rvert)b=a+\lvert a \rvert b \ge a + \lvert a \rvert \ge 0$ $x=-\lvert a \rvert$라고 하면 $a-xb \in S$ 이기 때문에 $S \ne \varnothing$ 이다.

$S$의 원소는 음이 아닌 정수이기 때문에 정렬성의 원리에 의해 $S$에서 가장 작은 원소가 있고, 그 원소를 $r$ 이라고 하자.

또한, $S$의 정의에 의해 $r=a-xb$ 를 만족하는 $x=q$ 라고 하자. $(r=a-qb)$

2- $r<b$ 임을 보이자.

$r \ge b$ 라면 $r-b \ge 0$이고

$$ r-b=(a-qb)-b=a-(q+1)b $$

이렇게 되면 $a-(q+1)b \in S$ 가 되는데,

$a-(q+1)b=a-qb-b$ 이고 $b>0$ 이라서 $r$ 보다 작은 원소가 존재하게 되기 때문에 모순이다.

따라서 $r<b$ 이다.

3- 이제 $r,\,q$의 유일성을 보이자.

$a=qb+r=q’b+r’~(0 \le r,r’ < b)$ 라고 해보자.

$r-r’=(q’-q)b$ 이고, 곱의 절댓값은 절댓값의 곱과 같으므로

$\qquad \lvert r-r’ \rvert = \lvert q’-q \rvert b$

$-b<-r’ \le 0$과 $0 \le r < b$ 를 더하면

$$ \begin{aligned} -b < r-r' < b \\ \therefore \lvert r-r' \rvert < b \end{aligned} $$

$\lvert r-r’ \rvert = \lvert q’-q \rvert b$ 이므로 $\lvert q’-q\rvert b < b$

즉, $\lvert q’-q \rvert = 0$ 이여야 하기 때문에 $q’=q$ 이고 이로부터 $r=r’$ 도 보여져서 항상 $r$과 $q$는 유일하다.

---

$a=qb+r~(0 \le r < b,~~b>0)$ 에서 확장시켜 $b<0$ 인 경우에도 적용이 가능하다.

$$ b \ne 0 \text{이면 다음 식을 만족하는 유일한 정수 }r, q\text{가 존재한다.}\\ a=qb+r~(0 \le r < \lvert b \rvert) $$

$b$ 가 양수이면 나눗셈 정리에 의해 성립한다.

$b$가 음수이면 나눗셈 정리에 의해

$\qquad a=q’\lvert b \rvert+r~(0 \le r < b)$ 를 만족하는 $q’$ 가 유일히 존재함이 보여지므로

$\qquad q=-q’$ 라고 하면 식이 성립한다.

나눗셈 정리의 활용

나눗셈 정리도 중요하지만, 그로 인해 파생되는 여러가지 강력한 증명법들이 있다.

예를 들어, 완전제곱수를 4로 나눈 나머지는 0이나 1이다.

증명

정수 $a$는 짝수일 때 $2k$, 홀수일 때 $2k+1$ 로 표현된다.

나눗셈 정리에 의해 이를 만족하는 $k$ 가 유일히 존재하기 때문이다.

$(2k)^2=4k^2 \equiv 0~(mod~4)$

$(2k+1)^2=4k^2+4k+1 \equiv 1~(mod~4) \square$