数学笔记:欧几里德算法及其扩展 – polebug

有关欧几里德算法整理:


1.一些相关概念:

<1>.整除性与约数:

①一个整数可以被另外一个整数整除即为d|a(表示d整除a,通俗的说是a可以被d整除),其含义也可以说成,存在某个整数k,使得a=kd.
②如果d|a且d>=0,则称d是a的约数。
③如果d|a,则-d|a,即a的任何约数的负数同样可以整除a.但一般规定,约数为非负数。非零整数a的约数应至少为1,且d<=|a|.
④因子:整数a的非平凡约数(除了1和它本身的约数)称为a的因子。

<2>.素数和合数.

<3>.除法定理:
对于任何整数a和任何正整数n,存在唯一整数q和r,满足0<=r<n,且a=qn+r.        等模:               
根据整数模n的余数,我们可以将所有的整数划分成n个等分类。包含整数a的模n等价类为:[a]n={a+kn}  <4>.公约数与最大公约数:
①概念:
公约数:如果d是a的约数并且d也是b的约数,则d是a与b的公约数;
两个不同时为0的整数a与b的公约数种最大的称为其最大公约数,记作gcd(a,b);
②基本性质:
公约数的重要性质:若d是a,b的公约数,则d|(a+b)且d|(a-b);且对任意整数x,y,有d|(ax+by);
gcd函数的基本性质略简单不提;

若任意整数a,b不都为0,则gcd(a,b)为a与b的线性组合集{ax+by:x,y属于Z}的最小正整数。

1 这里略带证明一下:
2
3 设s是a与b的线性组合集合中的最小正元素,并且对某个x,y属于Z,有s=ax+by,设q=a/s.
4 a mod s=a-qs;
5 由于0<=a mod s<s
6 =>a mod s=0
7 =>s|a;
8 同理,s|b
9 =>s是a与b的公约数,满足gcd(a,b)>=s;
10 又gcd(a,b)|s,s>0
11 =>gcd(a,b)<=s;
12 结合以上,gcd(a,b)=s;
13

      

2.欧几里德算法:

<1>.基本原理:gcd(a,b)=gcd(b,a mod b)

<2>.代码:

欧几里德算法://递归
int gcd(int a,int b)
{
if (b==0) return a;
else return gcd(b,a mod b);
}

最小公倍数:
int gbs(int m,int n)
{
return m*n/gcd(m,n);
}

 3.扩展欧几里德算法:

 

  <1>.形式:d=gcd(a,b)=ax+by;

  

  <2>.推导:

     设 ax1+by1=gcd(a,b);

  bx2+(a mod b)y2=gcd(b,a mod b);

  根据欧几里德原理有 gcd(a,b)=gcd(b,a mod b);

  则:ax1+by1=bx2+(a mod b)y2;

  即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;

  根据:x1=y2; y1=x2-(a/b)*y2;

     

   上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束。

 

代码如下

int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return r;
}

  

 

    

 

 

本文链接:http://www.cnblogs.com/polebug/p/3536536.html,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量