최대 공약수만약 12, 18의 최대 공약수를 찾고자 한다면, 간단하게 두 수의 약수를 모두 나열한다.12:1, 2, 3, 4, 6 ,1218:1, 2, 3, 6 ,9 ,1812와 18의 공약수중 가장 큰 수인 6이 최대 공약수가 된다.다만 이 방법으로 큰 수들의 최대공약수를 찾으려면 매우 오랜 시간이 걸릴 것이다.따라서 유클리드 호제법으로 해결하면 된다.유클리드 호제법두 양의 정수 a,b (a>b)에 대하여 a=bq+r(0≤r이라 하면, a,b의 최대공약수는 b,r의 최대공약수와 같다.gcd⁡(𝑎, 𝑏)=gcd⁡(𝑏, 𝑟) 즉, 𝑟=0이라면, 𝑎,𝑏의 최대공약수는 b가 된다. 위의 정리를 활용하면 최대 공약수를 간단하게 구할 수 있다.한마디로 r이 0이 될 때까지 계속해서 a에 b값을 다시 ..