[Number Theory] 2. Divisibility(나누어 떨어짐)

0. Introduction

---

"나눗셈"에서 중요한 일은, Remainder(나머지)가 0일 때 주로 일어난다. Divisor(나누는 수, 제수)가 Dividend(나눠지는 수, 피제수)의 약수 일 때, Remainder는 0이 된다.

"나누어 떨어진다."라는 개념은 뒤에서 나올 "소수" 그리고 "합동식"의 중요한 개념이 된다.

따라서

1. "나누어 떨어짐."의 정의
2. 공약수와 최대공약수의 정의 및 성질
3. 베주 항등식
4. 베주 항등식의 증명
5. 유클리드 알고리즘
6. 유클리드 알고리즘의 증명

순으로 포스팅 하려 한다.

1. Divisibility 나누어 떨어짐.

---

Def. Divisibility

---

a와 b가 정수이고, b $\ne$ 0이라 하자.

만약 "a = bc"를 만족하는 임의의 정수가 존재할 때, "b가 a를 나누어 떨어트린다."라고 한다.
기호로는 

b $\mid$ a (b가 a를 나누어 떨어트린다.)

b $\nmid$ a (b가 a를 나누어 떨어트리지 않는다.)

로 표기한다.

-1을 곱함으로 음수의 경우로 확장 할 수 있다.

1. 만약, b가 a를 나눈다면 임의의 정수 c에 대해 "a = bc"가 성립한다.
2. 그런 이유로, (-a) = b(-c)"이므로 "$b \mid a"이다.

2. Common Divisor, GCD(Greatest Common Divisor)의 정의 및 성질

---

두 정수 "12"와 "30" 그리고 임의의 두 정수 a, b를 생각해보자.

"$a \mid 12$" 그리고 "$b \mid 30$"을 만족하는 a와 b는 아래와 같다.

$a = \pm \{1, 2, 3, 4, 6, 12\}$

$b = \pm \{1, 2, 3, 5, 6, 10, 15, 30\}$

a와 b에 공통으로 있는 원소 중 가장 큰 정수는 "6"이다. 6은 "12"와 "30"두 수를 나누는 가장 큰 정수가 된다.

이처럼 Common Divisor는 두 정수를 나누는 "가장 큰 공통된 Divisor"이다.

def. GCD(Greatest Common Divisor)

---

a와 b가 임의의 정수이고, 둘 다 0이 아니라고 하자.
이 때 a와 b를 둘 다 나누어 떨어지게 하는 "가장 큰 Divisor 'd'를 Greatest Common Divisor"라고 하며

"d가 a 와 b의 GCD이다." 라는 것은 

    1) $d \mid a$ 이고 $d \mid b$이다.
    2) $c \mid a$ 이고 $c \mid b$이면, $c \le d$이다.

a와 b의 GCD는, (a, b)로 표기한다.

a와 b가 둘 다 0이 아니라면, GCD가 유일하게 존재한다는 것을 보장한다.

그리고 (a, b)는 $gcd(a, b) \ge 1$을 만족한다.

3. Bezouts Identity(베주 항등식)

---

Bezouts Identity(베주 항등식)은 "두 정수와 gcd 사이에 관계를 나타내는 항등식이다."

Theorem 1.3 - "Bezouts Identity"

---

a와 b가 둘 다 0이 아닌 정수이고, d가 a와 b의 gcd라고 하자. 이 때

$d = au + bv$를 만족하는, 정수 u와 v가 존재한다. (u, v는 유일하지 않다.)

4. Proof of Bezouts Identity

---

증명은 먼저, S의 정의에 의해 양수가 반드시 존재함을 보여, Positive Smallest Element의 존재성을 보인 후 그것이 Common Divisor임을 보인 후 최종적으로 그것이 gcd임을 보일 것이다.

1. $\mathbf{S}$가 $a$와 $b$의 모든 선형 조합의 집합이라 하자 즉, $\mathbf{S} = \{am + bn | m, n \in{\mathbf{Z}}\}$
2. 먼저 주의할 점은, $a^2 + b^2 = aa + bb$는 $\mathbf{S}$의 원소이다. (이 경우, $m = a, b = n$)
3. 그리고 $a^2 + b^2 \ge 0$이다.
4. $a, b$가 둘 다 0이 아닌 것으로부터 $a^2 + b^2$은 반드시 양의 정수가 되어야한다.
5. 그러므로, $\mathbf{S}$는 양의 정수를 포함하고 있고, 그런 이유로 "Well - Ordering - Axiom"에 의해 최소원을 포함하고 있다.
6. $t$를 $\mathbf{S}$의 최소원이라고 하자.
7. $\mathbf{S}$의 정의에 의해, 임의의 정수 u, v에 대해 $t = au + bv$가 성립한다.
8. $t$가 $a$와 $b$의 gcd라고 가정하자, 즉 $t = d$임을 증명할 것이다.
9. "Division Algorithm"에 의해, t|a가 성립함을 보일 것이다.
10. 정수 $q, r$에 대해 다음 식을 생각하자. $a = bq + r, (단 0 \le r < q)$
11. 식을 정리하면 아래와 같다.

12. 

13. 따라서, $r$은 $a$ 와 $b$의 Linear Combination이고 $r \in \mathbf{S}$이다. ($\mathbf{S}의 정의가 $a$와 $b$의 Linear Combination이니)
14. "Division Algorithm"에 의해 $r < t$이라 했으나,
    i) "$0 \le r$" 그리고
    ii) "$t$가 최소원" 이라 했으니,
    $r = 0$일수밖에 없다.
