1.1. 정수의 나누어짐(divisibility)

aaa

정의.

두 정수 $a,\, b \in \Z$에 대하여, $b=ac$를 만족하는 정수 $c \in \Z$가 존재하면, $b$는 $a$로 나누어(divisible)진다고 하고, 이 경우 $a \mid b$와 같이 나타낸다. 만약 $b$가 $a$로 나누어 지지 않는 경우, $a \nmid b$로 나타낸다.

  예제. 예를 들어 $-12 = 4(-3)$이므로 $4 \mid -12$이고 $-3 \mid -12$임을 알 수 있다. 반면 $7=2c$를 만족하는 정수 $c \in \Z$는 존재하지 않으므로 $2 \nmid 7$이다..

  위 정의에 따라 다음의 사실들을 어렵지 않게 증명할 수 있다.

 

정리.

세 정수 $a,\,b,\,c \in \Z$에 대하여 다음이 성립한다.

  1. $a \mid 0$, $1 \mid a$, $a \mid a$.
  2. $a \mid b$이고 $b \mid c$이면, $a \mid c$.
  3. $a \mid b$이고 $b \mid a$이면, 그리고 오직 이 때에만 $a = \pm b$.
  4. $a \mid b$이고 $b \neq 0$이면, $\abs{a} \leq \abs{b}$. 따라서 $0$이 아닌 정수는 유한개의 인수를 갖는다.
  5. $a \mid b$이고 $a \mid c$이면, 임의의 정수 $m,\, n \in \Z$에 대하여 $a \mid mb + nc$.
  6. $a \mid b$이면, 임의의 정수 $n \in \Z$에 대하여 $na \mid nb$.

  정수가 갖고 있는 또 다른 중요한 성질 중 하나는 아래에서 설명할 나눗셈 정리이다.

 

정리. 나눗셈 정리(division theorem)

두 정수 $a,\,b \in \Z$에 대하여 $a \neq 0$이라 하자. 그러면 다음 등식을 만족하는 정수 정수 $p,\,q \in \Z$가 유일하게 존재한다. \[ b = aq + r, \qquad 0 \leq r < \abs{a} \] 이 때, 두 정수 $q$와 $r$을 각각 $b$를 $a$로 나누었을 때의 몫(quotient)과 나머지(remainder)라 한다.

  증명. 먼저 두 정수 $p,\,q \in \Z$의 존재성을 증명하자: 우선 $a>0$인 경우, $q = \lfloor \frac{b}{a} \rfloor$로 정의한다. (단, $\lfloor x \rfloor$는 $x$의 정수부분을 나타낸다.) 그러면 자명하게 $q \leq \frac{b}{a} < q+1$이 성립한다. 이제 $r = b-aq$로 정의하자. 그러면 $b = aq + r$이 성립하고 \[ aq \leq b < aq + a \implies 0 \leq b-aq < a \] 즉, $a \leq r < a$가 성립한다. $a < 0$인 경우에는 $q = -\lfloor -\frac{b}{a} \rfloor$로 잡으면 같은 결과를 얻을 수 있다.

이제 $p,\,q \in \Z$의 존재성을 증명하기 위해 $b = aq_1 + r_1 = aq_2 + r_2$이고 $0 \leq r_1,\, r_2 < \abs{a}$라 가정하자. 그러면 $a(q_1-q_2) = r_2-r_1$을 얻는다. 이제 $q_1 \neq q_2$라고 가정하면 $\abs{q_1-q_2} \geq 1$이고 \[ \abs{a} > \abs{r_2-r_1} = \abs{a}\abs{q_1-q_2} \geq \abs{a} \] 이 되어 모순이 발생한다. 그러므로 $q_1 = q_2$이고, 따라서 $r_1 = r_2$ 또한 얻는다..

  예제. $n \in \Z$이 임의의 정수라 하자. 그러면 나눗셈 정리에 의해 유일한 정수 $k \in \Z$가 존재하여 $n = 2k$ 또는 $n = 2k+1$의 형태를 가져야만 한다. 이 때, $n=2k$의 형태로 나타나는 수를 짝수(even number), 반대로 $n = 2k+1$의 형태로 나타나는 수를 홀수(odd number)로 정의한다.

  예제. $n \in \Z$이 임의의 정수라 하자. 이제 $n,\, n+1,\, n+2$ 중에는 반드시 $3$으로 나누어지는 수가 존재함을 증명하자: 우선 나눗셈 정리에 의해 $n=3q+r$을 만족하는 유일한 정수 $p,\,q \in \Z$가 존재한다. 여기서 $r$은 $0 \leq r < \abs{3}$을 만족해야 하므로, $0,\,1,\,2$ 중의 하나이다. 먼저 $r=0$인 경우, $n = 3q$가 되어 $n$이 $3$으로 나누어진다. $r=1$인 경우는 $n+2 = (3q+1) + 2 = 3(q+1)$이 되어 $n+2$가 $3$으로 나누어진다. 마지막으로 $r=2$인 경우, $n+1 = (3q+2)+1 = 3(q+1)$이 되어 $n+1$이 $3$으로 나누어진다. 따라서 $r$이 어떠한 값을 가지더라도 $n,\, n+1,\, n+2$ 중에는 반드시 $3$으로 나누어지는 수가 존재한다..

1.3
위로
2.2