두 정수 a, b에 대하여 d = gcd(a,b) 일때 d = ax + by 의 일차결합 형태로 나타낼 수 있다 예를 들어, 218 과 21의 최대 공약수를 유클리드 호제법으로 구하면 218 = 10 * 21 + [8] 21 = 2 * 8 + [5] 8 = 1 * 5 + [3] 5 = 1 * 3 + [2] 3 = 1 * 2 + [1] 최대 공약수는 1이 되고, 일차 결합으로 나타내면... 위의 유클리드 호제법에 나온 수식들을 나머지를 기준으로 이항해 주고 역순으로 대입한다 1 = 3 -1 * [2] = [3] -1 * (5 -1 *[3]) = -1 * 5 + 2 * [3] = -1 * [5] + 2 * (8 - 1 * [5]) = 2 * 8 -3 * [5] = 2 * [8] -3 * (21 - 2 * [8]) = -3 * 21 + 8 * [8] = -3 * [21] + 8 * (218 -10 * [21]) = 8 * [218] -83 * [21]