Euclidean Algorithm
개요
유클리드 호제법은 두 정수의 최대공약수를 빠르게 구하는 방법입니다.
두 정수 의 최대공약수를 라 합시다. 인 경우 입니다.
를 로 나눈 나머지를 이라 할 때, 이 성립합니다.
따라서 같은 방법으로 를 로 나눈 나머지를 이라 하면 이므로 나머지가 이 될 때 까지 계속 나머지를 취하는 방법으로 를 구할 수 있습니다.
def gcd(a: int, b: int) -> int:
while b > 0:
a, b = b, a % b
return a
시간 복잡도는 입니다.
증명
알고리즘
라 하고 이라 합시다.
, , 으로 쓸 수 있습니다.
를 로 나눈 몫을 라 하면 입니다. 따라서 이므로 는 의 약수이고 와 의 공약수가 됩니다.
가 최대공약수이므로 으로 둡시다. (은 자연수)
이므로 는 의 약수이고 와 의 공약수가 됩니다.
이 최대공약수이므로 로 둡시다. (는 자연수)
에 를 대입하면 입니다. 이를 만족하는 자연수 , 는 , 인 경우만 존재합니다. 따라서 입니다.
시간 복잡도
라 합시다.
나머지의 정의에 의해 입니다. 따라서 이고 이므로 입니다.
유클리드 호제법을 한번 더 적용해서 를 로 나눈 나머지를 이라 하면 임을 알 수 있습니다.
많아야 두 번 호제법을 사용하면 두 번째 인자가 절반으로 줄어드므로 시간 복잡도는 입니다.
최소공배수
최대공약수를 알면 최소공배수도 알 수 있습니다. 이기 때문입니다.
증명 1
로 나타낼 수 있습니다. 는 를 소인수 분해 했을 때 의 지수입니다.
같은 방식으로 입니다.
그렇다면 입니다.
같은 방식으로 입니다.
이때 임을 알 수 있습니다.
이는 와 같습니다.
증명 2
이라 합시다.
적당한 서로소인 정수 에 대해 입니다.
여기에 를 대입하면 입니다.
양변에 를 나누면 입니다.
와 는 각각 서로소이므로 입니다.
따라서
문제
