初等数论第一章第6节 辗转相除法

第六节 辗转相除法

定义设a和b是整数, b > 0, 依次做带余数除法 : a = bq1 + r1 , 0 < r1 < b b = r1q2 + r2 , 0 < r2 < r1 LL r n 2 = rn 1qn + rn , 0 < rn < rn 1 rn 1 = rn qn +1 + rn +1 , rn +1 = 0 且b > r1 > r2 > L > rn-1 > rn > rn +1 , 这一组带余数除法叫辗转相除法. (1)

定理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)k 1

rk , k = 1, 2,L , 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的正整数都成立, 则0

aQm - bPm = a (qmQm-1 + Qm-2 ) - b(qm Pm-1 + Pm-2 ) = (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 若a,b是任意两个非零整数,则存在整数x,y, 可使ax+by=(a,b)成立.

证明 : 在aQk - bPk = (-1) rk , k = 1, 2,L , n中,k -1

令k = n, 则aQn - bPn = (-1) rn .(其中( a, b) = rn )n -1

推论2 若a,b是非零整数,则a与b互素的充要条件是 存在整数x,y,适合ax+by=1.

证明 : 若(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

678 18 = q1

12204 q2 = 4 141 564 114 114 1 = q3 q4 = 4 27 108 24 6 4 = q5 3 6 q6 = 2 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.

或 (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).

解: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.

Q aQk bPk = ( 1) 又Q0 = 0, Q1 = 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.

3 1