费马小定理+欧几里德定理+扩展欧几里德定理

  • Post author:
  • Post category:其他


<font color=“red”,size=“5”>一、费马小定理

费马小定理:

费马小定理(Fermat’s little theorem)

是数论中的一个重要定理,在1636年提出

其内容为: 假如p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p)

例如:假如a是整数,p是质数,则a,p显然互质(即两者只有一个公约数1),那么我们可以得到费马小定理的一个特例

即当p为质数时候,

<font color=“red”,size=“4”>a^(p-1)≡1(mod p)。

其中 p 是任意一个不能被 a 整除的素数

<font color=“blue”,size=“3”>

用处:

计算 2^100 除以13的余数

2

100=2

(12*8+4) (mod 13)

=((2

12)

8)

2^4 (mod 13)

=1^8

16 (mod 13) // 2^12 (mod 13) 利用费马小定理,得出 等于 1

=16 (mod 13)

=3 (mod 13)

故余数为3。

有关费马小定理的引理:

引理1

若 n 为费马指数,则 n 的任何倍数都是费马指数。换言之,对于给定的质数 p 和整数 a ,

若 a^n-1 能被 p 整除,则 a^n*m-1(m 为正整数)也能被 p 整除 。

引理2

若 m, n 为费马指数,则 m + n 也是费马指数。换言之,对于给定的质数 p 和整数 a ,

若 a^n – 1 和 a^m – 1 能被 p 整除,则 a^(n+m)- 1 也能被 p 整除 。

引理3

若 m, n 为费马指数且 m > n ,则 m – n 也是费马指数。换言之,若 a^m – 1 和 a^n- 1 都能被 p 整除(m > n),则 a^(n-m)- 1 也能被 p 整除。

引理4

所有的费马指数都是某个最小费马指数的倍数。

<font color=“red”,size=“5”>二、欧几里德定理

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。

基本算法:

设a=qb+r,其中a,b,q,r都是整数,则gcd(a,b)=gcd(b,r),即gcd(a,b)=gcd(b,a%b)。

第一种证明:

 a 可以表示成a = kb + r,则r = a mod b

假设d是a,b的一个公约数,则有

d|a, d|b,而r = a – kb,因此d|r

因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数,则

d | b , d |r ,但是a = kb +r

因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证

第二种证明:

要证欧几里德算法成立,即证: gcd(a,b)=gcd(b,r),其中 gcd是取最大公约数的意思,r=a mod b

下面证 gcd(a,b)=gcd(b,r)

设 c是a,b的最大公约数,即c=gcd(a,b),则有 a=mc,b=nc,其中m,n为正整数,且m,n互为质数

由 r= a mod b可知,r= a- qb 其中,q是正整数,

则 r=a-qb=mc-qnc=(m-qn)c

b=nc,r=(m-qn)c,且n,(m-qn)互质(假设n,m-qn不互质,则n=xd, m-qn=yd 其中x,y,d都是正整数,且d>1,

则a=mc=(qx+y)dc, b=xdc,这时a,b 的最大公约数变成dc,与前提矛盾,所以n ,m-qn一定互质)

则gcd(b,r)=c=gcd(a,b)

得证。

代码:

1、最简单的递归
int gcd(int a,int b)
 {
    if(b==0)
            return a;
   return 
       gcd(b,a%b);
}
2、优化代码
int gcd(int a,int b)
{
     return b ? gcd(b,a%b) : a;
}
3、迭代方式
int Gcd(int a, int b)
 {
      while(b != 0)
      {
      int r = b;
      b = a % b;
      a = r;
      }
     return a;
 }

<font color=“red”,size=“5”>三、扩展欧几里德

基本算法:对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x,y ,使得 gcd(a,b)=ax+by。

证明:设 a>b。

1,显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;

2,ab!=0 时

设 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;

这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.

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


a

x+b

y=gcd(a,b);

一定能求出来多组 x,y;

(其中 a,b 为整数,求出来的解 x,y 也为整数)

代码:

int ex_gcd(int a,int b,int &x,int &y,int &d)   // &x 是C++ 中的引用
{					      //  d 代表的是 gcd(a,b);
    if(b==0){
        x=1;
        y=0;
        d=a;
    }
    else{
        ex_gcd(b,a%b,x,y,d);  // 循环调用该函数
                  // 类似于求最大公约数,gcd(a,b)==gcd(b,a%b);
        t=y;  // 先把 y(刚求出来的)记录下来
        y=x-(a/b)*y; // 求得是原本刚开始式子中的 y( 根据上边证明求解)
        x=t; 
    }
}
或者是:
int ex_gcd(int a,int b,int &x,int &y,int &d)
{
    if(b==0){
        x=1;
        y=0;
        d=a;
    }
    else{
        ex_gcd(b,a%b,x,y,d);
        t=x;
        x=y;
        y=t-(a/b)*y;
    }
}
或者是:
int ex_gcd(int a,int b,int &x,int &y)
{
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int r= ex_gcd(b,a%b,x,y);
    t=x;
    x=y;
    y=t-(a/b)*y;
    return r;
}



版权声明:本文为JKdd123456原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。