이전의 유클리드 호제법으로 최대공약수를 구하는법을 알았다 유클리드 호제법 이론 (최대 공약수 구하기) 즉, a, b의 최대공약수와 b, r의 최대공약수가 같음을 이용해서 최대공약수를 빠르게 구하는 방법이다. 예를들어 78696과 19323의 최대 공약수를 구하고자 한다면 78696 = 19323 * 4 + 1368 19323 = 1368 * 14 +.. fullfish.tistory.com 더 나아가서 이를 이용해서 a, b의 최대공약수와 함께 이 최대공약수가 되기위해서 a에 몇을 곱하고 b에 몇을 곱해야하는지 구해보자 gcd(a,b) = a * x + b * y 이러한 형식으로 표현되는데 x와 y를 구하는것이다 이전의 78696과 19332의 경우로 확장된 유클리드 호제법을 사용해 보겠다 78696 =..
