欧几里德辗转相除法.doc

欧几里德辗转相除法.doc欧几里德辗转相除法是最大公约数(greatest common divisor)的求法。 C++代码如下: int gcd(int a, int b) { if(b == 0

欧几里德辗转相除法.doc 欧几里德辗转相除法是最大公约数(greatestcommondivisor)的求法。 C++代码如下: intgcd(inta,intb) { if(b==0) returna; else returngcd(b,a%b); } 这个算法就是利用了gcd(a,b)=gcd(b,amodb)。 证明: 对于a,b的任意公约数r，则r|a,r|b。 那么amodb=a-[a/b]*b，[a/b]是取整函数 由于r|a，r|b所以r|(amodb)。 对于b,amodb的公约数r，则r|b，r|(amodb) a=amodb+[a/b]*b,所与r|a。这样就证明了 a，b的公约数和b，amodb完全相同，则最大公约数也相同。 费马小定理 (1)p为素数,则p|(a^p-a) (2)p为素数，gcd(a,p)=1,则p|(a^(p-1)-1) 证明: 对于(2)，p是素数，a是整数且gcd(a,p)=1即他们的最大公约数是1。