证明 :⇒ 若(a, b) = 1,由推论1知成立. ⇐ 若ax + by = 1, 设d = (a, b), 则d a, d b , ∴ d ax + by = 1,∴ d 1,∴ d = 1,∴(a, b) = 1, a, b互素
例题
• 例1 求(12345,678).
12345 12204 q2 = 4 q4 = 4 q6 = 2
第六节 辗转相除法
定义
设a和b是整数, b ≠ 0, 依次做带余数除法 : a = bq1 + r1 , 0 < r1 <| b | b = r1q2 + r2 , 0 < r2 < r1 (1) r
n−2
= rn −1qn + rn , 0 < rn < rn −1 > rn-1 > rn > rn +1 ,
∵ P0 = 1, P = q1 = 8, 1 ∴ P2 = q2 P + P0 = 1× 8 + 1 = 9, 1 P3 = q3 P2 + P = 1× 9 + 8 = 17, 1 P4 = q4 P3 + P2 = 3 × 17 + 9 = 60, P5 = q5 P4 + P3 = 1× 60 + 17 = 77, P6 = q6 P5 + P4 = 1× 77 + 60 = 137, P7 = q7 P6 + P5 = 4 × 137 + 77 = 625.
• 若a,b是任意两个非零整数,则存在整数x,y, 可使ax+by=(a,b)成立.
证明 : 在aQk - bPk = (-1) rk , k = 1, 2,
k -1 n -1
, n中,
令k = n, 则aQn - bPn = (-1) rn .(其中( a, b) = rn )
推论2
• 若a,b是非零整数,则a与b互素的充要条件是 存在整数x,y,适合ax+by=1.
解:125=17 × 7+6,q1 = 7, r1 = 6, 17 = 6 × 2 + 5, q2 = 2, r2 = 5, 6 = 5 × 1 + 1, q3 = 1, r3 = 1, 5 = 1× 5, q4 = 5, r4 = 0, ∴ (125,17) = 1.
∵ aQk − bPk = (−1) 又Q0 = 0, Q1 = 1,
∵ Q0 = 0, Q1 = 1, ∴ Q2 = q2Q1 + Q0 = 1× 1 + 0 = 1, Q3 = q3Q2 + Q1 = 1× 1 + 1 = 2, Q4 = q4Q3 + Q2 = 3 × 2 + 1 = 7, Q5 = q5Q4 + Q3 = 1× 7 + 2 = 9, Q6 = q6Q5 + Q4 = 1× 9 + 7 = 16, Q7 = q7Q6 + Q5 = 4 × 16 + 9 = 73.
k −1
rk , k = 1, 2,
,n
证明 :10 当k = 1时, aQ1 - bP = a - bq1 = r1 , 即a = bq1 + r1成立. 1 当k = 2时, Q2 = q2Q1 + Q0 = q2 , P2 = q2 P + P0 = q2 q1 + 1, 1 则aQ2 - bP2 = aq2 - b(q2 q1 + 1) = (a - bq1 )q2 - b = r1q2 - b = -r2 , 当k = 2时成立. 2 假设对于不超过k < m的正整数都成立, 则 aQm - bPm = a (qmQm-1 + Qm-2 ) - b(qm Pm-1 + Pm-2 )
678 18 = q1
141 564 114 114 1 = q3 27 108 24 6 4 = q5 3 6 0
∴ (12345, 678) = 3.
或 12345 = 678 ×18 + 141, q1 = 18, r1 = 141, 678 = 141× 4 + 114, q2 = 4, r2 = 114, 141 = 114 × 1 + 27, q3 = 1, r3 = 27, 114 = 27 × 4 + 6, q4 = 4, r4 = 6, 27 = 6 × 4 + 3, q5 = 4, r5 = 3, 6 = 3 × 2, q6 = 2, r6 = 0.
rn −1 = rn qn +1 + rn +1 , rn +1 = 0 且 | b |> r1 > r2 > 这一组带余数除法叫辗转相除法.
定理1
• 使用(1)中的记号,有 rn = (a, b) • 此定理在第四节中已证.
定理2
使用(1)式中的记号, 记 P0 = 1, P = q1 , Pk = qk Pk −1 + Pk − 2 , k ≥ 2, 1 Q0 = 0, Q1 = 1, Qk = qk Qk -1 + Qk -2 , k ≥ 2, 则aQk − bPk = (−1)
0
= (aQm-1 - bPm-1 )qm + (aQm-2 - bPm-2 ) = (-1) m-2 rm-1qm + (-1) m-3 rm-2 = (-1) m-1 (rm-2 - rm-1qm ) = (-1) m-1 rm , 当k = m时成立. 由10 , 20 知, 结论成立.
推论1
k −1
rk ,
∴ aQ3 − bP3 = (−1) r3 . Q2 = q2Q1 + Q0 = 2 × 1 + 0 = 2, Q3 = q3Q2 + Q1 = 1× 2 + 1 = 3. 同理P0 = 1, P = q1 = 7, 1 ∴ P2 = q2 P + P0 = 2 × 7 + 1 = 15, 1 P3 = q3 P2 + P = 1× 15 + 7 = 22, 1 即125 × 3 -17 × 22 = 1, x = 3, y = -22.
• 或 (12345,678)=(12345,339)=(12006,339)=(6 003,339)=(5664,339) =(177,339)=(177,162)=(177,81)=(96,81)=( 3,81)=3.
• 例2 求(125,17),以及x,y,使得 125x+17y=(125,17).
• • • • • • • •
1解:对169,121作辗转相除法: 169=121+48 121=2×48+25 48=25+23 25=23+2 23=11×2+1 2=2×1. 所以(169,121)=1.
• 2解:因(-1859,1573)= (1859,1573),对 1859,1573作辗转相除法: • 1859=1×1573+286 • 1573=5×286+143 • 286=2×143 • 所以(-1859,1573)=143.
∴ 4 × 525 − 9 × 231 = 21.
5解 : 对288,158作辗转相除法. 288=1 × 158+130, q1 = 1, r1 = 130, 158 = 1× 130 + 28, q2 = 1, r2 = 28, 130 = 4 × 28 + 18, q3 = 4, r3 = 18, 28 = 1× 18 + 10, q 4 = 1, r4 = 10, 18 = 1×10 + 8, q5 = 1, r5 = 8, 10 = 1× 8 + 2, q6 = 1, r6 = 2, 8 = 4 × 2, q7 = 4, r7 = 0. ∴ (288,158) = 2.
∵ P0 = 1, P = q1 = 1, 1 ∴ P2 = q2 P + P0 = 1× 1 + 1 = 2, 1 P3 = q3 P2 + P = 4 × 2 + 1 = 9, 1 P4 = q4 P3 + P2 = 1× 9 + 2 = 11, P5 = q5 P4 + P3 = 1×11 + 9 = 20, P6 = q6 P5 + P4 = 1× 20 + 11 = 31.
• 例3求整数x,y,使得1387x-162y=(1387,162).
解 :1387 = 162 × 8 + 91, q1 = 8, r1 = 91, 162 = 91× 1 + 71, q2 = 1, r2 = 71, 91 = 71× 1 + 20, q3 = 1, r3 = 20, 71 = 20 × 3 + 11, q4 = 3, r4 = 11, 20 = 11× 1 + 9, q5 = 1, r5 = 9, 11 = 9 × 1 + 2, q6 = 1, r6 = 2, 9 = 2 × 4 + 1, q7 = 4, r7 = 1, 2 = 1× 2+, q8 = 2, r8 = 0, ∵ aQk − bPk = (−1) k −1 rk ,∴ aQ7 − bP7 = (−1)6 r7 = 1.
∴1387 × 73 − 162 × 625 = 1.
另解:由等式9=4 × 2+1起逐步回代,得 1=9-4 × 2=9-4 ×(11-9)=5 × 9-4 × 11=5 ×(20-11)-4 × 11 =5 × 20-9 × 11=5 × 20-9 × (71 − 3 × 20) = 32 × 20 − 9 × 71 =32 ×(91-71) − 9 × 71 = 32 × 91 − 41× 71 = 32 × 91 − 41× (162 − 91) = 73 × 91 − 41× 162 = 73 × (1387 − 8 × 162) − 41× 162 = 73 ×1387 − 625 × 162. ∴1387 × 73 − 162 × 625 = 1.