Eculid算法以及Extend_Eculid算法证明及实现

Eculid算法欧几里得算法

证明：

设两数a,b(a<b).

令c=gcd(a,b) . 则设a=mc, b=nc 。

所以 r= r =a-kb=mc-knc=(m-kn)c 。

所以 c也是r的因数。

可以断定 m-kn 与 n 互质。【假设m-kn=xd，n=yd (d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)cd，b=nc=ycd，则a与b的一个公约数cd>c，故c非a与b的最大公约数，与前面结论矛盾】，因此，c也是b与r的最大公约数。

得证。

代码实现：

int gcd (int a, int b)

{

    return b ==  ? a : gcd(b, a%b);

}

Extend_Eculid 拓展欧几里得算法

证明：

设a>b

当b=0时，a∗1+b∗0=a=gcd(a,b)，此时x=1,y=0

当b!=0时，设

a∗x1+b∗y1=gcd(a,b)

b∗x2+a%b∗y2=gcd(b,a%b)

由于gcd(a,b)=gcd(b,a%b)，所以有a∗x1+b∗y1=b∗x2+a%b∗y2

将a%b=a−(a/b)∗b代入，

得到 a∗x1+b∗y1=a∗y2+b∗x2−(a/b)∗b∗y2

即 x1=y2,y1=x2−(a/b)∗y2

因此可以递归的定义exgcd，同样b=0时递归结束。返回最大公约数

代码实现：

void ext_gcd(int a, int b, int &d, int &x, int &y)

{

    if(!b)

    {

        d = a;

        x = ;

        y = ;

    }

    else

    {

        ext_gcd(b, a%b, d, y, x);

        y -= x*(a/b);

    }

}

巴特西

Eculid算法以及Extend_Eculid算法证明及实现

Eculid算法欧几里得算法

证明：

Extend_Eculid 拓展欧几里得算法

证明：

最新文章

热门文章

巴特西

Eculid算法 以及Extend_Eculid算法 证明及实现

Eculid算法 欧几里得算法

证明：

Extend_Eculid 拓展欧几里得算法

证明：

最新文章

热门文章

Eculid算法以及Extend_Eculid算法证明及实现

Eculid算法欧几里得算法