高中数学的辗转相除法问题

发布网友发布时间：2022-05-02 02:47

共2个回答

热心网友时间：2022-06-27 05:16

辗转相除法百科名片欧几里德辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。简单的想法　　设两数为a、b(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a＝bq......r 1(0≤r)。若r1=0，则(a，b)＝b；若r1≠0，则再用r1除b，得b＝r1q......r2 (0≤r2).若r2＝0，则(a，b)＝r1，若r2≠0，则继续用r2除r1,……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。原理及其详细证明　　在介绍这个方法之前，先说明整除性的一些特点（下文的所有数都是正整数，不再重覆），我们可以这样给出整除性的定义：　　对于二个自然数a和b，若存在正整数q，使a=bq，则a能被b整除，b为a的因子，a为b的倍数。　　如果a能被c整除，并且b也能被c整除，则c为a、b的公因数（公有因数）。　　由此我们可以得出以下推论：　　推论1、如果a能被b整除（a=qb），若k为正整数，则ka也能被b整除（ka=kqb）　　推论2、如果a能被c整除（a=hc），b也能被c整除（b=tc），则(a±b)也能被c整除　　因为：将二式相加：a+b=hc+tc=(h+t)c 同理二式相减：a－b=hc－tc=(h－t)c 　　所以：(a±b)也能被c整除　　推论3、如果a能被b整除（a=qb），b也能被a整除（b=ta），则a=b 　　因为：a=qb　b=ta　a=qta qt=1 因为q、t均为正整数，所以t=q=1 　　所以：a=b 　　辗转相除法是用来计算两个数的最大公因数，在数值很大时尤其有用，而且应用在电脑程式上也十分简单。其理论如下: 　　如果 q 和 r 是 m 除以 n 的商及余数，即 m=nq+r，则 *(m,n)=*(n,r)。　　证明是这样的: 设 a=*(m,n)，b=*(n,r) 　　证明：　　∵a为m,n的最大公约数，　　∴m能被a整除，且n也能被a整除，　　∴由推论1得：qn也能被a整除，　　∴ 由推论2得：m-qn也能被a整除，　　又 ∵m-qn=r，　　∴r也能被a整除，即a为n和r的公约数（注意：还不是最大公约数）　　∵b为n和r的最大公约数，a为n和r的公约数　　∴a≤b，　　同理　　∵b为n, r的最大公约数，　　∴n能被b整除，且r也能被b整除，　　∴由推论1得：qn也能被b整除，　　∴由推论2得：qn+r也能被b整除，　　又∵m=qn+r，　　∴m也能被b整除，即b为m和n的公约数，（注意：还不是最大公约数）　　∵a为m,n的最大公约数，b为m和n的公约数，　　∴b≤a，　　由以上可知：　　a≤b与b≤a同时成立，　　故可得　　a=b，　　证毕。　　例如计算 *(546, 429) 　　*(546, 429) 546=1*429+117 　　=*(429, 117) 429=3*117+78 　　=*(117, 78) 117=1*78+39 　　=*(78, 39) 78=2*39 　　=39 [编辑本段]计算机算法自然语言描述　　辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：　　1. 若 r 是 a ÷ b 的余数, 则　　*(a,b) = *(b,r) 　　2. a 和其倍数之最大公因子为 a。　　另一种写法是：　　1. a ÷ b，令r为所得余数（0≤r＜b）　　若 r = 0，算法结束；b 即为答案。　　2. 互换：置 a←b，b←r，并返回第一步。流程图　　流程图(当型) 伪代码　　这个算法可以用递归写成如下: 　　function *(a, b) { 　　if b<>0 　　return *(b, a mod b); 　　else 　　return a; 　　} c语言实现　　/* 辗转相除法（递归）*/ 　　#include <stdio.h> 　　int Gcd(int a,int b); 　　int main(void ) 　　{ 　　int m,n,t; 　　printf("Enter the two figures:"); 　　scanf("%d %d",&m,&n); 　　printf("Gcd:%d\n",Gcd(m,n)); 　　return 0; 　　} 　　int Gcd(int m,int n)//最大公约数　　{ 　　int t; 　　if(m<n) 　　{t = n,n = m,m = t;} 　　if(n == 0) return m; 　　else return Gcd(n,m%n); 　　} pascal实现　　function *(a,b:integer):integer; 　　begin 　　if b=0 then *:=a 　　else *:=* (b,a mod b); 　　end ; 数据举例　　其中“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 时间复杂度　　辗转相除法的运算速度为 O(n2)，其中 n 为输入数值的位数。辗转相除法求不定方程的特解　　辗转相除法可以求出不定方程的一组整数解。　　设不定方程为a x+b y=c，其中a,b,c为整数且lcm(a,b)|c 　　a,b辗转相除的算式为　　b=q(1) a+r(2) 　　a=q(2) r(2)+r(3) 　　r(2)=q(3) r(3)+r(4) 　　... 　　r(n-2)=q(n-1)r(n-1)+r(n) 　　r(n-1)=q(n)r(n) 　　其中r(n)为lcm(a,b)，不妨令b=r(0)，a=r(1)，r(n+1)=0 　　第i个算式为　　r(i-1)=q(i)r(i)+r(i+1) 　　所以r(i+1)=r(i-1)-q(i)(ri) (*) 　　用公式(*)可以得到r(n)=lcm(a,b)关于a,b的线性组合sa+tb=lcm(a,b) 　　所以不定方程a x+b y=c的一组特解为　　x=sc/lcm(a,b) 　　y=tc/lcm(a,b) 　　例如：　　不定方程为326x+78y=4 　　求(163,39)的算式为　　326=4*78+14 14=326-4*78 　　78=5*14+8 8=78-5*14 　　14=1*8+6 6=14-1*8 　　8=1*6+2 2=8-1*6 　　6=3*2 　　所以　　2 　　=8-6=8-(14-8) 　　=2*8-14=2*(78-5*14)-14 　　=2*78-11*14=2*78-11*(326-4*78) 　　=46*78-11*326 　　即2=(-11)*326+46*78 　　所以4=(-22)*326+72*78 　　所以x=-22,y=72是不定方程326x+78y=4的一组特解　　注：q(i)，r(i)，括号中的是下标，lcm是求最大公约数按此方法 6497 3869 2628 3869 2628 1241 2628 1241 1387 1387 1241 146 1241 146 1095 1241 1095 146 1095 146 949 949 146 803 803 146 657 657 146 511 511 146 365~~~~~~~~~~~~146 73 73最大公约数为73 3869=73*53 6497=89*73最小公倍数 73*53*89=344341

热心网友时间：2022-06-27 05:16

6497-3869=26283869-2628=12412628-1241=13871387-1241=1461241-146=10951095-146=949949-146=803803-146=657657-146=511511-146=365365-146=219219-146=73146与73的最大公约数为73可知3869与6497的最大公约数为73那么3869与6497的最小公倍数为3869*6497/73=344341