[Number Theory] 1. The Division Algorithm(나눗셈 알고리즘)

0. Introduction

---

집합 위에 연산들을 정의한 것을 대수적 구조라고 한다. 앞으로 기초적인 정수론 내용들을 공부한 후 현대대수학으로 넘어가려한다. 그 전에 우리가 자연스럽게 쓰고 있는 자연수에 대해 간단하게 알아보려고 한다. 왜냐하면 아래에서 다루겠지만 자연수의 "덧셈의 역원"을 정의한 것이 "정수 집합"이기 때문이다.

우리는 초등학생때 몫과 나머지가 있는 자연수의 나눗셈에 대해 배운다. 이것은 직관적으로 매우 당연한 것이라 받아드릴 수 있지만 당연한 것이 아니며 수학적인 증명이 필요하다.

따라서

1. 페아노 공리계
2. Division Algorithm
3. Division Algorithm의 증명

순으로 포스팅을 해보려 한다.

1. Peano's Axioms 페아노 공리계

---

우리는 어떤 것들을 세고 정량화 할 때 자연스럽게 1, 2, 3, ...과 같은 자연수들을 사용해왔다.

중요한점은, 이러한 1, 2, 3과 같은 것들은 우리가 다루기 쉽게 "자연수"라는 기호들로 모델링 한 것들이라는 것이다.

먼저 페아노 공리계를 통해 자연수를 정의하려 시도하였다.

Peano's Axioms(페아노 공리계)

---

다음 5가지의 성질들을 만족하는 "집합 $\mathbb{N}$"을 "자연수"라고 한다.

1) 집합 $\mathbb{N}$은 "1"이라는 특별한 원소를 가진다.

2) $\mathbb{N}$의 임의의 원소 n에 대해 "그 다음 수 "$n^+$"도 $\mathbb{N}$의 원소이다."

3) $n^{+} = 1$인 $\mathbb{N}$의 원소는 없다. 즉 1을 다음 수로 가지는 원소는 $\mathbb{N}$에 존재하지 않는다.

4) $\mathbb{N}$의 임의의 두 원소 m, n에 대해 $m^{+} = n^{+}$이면, $m = n$이다. 즉 자연수의 임의의 두 원소가 같은 다음 수를 가진다면 "두 원소는 같다."

5) $\mathbb{N}$의 부분 집합 $\mathbf{S}$에 대해
    i) $1 \in{\mathbf{S}}$
   ii) 임의의 $n \in{\mathbf{S}}$일 때
    
    $n^{+} \in{\mathbf{S}}$라면, $\mathbb{N} \subset{\mathbf{S}}$이다.

Axiom, 공리란 "가장 기초적인 근거가 되는 명제이다." 즉, 증명할 필요가 없는 기초적인 성질이란 뜻이다.

우리는 가장 기초적인 "페아노 공리들"로 자연수를 정의했으니, "자연수 집합"임을 주장하는 수 많은 "집합들"중 어떤 것이 "유일하게 자연수 집합을 이루는지"를 위 공리들을 만족하는지 따져가며 찾을 수 있다.

5번 공리는 "수학적 귀납법"으로, 쉽게 말하자면 $\mathbb{N}$의 모든 원소(자연수)들은 "1"이라는 특별한 원소로부터 다음 수($1^{+}$), 그 다음 수($1^{+^{+}}$), 그 다음다음 수($1^{+^{+^{+}}}$), ... 이런 식으로 쭉 뻗어나가면서 구성되는 "최소한의 유일한 집합"을 결정하는 공리이다.

그리고 위에서 말했듯이 1, 2, 3, ...과 같은 자연수들은 "1, ($1^{+}$), ($1^{+^{+}}$), ($1^{+^{+^{+}}}$)"의 모델링된 객체일 뿐이다.그리고 앞으로 정수론을 공부하면서, 사용할 2가지 공리를 위의 "페아노 공리계"를 통해 받아드릴 수 있다.

Well - Ordering - Axiom(정렬 공리)

---

공집합이 아닌 자연수 집합의 부분 집합은 가장 작은 원소(= 최소원)를 포함한다.

"Well - Ordering - Axiom"은 직관적으로, 자연수의 수직선을 생각했을 때 자연수의 각 부분 집합들은 항상 다른 원소들보다 가장 왼쪽에 있는 원소를 포함하고 있다는 것이라고 볼 수 있다.

하지만 "정수 전체 집합"과 "양의 유리수의 집합"에서는 성립하지 않는다. 왜냐하면

1. [inf, 0)의 경우 최소원이 정의되지 않는다.
2. 임의의 양의 유리수 "r"에 대해, 항상 더 작은 양의 유리수 원소가 존재하기 때문이다.

Mathematical Induction(수학적 귀납법)

---

자연수의 부분 집합 $\mathbf{S}$가

    1) $1 \in{\mathbf{S}}$
    2) $n \in{\mathbf{S}} \rightarrow n + 1 \in{\mathbf{S}}$

를 만족한다면, $\mathbb{N} = {\mathbf{S}}$도 만족해야만 한다.

2. Division Algorithm

---

초등학생때 우리는 다음과 같은 나눗셈을 배운다.

악필이라 죄송합니다..

이런 나눗셈의 과정은 "Remainder(나머지)"가 "Divisor(나누는 수, 제수)"보다 작아질 때 멈춘다.

