유클리드 알고리즘이라고도 하는 유클리드 호제법은 너무 큰 두 수의 최대 공약수를 구하기 위한 알고리즘입니다. 유클리드 호제법이 뭔지부터 알아보자면 두수 a,b가 있고 a% b 값을 r이라 할 때 gcd(a, b)는 gcd(b, r)과 같아서 점차 숫자의 크기를 줄여가며 최대공약수를 쉽게 구할 수 있게 해주는 방식입니다. 그럼 저희가 증명해야할 것이 바로 눈에 들어옵니다. 바로 gcd(a,b) = gcd(b, r)이라는 것이죠. 단계적으로 증명해 나가보죠. 먼저 a, b는 정수이고 a >= b라 가정합니다. gcd(a, b)나 gcd(b, a)나 같으므로 일반성에 영향을 끼치지 않는 조건이죠. 그러면 a = bq + r을 만족하는 유일한 정수 q, r이 존재합니다. 이때 0
