나머지로 바꾸는 이유
a=bq+r라고 할 때 a와 b를 모두 나누는 수는 r=a−bq도 나눈다. 반대로 b와 r을 모두 나누는 수는 a=bq+r도 나눈다. 따라서 두 쌍의 공약수가 같아 최대공약수도 같다.
실제 계산
84를 30으로 나누면 나머지는 24다. 다음으로 30을 24로 나누면 6이 남고 24를 6으로 나누면 0이 남는다. 마지막으로 나누는 데 사용한 6이 84와 30의 최대공약수다.
왜 끝나는가
양의 정수를 나누어 얻는 나머지는 0 이상이고 나누는 수보다 작다. 반복 과정에서 0이 아닌 나머지들이 점점 작아지므로 무한히 계속될 수 없다. 나머지가 0이 되는 순간에 계산을 마친다.
경계 조건
처음부터 한 수가 다른 수를 나누어떨어지게 하면 한 번의 나눗셈으로 끝날 수 있다. 이때도 마지막 나누는 수가 답이다. 프로그램에서는 0으로 나누지 않도록 반복 조건과 입력의 부호를 정리해야 한다.