[Number Theory] GCD, 유클리드 호제법

모든 문자는 정수입니다.

 

Common Divisor

c is common divisor of a and b $\equiv c | a \land c | b$

 

GCD, Greatest Common Divisor

$\gcd(a,b) \\ = \max(\{c\; |\; c|a \} \bigcap \{c\; |\; c|b \}) \\ = \max \{ c\; |\; c|a \land c|b \}$

 

Common Multiple

c is common multiple of a and b $\equiv a | c \;\land\; b | c$

 

LCM, Least Common Multiple

$\operatorname{lcm}(a, b) = \min\{ c \;|\; \forall a, b \in \mathbb{Z}, \; c | a \;\land\; c | b\}$

 

Relatively Prime

c is relatively prime for a and b $\equiv \gcd(a, b) = 1$

 

Tautoloagy

∀ a, b ∈ ℤ 에 대해 다음이 성립한다.

1. gcd(a, b) ≥ 1 ∵ 1 | a ∧ 1 | b ⇒ 1 ∈ { c | ∀ a, b ∈ ℤ, c | a ∧ c | b }, ∴ gcd(a, b) ≥ 1
2. gcd(a, b) = gcd(|a|, |b|) ∵ gcd(a, b) = max{ c | c|a ∧ c|b } ⇒ max { c | c|(a-2a) ∧ c|(b-2b) }, ∴ gcd(a, b) = gcd(|a|, |b|)
3. gcd(a, 0) = |a| ∵ 0의 약수는 모든 정수이고, a의 약수 중 가장 큰 수는 -a 혹은 a. 따라서 |a|가 가장 큰 약수임.

 

Division Algorithm

임의의 양의 정수 a, b에 대해

$$ b = qa + r, \quad (0 ≤ r < a) $$

를 만족시키는 정수 q, r 이 유일하게 존재한다. 먼저 존재성을 증명하자.

𝑝𝑓) 𝑒𝑛𝑜𝑢𝑔ℎ 𝑡𝑜 𝑠ℎ𝑜𝑤 "∃ r = (b - qa) ∈ ℤ, b - qa ∈ [0, a)".
b - qa ∈ [ 0, a ) ⇔ b ∈ [ aq, a(q+1) )
인 p가 존재하기만 하면 된다. ∀ i ∈ ℤ 에 대해서 첨수 집합 $A_{i} = [ai, a(i+1))$ 이라고 두면, $\bigcup_{i=1}^{n} A_{i} ≡ ℤ $ 이며, $A_{i}$와 $A_{j}$는 disjoint 하기 때문에 첨수집합족 $ \mathcal{F} = \{A_{i} \;|\; A_{i} = [ai, a(i+1)) \}$ 로 두면, 이때 b ∈ ℤ 이므로, 어떤 첨수 i 에 대해 $b ∈ A_{i}$ 이다.

유일성을 증명하자.

𝑝𝑓) 𝑒𝑛𝑜𝑢𝑔ℎ 𝑡𝑜 𝑠ℎ𝑜𝑤 ∀ i, j(≠ i) ∈ ℤ 에 대해 A_i ∩ A_j = ∅
A_i ≡ [ai, a(i+1)), A_j = [aj, a(j+1)) 임을 안다.
i) i < j 인 경우, i < j ⇒ i < i+1 ≤ j ⇒ a(i+1) ≤ aj 이므로 sup A_i ≤ inf A_j 이므로 A_i ∩ A_j = ∅ 이다.
ii) 𝑤𝑖𝑡ℎ𝑜𝑢𝑡 𝑙𝑜𝑠𝑠 𝑜𝑓 𝑔𝑒𝑛𝑒𝑟𝑎𝑙𝑖𝑡𝑦, i와 j를 바꾸면 끝
따라서 $\bigcup \mathcal{F} = \mathbb{Z}$ 이므로(분할 이므로) 어떤 첨수 i에 대해 b ∈ A_i인 i가 유일하다.

∴ ∃! q, r ∈ ℤ, b = qa + r,    (0 ≤ r < a)

 

Tautoloagy

∀ m, n ∈ ℤ 에 대해서 다음이 성립한다.

1. d = gcd(m, n) ⇒ gcd(m/d, n/d) = 1 ∵ m = d×k, n = d×r 이므로 m/d = k, n/d = r 이다. 만약 k와 r의 공약수가 1보다 크다면 d의 최대공약수가 d라는 것에 모순이다. 따라서, k와 r의 공약수는 1뿐이게 된다.
2. ∀ k ∈ ℤ, gcd(m, n) = gcd(m+kn, n) ∵ gcd(m, n) = t로 두자(유일하게 존재하기 때문). t = max { c  |  c | m ∧ c | n } ⇒ t = max { c  |  c | m + kn ∧ c | n } ( ∵ 전 장의 tautology에 의해 ) ⇒ t = gcd(m+kn, n). 역으로 t = gcd(m+kn, n) ⇒ t = max { c | c | m+kn ∧ c | n } ⇒ t = max { c | c | m+(k-1)n ∧ c | n } ( ∵ 전 장의 tautology에 의해 ) ⇒ ... ⇒ t = max { c | c | m ∧ c | n} 이다. ■
3. ∃ a, b ∈ ℤ, gcd(m, n) = am + bn
   ∵ Let, S = {ax + by | x, y ∈ ℤ ∧ ax+by > 0} (⊂ ℕ) ≠ ∅
   Take c = 𝑚𝑖𝑛 S, by division thm., ∃! q, r ∈ ℤ, a = qc + r ( 0 ≤ r < c)
   a - qc = a - q(ax + by) = a(1-qx) + b(qy) = r.
   If r > 0, r ∈ S ≡ c (ontradiction, about c = the least elem. of S). ∴ r = 0 ∧ c | a.
   𝑤𝑖𝑡ℎ𝑜𝑢𝑡 𝑙𝑜𝑠𝑠 𝑜𝑓 𝑔𝑒𝑛𝑒𝑟𝑎𝑙𝑖𝑡𝑦, the same logic applies to b.
   ∴ d | gcd(a, b) ■
4. ∃ x, y ∈ ℤ, gcd(m, n) = 1 ⇔ ax + by = 1 ∵ 3번에 의해 gcd(m, n) = 1 = xm + yn 을 만족시키는 x, y가 존재한다.

 

Euclidean Algorithm

유클리드 호제법이라고 불리며, 두 양의 정수 a, b 에 대해
$$ gcd(a, b) = gcd(a - bq, b) = gcd(a - bq, b - q_{2}(a - bq_{1}) = ... = d $$ 이다.

위의 tautology만 보면 쉽게 보일 수 있다.