세 정수 a, b, c에 대해 c = ax + by 의 정수해가 존재하려면, a와 b의 최대공약수 d가 c|d를 만족하면 주기적인 해를 갖는다. a와 b를 선형 결합 형태로 나타내면 (유클리드 호제법) d = sa + tb 가 되는데, 이 때 정수해는 다음과 같다. m = c/d x = bk + sm y = -ak + tm 가령 100 = 7x + 5y 라고 하면, 7 = 1*5 + 2 5 = 2*2 + 1 1 = 5 - 2*2 = 5 - 2*(7 - 1*5) = -2 * 7 + 3 * 5 (s = -2, t = 3) x = 5k - 2*100 y = -7k + 3*100 k=40 이면, x=0, y=20 k=41 이면, x=5, y=13 k=42 이면, x=10, y=6 k=43 이면, x=15, y=-1 ... 정수 해가 존재하며, 자연수 해도 2쌍 존재한다. (5,13), (10,6)