유클리드 호제법 사용하기
유클리드 호제법을 이해하기 위해서는 MOD연산에 대해 알고 있어야 한다.MOD연산이란? 두 값을 나눈 나머지를 구하는 연산!
먼저, 큰 수를 작은 수로 나눈 나머지를 구한다. 즉, MOD 연산을 한다.
1112 mod 695 = 417
Plain Text
복사
그 다음, 나눴던 수와 나머지로 또 MOD 연산을 한다.
695 mod 417 = 278
Plain Text
복사
이 과정을 계속 반복한다.
417 mod 278 = 139
278 mod 139 = 0
Plain Text
복사
나머지가 0이 됐을 때, 마지막 계산에서 나누는 수로 사용된 139가 1112와 695의 최대공약수가 된다.
간단하게 말하면, 유클리드 호제법은 MOD연산을 반복하면 된다!
