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

第六节 辗转相除法 定义 定理1 使用(1)中的记号,有 此定理在第四节中已证. 定理2 推论1 若a,b是任意两个非零整数,则存在整数x,y,可使ax+by=(a,b)成立. 推论2 若a,b是非零整数,则a与b互素的充要条件是存在整数x,y,适合ax+by=1. 例题 例1 求(12345,678). 或 (12345,678)=(12345,339)=(12006,339)=(6003,339)=(5664,339) =(177,339)=(177,162)=(177,81)=(96,81)=(3,81)=3. 例2 求(125,17),以及x,y,使得125x+17y=(125,17). 例3求整数x,y,使得1387x-162y=(1387,162). 思考问题 1 求(169,121). 2 求(-1859,1573). 3 求(221,391,136). 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. 3解:(221,391,136)= ((221,391),136)=(17,136)=17. 挑战自我 四位数aabb是平方数，求出这样的数。 课后作业 * *