辗转相除法的应用

求不定方程的一组整数解方法
[注：以下出现的qi，ri括号中的是下标，gcd(a,b)为a,b的最大公约数]
辗转相除法可以求出特定条件的不定方程的一组整数解。
设不定方程为ax+by=c，其中a,b,c为整数，且 gcd(a,b) | c
a,b辗转相除的算式为
b=q1 a+r2
a=q2 r2+r3
r2=q3 r3+r4

rn-2=qn-1rn-1+rn
rn-1=qnrn
其中rn=gcd(a,b)，不妨令b=r0，a=r1，rn+1=0
第i个算式为
ri-1= qi×ri+ ri+1
所以ri+1= ri-1 - qi×r(i)(1)
用公式(1)可以得到rn=gcd(a,b)关于a,b的线性组合sa+tb=gcd(a,b)
所以不定方程a×x+b×y=c的一组特解为x=s×c/gcd(a,b) y=t×c/gcd(a,b)
举例说明
例如不定方程为326x+78y=4，求出一组整数解x,y
求（326,78）的算式为：
326=478+14
14=326-478
78=514+8
8=78-514
14=18+6
6=14-18
8=16+2
2=8-16
6=32
所以
2=8-6=8-（14-8）
=28-14=2（78-514）-14
=278-1114=278-11（326-478）
=4678-11326
即2=(-11)326+4678
所以4=(-22)326+9278
所以x = - 22, y = 92是不定方程326x+78y=4的一组解。

辗转相除法,
又名欧几里德算法乃求两个正整数之最大公因子的算法。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。

如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。另一种求两数的最大公约数的方法是更相减损法。

扩展资料：

辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公约数的：

1、若 r 是 a ÷ b 的余数, 则gcd(a,b) = gcd(b,r)

2、a 和其倍数之最大公约数为 a。

另一种写法是：

1、a ÷ b，令r为所得余数（0≤r<b），若 r = 0，算法结束；b 即为答案。

2、互换：置 a←b，b←r，并返回第一步。

参考资料来源：百度百科——辗转相除法

辗转相除法是求最大公约数的另一种方法。具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
例如：求112和77的最大公约数。
112=771+35(余数)
77=352+7(余数)
35=75+0(余数)
所以最大公约数是：7

求最小公倍数和最大公因数的最简便的方法有哪些
1观察法：比如两个数都是偶数
那么可以同时除以2后再观察
各位是5
和0
可以同时除5
2最准确的方法
相减法
在古代叫左右相更法
求A与B最大公因数：A
大于B
A-kB=C
k为整数
B-nC=D
一直到差为质数为止
比如；求221
与143的最大公因数
221-143=78
143-78=65
78-65=13
所以是13
143=13x11
221=13x17
求最小公倍数：=AxB÷
最大公因数
比如143
221
求最小公倍数=143x221÷13=2431
辗转相除的定义：
所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。
更相减损术的定义：
就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。

在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。 两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 × 105 + (−2) × 252。这个重要的等式叫做贝祖等式。 辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年），所以它是现在仍在使用的算法中最早出现的。这个算法原先只用来处理自然数，但在19世纪，辗转相除法被推广至其他类型的数，如高斯整数和一元多项式。自此，现代抽象代数概念如欧几里得整环开始出现。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。 辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，寻找满足中国剩余定理的数，或者求有限域的倒数。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。 辗转相除法处理大数时非常高效，它需要的步骤不会超过较小数的位数（十进制下）的五倍。加百利·拉梅(Gabriel Lamé)于1844年证明了这点，开创了计算复杂性理论。

辗转相除法
辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。

---