검산 과정에 모든 핵심을 포함하고 있으며, 요약하자면 나눗셈은 다음과 같은 관계식을 만족한다는 점이다.

Dividend(나눠지는 수, 피제수) = Quotient(몫) * Divisor + Remainder

Theorem 1.1 - "The Division Algorithm"

---

a, b가 정수이고, b > 0 이라 하자. 이 때

$a = qb + r$을 만족하는 "유일한 정수 $q, r$"이 존재한다. (단 $0 \le r < b$)

1. 이 때 Dividend, a는 음수인 경우에도 만족한다.
2. 단순하게 Remainder가 Divisor보다 작다는 사실이 "q와 r의 유일성을 보장하지 않는다."
3. Division Algorithm은 "몫과 나머지"를 우리가 자연스럽게 구할 수 있게 해준다.

3. Divison Algorithm의 증명

---

증명은 두 가지로 나눠서 할 것이다.

1) "존재성에 대한 증명"

1. $a, b$가 어떤 고정된 정수이고 $b > 0$이라고 하자.
2. 이 때, $\mathbf{S}$ = {$a - bx | a - bx \ge{0}, x \in{\mathbb{Z}}$} 에 대해 고려할 것이며, 이것이 "공집합이 아니다."라는 것을 보일 것이다.
3. 먼저 $a - bx$ 형태의 정수가 양수임을 보일 것이며, 이는 두 가지 가능성이 존재한다.
   • $a \ge{0}$(= a가 0을 포함한 자연수 집합의 임의의 원소일 때)
     • $a - b \bullet 0 = a \ge{0}$이므로, x = 0일 때, $a - bx$는 음이 아닌 정수를 가지게 된다.
     • 즉, x가 0일 때, $a \ge{0}$이므로 $\mathbf{S}$는 항상 "양수"만을 가지게 된다.
   • $a < 0$(= a가 음수인 경우)
     • $-a > 0$으로 부터, $b \ge{1}$임을 알 수 있다.
     • $b > 0$이고 $a < 0$일 때, $-bx \ge{a}$이어야 한다. 따라서 x = a이다.
4. 그러므로, 집합 $\mathbf{S}$ = {$a - bx | a - bx \ge{0}, x \in{\mathbb{Z}}$}는 최소한 "공집합은 아니며, 원소가 존재한다."
5. "Well - Ordering - Axiom"에 의해서, 집합 $\mathbf{S}$는 최소원을 포함한다. 이를 "r"이라고 하자.
6. $r \in{\mathbf{S}}$에 의해서, $a - bx$에 의해 최소원을 만들어내는 "적당한 정수, q"가 존재 할 것이다.
7. 따라서, $r = a - bq$ 또는 동등하게 $a = bq + r$이 되는 q와 r을 구했다.
8. $r \in{\mathbf{S}}$으로부터 $r \ge 0$임을 알 수 있고, 이제 $r < b$임을 증명하겠다.
9. 반대로, $r \ge{b}$라고 가정하자.(= 귀류법)
10. 그러면, $0 \le{r - b} = (a - bq) - b = a - b(q + 1)$으로부터, $a - b(q + 1)$은 양수임을 알 수 있고, 이는 정의에 의해$\mathbf{S}$의 원소이다.
11. 하지만, (1)에서 $b$는 양수로 정의하였다.
12. 따라서, $r - b < r$임은 자명하며, 따라서 $a - b(q + 1) = r - b < r$이다.
13. (12)의 마지막 부등식은 S의 원소인 "$a - b(q + 1) = r - b < r$"가 $r$보다 작다는 것을 의미한다.
14. 하지만, (5)에서 "$r$은 S의 최소원이다."라고 정의했다.
15. 이는 명백히 모순이고, 따라서 $r <  b$이어야만 한다.
16. 그런이유로, $a = bq + r$ 이고 $0 \le{r} < b$이 되도록 q와 r을 구했다.

2) "유일성에 대한 증명"

1. 임의의 정수 $q_1$ 그리고 $r_1$에 대해, $a = bq_1 + r_1$이고 $0 \le r_1 < b$라고 가정하자.
2. 이 때, $q = q_1$ 그리고 $r = r_1$을 $r \ge r_1$ 혹은 $r_1 \ge r$둘 중 하나를 통해 유일성을 증명 할 것이다.
3. 식을 아래와 같이 설정하고 빼고 정리하면 다음과 같다.
4. 마지막 식에서, "$r - r_1$이 b의 배수임을 알 수 있다.
5. 하지만 $b > 0$ 이고, $r \ge r_1$으로 부터 $r - r_1 \ge 0$임을 알 수 있다.
6. 그래서 $q - q_1$은 반드시 음이 아닌 정수가 되어야 한다.
7. 그러므로, $r - r_1$은 $0b, 1b, 2b, 3b, \cdots$의 b의 배수 형태이고, $0 \le r_1 \le r \le b$이다. 따라서 $r - r_1$은 $b$보다 엄밀하게 작다.
8. 유일하게 가능한 경우는, $r - r_1 = 0b = 0$이다.
9. 그러므로, $r = r_1$이다.
10. 마지막으로, $b(q_1 - q) = r - r_1 = 0$이고 $b >0$이므로, $q_1 - q = 0$이니 $q_1 = q$이다.