도입 GCD, Great Common Divisor는 최대공약수로 두 수가 가지는 공통 약수; 공약수 중에 가장 큰 수를 의미한다고 흔히 알려져 있으며 현재까지 그렇게 배워왔을 것이다. → 과연 실제 정의도 이와 동일할까? 1. GCD : Great Common Divisor 1.1. Definition of GCD $$\gcd(a,b) = d$$ Definition 1. for integers $a$ and $b$ unique integer $d$ s.t., $d|a$, and $d|b$ for all possible $c$, $c|a$ and $c|b$ implies $c|d$. 즉, $\gcd(a,b)=d$는 $a$와 $b$의 공약수이며, $a,b$의 공약수인 모든 $c$에 대해 $c$는 $d$의 ..