根据定理4的证明，用辗转相除法可以把两个数的最大公因数表示为这两个数的倍数和.
例7 把（5767，4453)表示成5767与4453的倍数和.
解 逆转例5的求解过程，可得
可见，这一过程烦琐而且容易出错，欧拉给出了下面的方法，我们称之为欧拉算法，其步骤如下：
（1)最后一个商q6=3不要，将其余的商按相反次序排成一行：
写在横线上方.
（2)在横线下方，对齐横线上方左数第一个商q5写q5，在q5的左边写数1.
（3)用横线上方左数第二个商q4按箭头所示方向乘q5，再加q5左侧箭头所指向的数值1，把所得结果q4q5＋1对齐q4写在横线下方.以下各步仿照上一步进行，直到算写完毕为止.
（4)在横线下方最后写出的两个数，就是“把（5767，4453)表示成5767与4453的倍数和”时，5767，4453的倍数的绝对值，倍数的符号分别为（-1)4，（-1)5，其指数分别为辗转相除的次数减2、减1.
即73=（5767，4453)
=（-1)4×17×5767＋（-1)5×22×4453
=17×5767-22×4453.
实际解题时，箭头可以省略.该方法在后面各章均有应用，其理论依据见本章末的拓展阅读.
例8 求一对整数x，y，使37x＋107y=25.
分析 先把（37，107)=1表示成37与107的倍数和，再在两边同乘25，即可求得一对整数x，y.
解
因此，（37，107)=1=37×（-1)3×26＋107×（-1)2×9
=37×（-26)＋107×9，
25=37×（-26×25)＋107×（9×25)(www.xing528.com)
=37×（-650)＋107×225.
故x=-650，y=225.
习题1.5
1.设p为质数，a为整数，求证：p|/a⇔（p，a)=1.
2.求证：（a，b)=（a-b，b)，反复运用这个结论求最大公因数的方法叫作辗转相减法.用这一方法求：
3.将0至9十个数字按任意顺序填入下面的“□”内，得28位数：
这些28位数中有多少个可被396整除？
4.某人几个月前买72只桶所花钱数记的账有两个数字已认不清，现状是□67.9□元，请你补上这笔账.
5.从0，3，5，7中任意取三个，排成能同时被2，3，5整除的三位数，共有多少个？
6.用欧拉算法完成下列各题：
（1)把（150，42)表示为150和42的倍数和；
（2)求整数s，t，使253s＋449t=（253，449).
7.设a，b∊Z，且a≤b，若ab=5766，（a，b)=31，求a，b.
8.设a，b∊Z，a≤b，若a＋b=50，（a，b)=5，求a，b.
9.去今两年电子零件售价不变，收入分别为3893.93元、8311.19元，问去年卖出多少个零件？
10.某大于1的整数除300，262，205余数相同，求这个整数（首届“华罗庚金杯”少年数学邀请赛题).
11.某商厦销售某种货物，去今两年销售金额分别为36963元、59570元，若两年销售单价相同且为整数元，去今两年销售这种货物各多少件？
12.有两个容量分别为27L，15L的容器，可否用它们从足量的桶油中倒出6L的油来？
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
