서로 다른 크기의 물통으로 정확한 양을 만들 수 있는지는 시행착오의 문제가 아니라 GCD와 정수의 선형결합 문제이다. Euclidean Algorithm은 GCD를 빠르게 구하고, 역추적을 통해 실제 선형결합의 계수까지 찾는다.
물통 문제
3갤런과 7갤런 물통만 사용하여 정확히 2갤런을 만들 수 있는지 생각하자. 물통을 가득 채우거나 비우고, 한 물통에서 다른 물통으로 물을 옮기는 동작을 반복할 수 있다.
한 방법은 다음과 같다.
- 3갤런 물통을 채워 7갤런 물통에 붓는다.
- 다시 3갤런 물통을 채워 7갤런 물통에 붓는다. 7갤런 물통에는 6갤런이 있다.
- 3갤런 물통을 다시 채운 뒤 7갤런 물통이 가득 찰 때까지 붓는다.
7갤런 물통에는 1갤런만 더 들어가므로 3갤런 물통에 2갤런이 남는다.
이 과정에서 만들 수 있는 양은 3과 7의 정수 선형결합으로 표현된다.
음수 계수는 그만큼 물을 버리거나 반대 방향의 동작을 수행하는 효과로 이해할 수 있다.
Greatest Common Divisor
두 정수 의 공약수 중 가장 큰 양의 정수를
라고 한다. 이면 어떤 정수 가 존재하여
가 성립한다. 이를 Bézout’s Identity라고 한다.
더 일반적으로 로 만들 수 있는 정수들은 정확히 의 배수이다.
- 모든 는 의 배수이다. 가 를 모두 나누기 때문이다.
- Bézout’s Identity로 를 만들 수 있으므로 그 정수배 도 만들 수 있다.
따라서 물통 크기가 이고 목표량 가 더 큰 물통의 용량을 넘지 않을 때, 채우기·비우기·옮기기만으로 를 만들 수 있는 기준은
이다. 즉 목표량이 GCD의 배수이면 만들 수 있고, GCD의 배수가 아니면 만들 수 없다.
Euclidean Algorithm
나눗셈 알고리즘에서
이면 의 공약수와 의 공약수는 같다. 왜냐하면 이기 때문이다. 따라서
이다.
이 과정을 나머지가 0이 될 때까지 반복하면 마지막 0이 아닌 나머지가 GCD이다.
예를 들어 와 에서는
따라서
이다.
역추적으로 선형결합 구하기
나눗셈 식을 거꾸로 대입하면 GCD를 원래 두 수의 선형결합으로 쓸 수 있다.
즉
이다. 432는 이므로
처럼 표현할 수 있다. 반면 316은 108의 배수가 아니므로 인 정수해는 존재하지 않는다.
역추적은 Euclidean Algorithm의 나눗셈 식만 거꾸로 대입하는 과정이다. 별도의 정수론 이론을 많이 사용하지 않고도 GCD가 실제로 어떤 선형결합으로 만들어지는지 확인할 수 있다는 점이 중요하다.
이 글에서는 물통 문제와 GCD의 연결까지만 다룬다. 소수, 합동식, Euler 함수, RSA와 같은 정수론 주제는 별도의 정수론 시리즈에서 다룬다.
정리
GCD는 두 정수의 모든 선형결합이 가질 수 있는 기본 단위이다. Euclidean Algorithm은 나머지를 반복하여 GCD를 구하고, 역추적은 GCD를 원래 두 수의 선형결합으로 표현한다. 두 물통으로 특정한 양을 만들 수 있는지는 목표량이 GCD의 배수인지 확인하여 판단할 수 있다.
연습 문제
- Euclidean Algorithm으로 을 구한다.
- 정수 를 찾아 을 만족시킨다.
- 6갤런과 10갤런 물통으로 정확히 7갤런을 만들 수 있는지 GCD로 판단한다.
풀이
1번
따라서 이다.
2번
역추적하면
따라서 한 해는 , 이다.
3번
이고 2는 7을 나누지 않는다. 따라서 6갤런과 10갤런 물통의 채우기·비우기·옮기기 동작만으로 정확히 7갤런을 만들 수 없다.