유클리드호제법 - 최소공배수(lcm), 최대공약수(gcd) 구하기

유클리드 호제법

두 정수 a, b의 최대공약수를 G(a, b)라고 하자.
정수 a, b, q, r (b ≠ 0)에 대하여 a = bq + r,이면 G(a, b) = G(b, r)가 성립한다.

 

〈증명〉
G(a, b) = g라고 하자. 최대공약수의 성질에 의해 a = a′g, b = b′g이고 G(a′, b′) = 1이다.
a = bq + r로부터 r = a - bq = g(a′ - b′q) 이고, g는 r의 약수이다.
G(b, r) = g임을 보이기 위해서는 G(b′, a′ - b′q) = 1임을 보이면 된다.

귀류법을 적용하여 결론을 부정해보자.
어떤 정수 d가 존재하여 G(b′, a′ - b′q) =d(≠ 1)라고 하면, b′ = dm, a′ - b′q = dn라고 할 수 있고, a′ = b′q + dn = dmq + dn = d(mq + n) 이므로 G(a′, b′) = 1라는 가정에 모순이다. 따라서 G(b′, a′ - b′q) = 1이므로 G(b, r) = g가 성립한다.

[네이버 지식백과] 유클리드 호제법 (통합논술 개념어 사전, 2007. 12. 15., 한림학사)

---

 1) 최대공약수

def gcd(a, b):
    while (b>0):
        a, b = b, a % b
    return a

print(gcd(64, 80))

 

math모듈을 사용해서 다음과 같이 더 간단히 작성할 수 있다.

import math
n = math.gcd(64, 80)
print(n)

 

 

2)최소공배수

a = 3
b = 7

def gcd(a, b):
    while (b>0):
        a, b = b, a % b
    return a

result = (a * b) // gcd(a, b)
print(result)

 

math모듈 사용해서 구하기

import math
n = math.gcd(3, 7)
print(3*7 // n)

 

+ lcm 사용하면 더 간단하게 구할 수 있다.

import math
print(math.lcm(3, 7))