15. 그러므로, $a = tq + r = tq + 0 = tq$이고 $t \mid q$이다.
16. $b$에 대해서도 (10) ~ (15)의 과정을 똑같이 적용할 수 있다.
17. 따라서, $t$는 $a$와 $b$의 Common Divisor이다.
18. 이제 $t$가 gcd임을 보일 것이다.
19. $c$를 $a$와 $b$의 아무런 Common Divisor라고 하자.
20. 그럼, $c \mid a$ 그리고 $c \mid b$가 성립한다.
21. 이 때, 임의의 정수 $r, s$에 대해 $a = cr$ 그리고 $b = cs$이다.
22. (21)의 식을 전개하면 아래와 같다.
23. $t = au + bv = cru + csv = c(ru + sv)$
24. (23)의 식의 첫 부분과 마지막 부분은 "$c \mid t$"를 의미하므로, $c \le |t|$이다.
25. 하지만, "t"는 양수이므로 $c \le t$이며, 이 말은, t가 gcd d라는 것과 같다. (t = d).

증명을 통해 우리는 다음과 같은 "따름 정리"를 얻을 수 있다.

Corollary 1.4

---

$a$와 $b$가 둘 다 0이 아닌 정수이고 $d$는 양의 정수라고 할 때
$d$가 $\gcd(a, b)$가 참일 때 다음 명제들도 참이다.(= iff)

    i) $d \mid a$ and $d \mid b$
    ii) $c \mid a$이고 $c \mid b$라면, $c \mid d$이다.

---

Proof


1. $d = \gcd(a, b)$라고 가정하자.
2. gcd의 성질에 의해, $d \ge 1$을 만족하게 된다.
3. "Theorem 1.3 - Bezouts Identity"의 증명 마지막 단락(23, 24, 25)에서 gcd "$d$"가 ii)의 조건을 만족함을 볼 수 있다.
4. 반대로, $d$가 i) 와 ii)를 만족하는 양의 정수라고 가정해보자.
5. i)에 의해 $d$는 $a, b$의 Common Divisor이다.
6. ii)에 의해 $c \mid d$일 때, $c$는 아무런 Common Divisor이다.
7. 그런 이유로, $c \le |d|$이지만 $d$는 양수이므로 $|d| = d$이다.
8. 따라서, $c \le d$이므로 $d$는 gcd이다.

즉, $c$가 $a, b$의 약수라면 "c는 gcd의 약수이기도 하다."라는 뜻이다.

5. Euclidean Algorithm(유클리드 알고리즘, 호제법)

---

"12"와 "30"의 gcd는 우리가 빠르게 구할 수 있다. 하지만 두 정수가 엄청 커진다면 그 거대한 두 정수의 gcd를 구하려면 매우 오랜 시간이 걸릴 것이다.

Euclidean Algorithm은 이런 거대한 두 정수의 gcd를 빠르게 구하는 방법론, 알고리즘이다.

Theorem 1.6 - "Euclidean Algorithm"

---

$a \ge b$관계가 성립하는 두 양의 정수 $a, b$에 대해, $b \mid a$라면, $b = \gcd(a, b)이고
$b \nmid a$라면, "Division Algorithm"을 반복해서 적용할 수 있다.

이 알고리즘은 Remainder = 0 일 때 끝나게 된다.

핵심은, "큰 수들의 gcd 구하기 문제를 작은 수들의 gcd문제로 치환 할 수 있다는 것이며, 마지막으로 0이 아닌 Remainder가 gcd가 된다."

6. Proof of Euclidean Algorithm

---

직접 증명을 하기 전에 한 보조 정리를 증명할 것이고, 이 보조 정리에 의해 "Euclidean Algorithm"은 즉각적으로 증명될 것이다.

Lemma 1.7

---

$a, b, q, r \in{\mathbb{Z}}$이고, $a = bq + r$일 때 $\gcd(a, b) = \gcd(b, r)$이다.

---

Proof

1. $c$가 $a$와 $b$의 Common Divisor일 때, 임의의 정수 $s, t$에 대해 $a = cs$와 $b = ct$가 성립한다.
2. 결과적으로,
        $r = a - bq = cs - ctq = c(s - tq)$
3. 따라서, $c \mid r$이고 그래서 $c$는 $b$와 $r$의 Common Divisor이다.
4. 반대로, $e$가 $b$와 $r$의 Common Divisor라고 가정하자.
5. 그러면, $b = ex$와 $r = ey$이고,
        $a = bq + r = exq + ey = e(xq + y)
4. 따라서, $e \mid a$이고 그래서 $e$는 $a$와 $b$의 Common Divisor이다.
5. 그러므로, 모든 $a, b$의 Common Divisor의 집합 $\mathbb{S}$는 "모든 $b, r$의 Common Divisor의 집합$\mathbb{T}$와 같다. (즉, $\mathbb{S} = \mathbb{T}$ )
6. 따라서, $\mathbb{S}$의 $\gcd(a, b)$와 $\mathbb{T}$의 $\gcd(b,r)$은 같다.

이제 본 증명을 해보자.

1. $b \mid a$라면, $a = bq + 0$이다.
2. 그럼, "Lemma 1.7"에 의해 $\gcd(a, b) = gcd(b, 0)$이다.
3. 만약, $b \nmid a$라면, "Lemma 1.7"을 반복해서 적용한다.