Euclidean Algorithm
歐幾里德演算法又稱輾轉相除法，即
(
gcd(n, 0) = 0, if n > 0
gcd(m, n) = gcd(n, m mod n), if m > n
假設m ≥ n，令r
0
= m, r
1
= n，不斷地利用毆幾里德演算法
r
0
= q
1
r
1
+ r
2
, 0 ≤ r
2
< r
1
r
1
= q
1
r
2
+ r
3
, 0 ≤ r
3
< r
2
.
.
.
r
n−2
= q
n−1
r
n−1
+ r
n
, 0 ≤ r
n
< r
n−1
r
n−1
= q
n
r
n
則gcd(m, n) = gcd(r
0
, r
1
) = gcd(r
1
, r
2
) = · · · = gcd(r
n−2
, r
n−1
) =
gcd(r
n−1
, r
n
) = gcd(r
n
, 0) = r
n
例題
94 中山資工
題目:
Find all of the possible solutions of 250x + 111y = 7, where both x
and y are integers.
Ans.
250 = 2 × 111 + 28
111 = 3 × 28 + 27
28 = 1 × 27 + 1
從最後一個式子代回去。
1 = 28 − 27
1 = 28 − (111 − 3 × 28)
整理
1 = (−1) × 111 + 4 × 28
1 = (−1) × 111 + 4 × (250 − 2 × 111)
整理
1 = (−9) × 111 + 4 × 250
寫成通式(小的為負，大的為正)
1 = (−9 + 250k) × 111 + (4 − 111k) × 250, ∀k ∈ Z
左右同乘7
7 = 7(−9 + 250k) × 111 + 7(4 − 111k) × 250, ∀k ∈ Z
所以x = 7(4 − 111k), y = 7(−9 + 250k), ∀k ∈ Z