第一章 整数的可除性02.pptVIP

litonghong 湖北警官学院 第一章 整数的整除性 广义欧几里得除法 设a，b是任意两个正整数，记r0=a，r1=b. 反复运用欧几里德除法，我们有 经过有限步骤，必然存在n使得rn+1=0， 这是因为 且b是有限正整数. 定理4 设a，b是任意两个正整数，则 (a，b)=rn , 其中 rn 是广义欧几里得除法中最后一 个非负余数. 证：根据定理3 ，我们有 (a，b) = (b，r2) = (r2, r3) = … =(rn-1 , rn) = (rn ，0) 再根据定理2，我们有 (a，b)=(rn，0)=rn 因此，定理4成立. 求两个整数的最大公因数的过程 首先，根据定理1 ，将求两个整数的最大公因 数转化为求两个非负整数的最大公因数； 其次，运用欧几里得除法，并根据定理3，我们 可以将求两个正整数的最大公因数转化为求两个较 小非负整数地最大公因数; 反复运用欧几里 得除法，即广义欧几里得除法， 来将求两个正整数的最大公因数转化为求0和一个正 整数的最大公因数; 最后，根据定理2，求出两个整数的最大公因数. 例1 设a=-1859，b=1573 ，计算(a，b). 解： 由定理1 ， (-1859，1573)=(1859，1573) 运用广义欧几里得除法，有 1859 = 1·1573 + 286 1573 = 5· 286 + 143 286 = 2·143 根据定理4，(-1859，1573)=143 例2 设a=169, b=121, 计算（a,b). 解 利用广义欧几里得除法，有 169 = 1· 121 + 48 121 = 2·48 + 25 48 = 1·25 + 23 25 = 1·23 + 2 23 = 11·2 + 1 2 = 2·1 所以，(169，121) = 1. 例3 求整数对 (20785 , 44350)的最大公因数. 答案 (20785 , 44350)= 5 例4 设a = 46480 , b=39423,计算(a,b). 解 利用欧几里德除法， 所以，(46480，39423)=1. 从欧几里得除法的演示中，可以观察到： 这样，逐次消去rn-1 , rn-2 , … , r3 , r2 ,我们可找 到整数s,t使得 sa +tb=(a，b) 例 5 设a=-1859 , b=1573 , 求整数s , t , 使得 sa + tb = (a , b) 运用欧几里德除法，有 1859 = 1·1573 + 286 1573 = 5·286 + 143 286 = 2·143 (-1859 , 1573)= 143 143 = 1573 - 5·286 = 1573 - 5·(1859 - 1·1573) = 5·(-1859) +6·1573 例6 设a=169 , b=121 ,求整数s , t ,使得 sa + tb = (a , b) 求解的具体过程： 定理5 设a , b 是任意两个正整数，则 sna + tnb = (a , b) 对于n = 0 , 1, 2 , … , 这里 sn , tn 归纳地定义 为 其中qj 是上式中的不完全商. 上述过程可以列成如下表格： 其中， 对于j = 1, 2 ,… ,n. 例 8 设a = 1859 , b = 1573.计算整数s,t 使得 sa + tb = (a , b) 解：根据表格及公式，我们有 因此， s= -5 , t = 6 使得 ( - 5) · 1859 + 6·1573 = 143 答案： (24871 , 3468) = 17 17 = 35 · 24871 – 251 · 3468 定理 6 整数 a , b 互素的充分必要条件是 存在整数s , t 使得 sa + tb = 1 证 根据定理 5 ，我们得到命题的必要性.