유클리드 호제법 GCD 알고리즘 친절한 증명

유클리드의 사기성

유클리드는 롤로 치면 잭스같은 캐릭터입니다.
잭스는 롤 초창기에 만들어진 원년멤버이면서 스킬셋도 지금까지 안바뀌고 유지되고 있습니다.
그럼에도 불구하고 웬만한 OP챔피언들은 다 씹어먹으며, 탑의 국밥으로 군림하고 있습니다.

유클리드가 그렇습니다.
무려 기원전 4세기의 사람이 만든 알고리즘이 지금까지도 가장 효율적인 알고리즘입니다.

GCD 알고리즘이란

GCD 알고리즘은 최대 공약수를 구하는 알고리즘입니다.

$GCD(a,b)$를 a와 b의 최대 공약수라고 하겠습니다.
이때, $GCD(a,b)=GCD(b,a\bmod b)$가 성립합니다.
여기서 $a\bmod b$는 a를 b로 나눈 나머지를 뜻한다.
또한 $b=0$에서 $GCD(a,b)=a$입니다.

이를 응용하면 이렇게 됩니다.

$GCD(391,85)$
$=GCD(85,51)$
$=GCD(51,34)$
$=GCD(34,17)$
$=GCD(17,0)$
$=17$

391과 85라는 계산하기에 너무 더러운 숫자도 손쉽게 최대공약수를 구할 수 있게 되는것입니다!!

GCD 증명

GCD알고리즘의 사기성을 알았으니 증명을 한번 해봅시다.

GCD알고리즘에 따르면 $a$와 $b$의 최대공약수는 $a\bmod b$와 $b$의 최대 공약수와 같습니다.

이때 $a\bmod b=r$이라고 한다면,
$a=b\times q+r$이 성립합니다. ($q$는 $a$를 $b$로 나눈 몫)

즉, 우리는 ($a$와 $b$의 최대공약수)가 ($b$와 $r$의 최대공약수)와 같음을 증명해야 합니다.

$k$를 ($a$와 $b$의 최대공약수)라고 하겠습니다.
$a=kn'$
$b=kn''$
($n'$과$n''$은 서로소)

$r=a-bq$
$=kn'-kn''q$
$=k(n'-n''q)$

$b$와 $r$의 최대공약수가 $k$이기 위해서는, $n''$과 $(n'-n''q)$가 서로소여야 합니다.

이를 증명하기 위해서 역으로 $n''$과 $(n'-n''q)$가 서로소가 아니라고 가정해 봅시다.
만약 위의 가정에서 모순이 도출된다면, $n''$과 $(n'-n''q)$는 서로소인 것이 증명됩니다.

$n''$과 $(n'-n''q)$의 최대공약수를 $m$이라 하겠습니다.
$n''=mt'$
$n'-n''q=mt''$ ($t'$과 $t''$은 서로소)

$n'-mt'q=mt''$ ($\because n''=mt'$)
$n'=mt''+mt'q$

$n''=mt'$
$n'=mt''+mt'q$
위의 두 식에서 $n'$과 $n''$이 공통 인수 $m$을 가진다.
그런데 $n'$과 $n''$은 서로소이므로 논리적 모순이 발생한다.

그러므로, $n''$와 $(n'-n''q)$는 서로소다.
그러므로, ($a$와 $b$의 최대공약수)와 ($b$와 $r$의 최대공약수)는 같다.
그러므로, $GCD(a,b)=GCD(b,a\bmod b)$가 성립한다.