유클리드 호제법

Euclidean Algorithm

개요

유클리드 호제법은 두 정수의 최대공약수를 빠르게 구하는 방법입니다.

자연수 에 대해 를 로 나눈 나머지를 이라 하면 의 최대공약수가 의 최대공약수와 같다는 뜻입니다.
만약 이라면 가 최대공약수가 됩니다.

증명

알고리즘

를 다르게 쓰면 입니다. 여기서 는 몫입니다. 이라 합시다. 적당한 서로소인 정수 에 대해 입니다. 이를 에 대입하면 이므로 가 의 약수임을 알 수 있습니다.

라고 합시다. 그러면 적당한 서로소인 두 정수 에 대해 입니다. 이를 에 대입하면 입니다. 따라서 은 의 약수입니다. 그런데 에서 이고 은 의 약수입니다. 따라서 은 의 공약수이고 는 서로소이므로 입니다.

시간 복잡도

나머지의 정의에 의해 입니다. 따라서 이고 은 의 절반보다 항상 작습니다. 따라서 시간 복잡도는 입니다.

구현

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

최대공배수

최대공약수를 알면 최소공배수도 알 수 있습니다. 이기 때문입니다.

증명 1

로 나타낼 수 있습니다. 는 를 소인수 분해 했을 때 의 지수입니다.
같은 방식으로 입니다.
그렇다면 입니다.
같은 방식으로 입니다.
이때 임을 알 수 있습니다.
이는 와 같습니다.

증명 2

이라 합시다. 적당한 서로소인 정수 에 대해 입니다. 여기에 를 대입하면 입니다. 양변에 를 나누면 입니다. 와 는 각각 서로소이므로 입니다.

문제

• 2609번: 최대공약수와 최소공배수 풀이