作业帮怎样利用辗转相除法求不等式中的正整数解
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/06 07:12:13
怎样利用辗转相除法求不等式中的正整数解
怎样利用辗转相除法求不等式中的正整数解
怎样利用辗转相除法求不等式中的正整数解
辗转相除法
开放分类：数学、最大公约数
辗转相除法,又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法.它是已知最古老的算法,其可追溯至前300年.它首次出现于欧几里德的《几何原本》（第VII卷,命题i和ii）中,而在中国则可以追溯至东汉出现的《九章算术》.它并不需要把二数作质因子分解.
证明：
设两数为a、b(b＜a),求它们最大公约数(a、b)的步骤如下：用b除a,得a＝bq?1＋r?1（0≤r?1＜b）.若r?1=0,则(a,b)＝b；若r?1≠0,则再用r?1除b,得b＝r?1q?2＋r?2（0≤r?2＜r?1）.若r?2＝0,则(a,b)＝r?1,若r?2≠0,则继续用r?2除r?1,……如此下去,直到能整除为止.其最后一个非零余数即为(a,b).
[编辑] 算法
辗转相除法是利用以下性质来确定两个正整数 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,并返回第一步.
[编辑] 虚拟码
这个算法可以用递归写成如下:
function gcd(a,b) {
if a mod b0
return gcd(b,a mod b);
else
return a;
}
或纯使用循环:
function gcd(a,b) {
define r as integer;
while b ≠ 0 {
r := a mod b;
a := b;
b := r;
}
return a;
}
其中“a mod b”是指取 a ÷ b 的余数.
例如,123456 和 7890 的最大公因子是 6,这可由下列步骤看出：
a b a mod b
123456 7890 5106
7890 5106 2784
5106 2784 2322
2784 2322 462
2322 462 12
462 12 6
12 6 0
只要可计算余数都可用辗转相除法来求最大公因子.这包括多项式、复整数及所有欧几里德定义域（Euclidean domain）.
辗转相除法的运算速度为 O(n2),其中 n 为输入数值的位数.
ax+by=c,把a,b互相除求余数
如:5x+12y=9
12/5....2
5/2.....1
所以9=1*9=（5-2*2）*9=5*9-(12-5*2)*9=5*9-12*9+5*18=5*27-12*9
x0=27,y0=-9