数学-数论-欧几里得算法

Posted by

定义

欧几里得算法用于求两个正整数的最大公因数,其内容为:设$latex gcd(a,b)$为正整数$latex a,b$的最大公因数,则$latex gcd(a,b)=gcd(b,a\ mod\ b)$。

求解算法

思路与简单证明

不妨设$latex gcd(a,b)=c,a>b,\lfloor \frac ab\rfloor=k,a\ mod\ b=r$;
令$latex a=mc,b=nc$,易得$latex gcd(m,n)=1$;
代入得$latex r=a-bk=mc-nck=(m-nk)c$;
若要证$latex gcd(a,b)=gcd(b,r)=c$,就要证$latex gcd(n,m-nk)=1$;
假设$latex gcd(n,m-nk)=d\neq 1$;
设$latex n=xd,m-nk=yd$;
代入得$latex m=ydk+xd=(x+yk)d$;
得$latex gcd(n,m)=d\neq 1$,与$latex gcd(n,m)=1$矛盾,故假设不成立,即$latex gcd(n,m-nk)=1$,故得证;
于是我们可以递归实现,边界条件:设在第$latex k$层递归$latex b_k=0$,即第$latex k-1$层递归$latex a_{k-1}\ mod\ b_{k-1}=0$时,可得$latex a_{k-1}$是$latex b_{k-1}$的倍数,即$latex gcd(a_{k-1},b_{k-1})=b_{k-1}$,得出$latex gcd(a_1,b_1)=b_{k-1}$;
故可在第$latex k$层递归返回$latex a_k$,终止递归,得出答案。

实现

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注