최소 공배수(최대 공약수) 찾기 - 유클리드 호제법 (나머지 정리)

결론 먼저

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

def lcm(a, b):
    return a * b // gcd(a, b)

test_number = int(input())
for _ in range(test_number):
    number_1, number_2 = map(int, input().split())
    print(lcm(number_1, number_2))

 

원리

유클리드 호제법 

a > b 일 때, a % b = r 이면 

a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다

 

 

나머지 정리

a % b = r 이면, 

a = bq + r (q는 임의의 몫)

만약 d가 a와 b의 공약수 라면, d는 r도 나눌 수 있다

좌변

a % d = 0

우변

bq % d = ((b % d ) * (q % d )) % d = 0 (나머지 정리 )

따라서 0 = 0 + r % d  이므로  r % d = 0