欧几里德算法和扩展欧几里德算法

阅读数:19 评论数:0

跳转到新版页面

分类

数学

正文

1、欧几里德算法

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理: 

定理:gcd(a,b) = gcd(b,a mod 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)的公约数是一样的,其最大公约数也必然相等,得证。

2、模P乘法逆元

对于整数a、p,如果存在整数b,满足ab mod p =1,则说,b是a的模p乘法逆元。

定理:a存在模p的乘法逆元的充要条件是gcd(a,p) = 1

证明:
 首先证明充分性
 如果gcd(a,p) = 1,根据欧拉定理,a^φ(p) ≡ 1 mod p(φ(p) 表示 {0,1,...,p-1}中有多少整数与p互素),因此
 显然a^(φ(p)-1) mod p是a的模p乘法逆元。
 
 再证明必要性
 假设存在a模p的乘法逆元为b
 ab ≡ 1 mod p
 则ab = kp +1 ,所以1 = ab - kp
 因为gcd(a,p) = d 
 所以d | 1
 所以d只能为1

3、扩展欧几里德算法

扩展欧几里德算法是用来在已知a, b求解一组x,y使得ax+by = Gcd(a, b) =d(解一定存在,根据数论中的相关定理)。

(1)求解x,y方法的理解

设 a>b,

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

$a\cdot b \not= 0$时,设置

$a\cdot x1 + b\cdot y1 = gcd(a,b)$,

$b\cdot x2+(a mod b)\cdot y2 = gcd(b,a mod b$

根据欧几里德原理:

$a\cdot x1 +b\cdot y1 = b\cdot x2+(a mod b)\cdot y2$

即$a\cdot x1 +b\cdot y1 = b\cdot x2 +(a-\dfrac{a}{b}*b)\cdot y2 = a\cdot y2+b\cdot x2 -(\dfrac{a}{b}*b \cdot y2)$

根据恒等定理:$x1 = y2; y1=x2-(\dfrac{a}{b}*y2)$

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

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

4、使用扩展欧几里德算法解决不定方程的办法

对于不定整数方程pa+qb=c,若 c mod Gcd(a, b)=0,则该方程存在整数解,否则不存在整数解。
  上面已经列出找一个整数解的方法,在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后, /*p * a+q * b = Gcd(a, b)的其他整数解满足:
  p = p0 + b/Gcd(a, b) * t 
  q = q0 - a/Gcd(a, b) * t(其中t为任意整数)
  至于pa+qb=c的整数解,只需将p * a+q * b = Gcd(a, b)的每个解乘上 c/Gcd(a, b) 即可
  在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后,应该是
  得到p * a+q * b = c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b)),p * a+q * b = c的其他整数解满足:
  p = p1 + b/Gcd(a, b) * t
  q = q1 - a/Gcd(a, b) * t(其中t为任意整数)
  p 、q就是p * a+q * b = c的所有整数解。 
  编程时 exgcd 更多用于求解“中国余数定理”相关知识 举个例子 比如n除以5余2 除以13余3 那么n最小是多少,所有的n满足什么条件?
  n(min)=42
  n=42+k*65