최대공약수
두 정수의 최대공약수는 두 수를 모두 나누어떨어지게 하는 수 가운데 가장 큰 수이다. 즉 이보다 큰 수로는 두 수를 모두 나누어떨어지게 할 수 없다.
예를 들어 24와 32를 보자. 두 수의 최대공약수는 무엇일까? 먼저 두 수를 모두 나누어떨어지게 하는 수를 찾는다.
- 예를 들어 12는 24를 나누어떨어지게 하지만 32는 그렇지 않다. 32 / 12는 2.666…으로 정수가 아니기 때문이다. 따라서 12는 24와 32의 최대공약수가 될 수 없다.
- 4는 어떨까? 4는 두 수를 모두 나누어떨어지게 한다. 24 / 4는 6이고 32 / 4는 8이다. 따라서 4가 첫 번째 후보이다. 두 수를 모두 나누어떨어지게 하는 더 큰 수는 없을까?
- 8은 24와 32를 모두 나누어떨어지게 하고, 4보다 크다.
- 8보다 크면서 두 수를 모두 나누어떨어지게 하는 수는 없다. 따라서 8이 24와 32의 최대공약수이다.
유클리드 호제법으로 최대공약수 구하기
유클리드 호제법을 이용하면 두 수의 최대공약수를 꽤 간단히 구할 수 있다. 최대공약수를 구하려는 두 수 x와 y가 있다고 하자. 예로 x = 50, y = 35로 해 보자. 그러면 다음과 같이 한다.
- x / y를 계산하고 나머지를 기억한다. 이 나머지를 z라고 하자. 이 예에서는 50 / 35를 계산하면 나머지가 z = 15이다.
- 이제 변수를 바꾼다. 변수 x에 y의 값을, y에 z의 값을 넣는다. 원래 x의 값은 버린다. 이 단계를 마치면 x = 35, y = 15이다.
- 이제 y가 0인지 확인한다. 0이면 최대공약수는 x이다. y가 0이 아니므로 계속해서 첫 단계부터 다시 되풀이한다.
- 다시 x / y, 즉 35 / 15를 계산하면 나머지는 z = 5이다.
- 변수를 바꾸면 x = 15, y = 5이다. y가 0이 아니므로 계속한다.
- x / y, 즉 15 / 5를 계산한다. 나머지는 z = 0이다.
- 변수를 바꾸면 x = 5, y = 0이다.
- 이제 y = 0이므로 알고리즘이 끝난다. 최대공약수는 x = 5이다.
두 수의 순서는 상관없다는 것이 중요하다. 예의 두 수를 바꾸면 x = 35, y = 50이 된다. 방법은 같다.
- x / y, 즉 35 / 50을 계산하면 나머지는 z = 35이다.
- 변수를 바꾸면 x = 50, y = 35이다.
- 이 단계를 마치고 나면 변수 x와 y의 값이 서로 바뀌었을 뿐이라는 것을 알 수 있다…
계산기
이 계산기는 최대공약수를 구해 준다.