유클리드 호제법, 최대공약수(GCD), 최소공배수(LCM)

#1 유클리드 호제법

두 양의 정수 A, B (A > B) 에 대하여
A = B × Q + R   (0 ≤ R < B) 이라 하면,
A, B의 최대공약수는
B, R의 최대공약수와 같다.

최대공약수는 두 양의 정수의 공약수 중 가장 큰 양의 정수를 의미한다. 유클리드 호제법은 최대공약수를 구하는 알고리즘이다.

 

#1-1 증명 1: D | A고 D | B면 D | R이다.

배경지식: 수학에서 X가 Y로 나누어 떨어지면 이를, Y | X라 표현한다.

72 ÷ 27 = 2 나머지 18

 

약속

• 큰 수 (A): 72
• 작은 수 (B): 27
• 큰 수를 작은 수로 나눈 몫 (Q): 2
• 큰 수를 작은 수로 나눈 나머지 (R): 18
• 큰 수와 작은 수의 공약수 (D): ? (아직 값이 뭔지는 모름)

 

전개 1

• A = B × Q + R
• R = A - B × Q
• 양변에 (÷ D)를 취하면,
  → R ÷ D = (A ÷ D) - (B ÷ D × Q)

 

전개 2

• (A ÷ D)의 결과는 반드시 정수
• (B ÷ D × Q)의 결과도 반드시 정수
• 따라서 (A ÷ D) - (B ÷ D × Q)의 결과 또한 정수
• 그렇다면 R ÷ D 또한 정수라는 말
• 나눗셈의 결과가 정수 = 나누어 떨어진다!
  → D는 R의 약수

 

∴ D | A고 D | B면 D | R이다.

 

#1-2 증명 2: D' | B고 D' | R이면 D' | A이다.

72 ÷ 27 = 2 나머지 18

 

약속

• 큰 수 (A): 72
• 작은 수 (B): 27
• 큰 수를 작은 수로 나눈 몫 (Q): 2
• 큰 수를 작은 수로 나눈 나머지 (R): 18
• 작은 수와 나머지의 공약수 (D'): ? (아직 모름)

 

전개 1

• A = B × Q + R
• 양변에 (÷ D')를 취하면,
• → A ÷ D' = (B ÷ D' × Q) + (R ÷ D')

 

전개 2

• (B ÷ D')의 결과는 반드시 정수
• 따라서 (B ÷ D' × Q)의 결과도 반드시 정수
• (R ÷ D')의 결과도 반드시 정수
• 따라서 (B ÷ D' × Q) + (R ÷ D')의 결과 또한 정수
• 그렇다면 A ÷ D' 또한 정수라는 말
• 나눗셈의 결과가 정수 = 나누어 떨어진다!
  → D'는 A의 약수

 

∴ D' | B고 D' | R이면 D' | A이다.

 

#1-3 정리

이미 증명한 것

• A = B × Q + R 에서
  • A와 B의 모든 공약수 즉, 공약수 집합 D
    → 증명 1에 의해, 모든 D는 R의 약수이기도 하다.
  • B와 R의 모든 공약수 즉, 공약수 집합 D'
    → 증명 2에 의해, 모든 D'은 A의 약수이기도 하다.

 

전개

• D에 속하는 어떤 수 x는 (R의 약수일테니) 반드시 D'에 들어간다 (D ⊆ D').
• D'에 속하는 어떤 수 y는 (A의 약수일테니) 반드시 D에 들어간다 (D ⊇ D').
• (D ⊆ D') 이고 (D ⊇ D') 이므로, D와 D' 사이에 서로 다른 원소는 단 하나도 존재할 수 없다.
  → D = D'

 

∴ A, B의 최대공약수는 B, R의 최대공약수와 같다.

 

#2 최대공약수(GCD) 구하기

최대공약수를 구하는 함수 gcd(a, b)가 있다고 치자 (a에는 큰 수, b에는 작은 수 할당). b가 0일 때, 즉 gcd(a, 0)이면 최대공약수는 a다. 0은 (0을 제외한) 모든 수로 나눌 수 있기 때문에, a의 약수 중 제일 큰 수인 a가 최대공약수가 되는 것이다.

 

여기에 방금까지의 증명(#1)을 더해 코틀린 수식을 써보자면,

// Greatest Common Divisor (최대공약수)
fun gcd(a: Int, b: Int): Int {
    return if (b == 0) {
        a
    } else {
        gcd(b, a % b) // %는 나눗셈 결과의 '나머지'를 반환하는 연산자
    }
}

뭔가 이상한 점이 있다. 바로, a ≥ b임을 판단하지 않는다는 것이다. 왜 그럴까? a < b라면 a % b = a이므로, 첫 재귀 호출에서 gcd(b, a)가 되어 두 수의 위치가 자동으로 뒤집히기 때문이다.

 

#3 최대공배수(LCM) 구하기

배경지식: 공통된 약수가 오직 1밖에 없는(= 최대공약수가 1) 두 정수의 관계를 서로소라 한다.

 

약속

• 두 양의 정수 A와 B의 최대공약수를 G라 하자.
  • A = G × a
  • B = G × b
• a와 b의 최대공약수를 d라 하자.
  • A = G × d × α
  • B = G × d × β
• A와 B의 공배수를 M이라 하자.
  • M = G × a × m

 

전개 1

• (G × d)는 A와 B의 공약수
• d는 최대공약수이므로 반드시 양의 정수임 (#1에 있는 최대공약수의 정의 참조)
• d가 1이 아니면 A와 B의 최대공약수가 G가 아니게되므로 (모순), d는 반드시 1
  → a와 b는 서로소

 

전개 2

• M = G × a × m의 양변에 (÷ B)를 취하면,
  M ÷ B = (G × a × m) ÷ B
  = (G × a × m) ÷ (G × b)
  = (a × m) ÷ b
• (M ÷ B)는 정수
  → 즉, (a × m) ÷ b의 결과가 정수
• a와 b는 서로소이므로, m은 반드시 b의 배수(b, 2b, 3b, ...)여야만 함. 그래야 (a × m) ÷ b의 결과가 정수가 되기 때문.
  → M = G × a × m = G × a × b × n (n은 1, 2, 3, ...)

∴ A와 B의 모든 공배수 M의 최솟값 즉, 최소공배수는 G × a × b = A × B ÷ G

 

최소공배수를 구하는 코틀린 수식을 써보자면,

// Least Common Multiple (최소공배수)
fun lcm(a: Int, b: Int): Int {
    return a / gcd(a, b) * b
}

왜 A × B ÷ G 순이 아니라, A ÷ G × B 로 썼을까? 바로 오버플로우 방지 때문이다. Int × Int가 Int의 범위를 벗어날 수도 있으니, 나눗셈을 먼저해서 Int의 범위를 벗어날 확률을 줄인 것이다.