유클리드 호제법

$0$이 아닌 두 정수 $a, b$가 $a=bq+c$가 성립한다고 하자.($q, c$는 정수)
$a, b$의 공약수 전체집합과 $b,c$의 공약수 전체 집합은 서로 같다.
특히 $(a, b)=(b,c)$이다.

GCD

유클리드 호제법을 영어로 Euclidean Algorithm이라 한다. 이를 이용하여 최대공약수(이하 $gcd$)를 빠르게 구할 수 있다.

코드

if $b | a$, then $gcd(a, b) = b$
otherwise, $gcd(a, b) = gcd(b, a \mod b)$

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

시간복잡도

좀 수학적인 지식이 필요하다.
우선 $(a_i, b_i)$를 $i$번째 단계에서의 $(a, b)$라 하자.
그러면 $b_1 = 0$이고, 두번째 단계부터는 $b \geq 1$이다.
또한 $(a_{k+1}, b_{k+1})$ -> $(a_{k}, b_{k})$ -> $(a_{k-1}, b_{k-1})$이 되고, 따라서
$a_k=b_{k+1}$, $a_{k-1}=b_k$, $b_{k-1}=a_k \mod b_k$
$q \geq 1$에 대하여 $a_k=qb_k+b_{k-1}$이므로
$b_{k+1} \geq b_k + b_{k-1}$
한편 피보나치 수열 $f_n$에 대하여 $f_n \approx \frac{1}{\sqrt{5}}\big( \frac{1+\sqrt{5}}{2}\big)^n$이므로
시간복잡도는 $O(\log{(a+b)})$이다.

LCM

$lcm(a, b) = \frac{|ab|}{gcd(a, b)}$임을 이용한다. (단, $a, b$는 $0$이 아닌 정수)
시간복잡도는 $gcd(a, b)$를 구하는 시간인 $O(\log{(a+b)})$이다.

또한 $lcm(a_1, a_2, ..., a_n)=lcm(a_1, lcm(a_2, a_3, ..., a_n))$이다.

❌ $gcd$는 같은 성질이 적용되지 않는다.