【笔记】扩展欧几里得算法

知识递进：

1. 同余符号：a = b % c ; b ≡ a mod c → a % c = b % c
   rsa中应用：c = m ^ e % n ；m ^ e ≡ c mod n
2. gcd(a,b)
   基础算法：for i in range(0,min(a,b)):
   if a % i == 0 | b % i == 0:
   return i
3. 欧几里得算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。
   [此时mod等同于%] gcd(a,b) = gcd(b,a mod b)
   原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。
   算法：
   求gcd(a,b)[假设a>b]：
   a ÷ b = c mod d
   b ÷ d = e mod f
   d ÷ f = g mod h
   if h == 0 → f = gcd(a,b)
4. 证明：gcd(a,b) = gcd(b,a mod b) (不妨设a＞b 且r=a mod b ,r不为0)

• 法一：公约数是最大公约数的因子，得到d = e

• 法二(感觉网上这个有点错误，改了下)
  假设c = gcd(a,b),则存在m,n，使a = mc, b = nc;
  令r = a mod b，即存在k，a = kb+r, 使r = a-kb = mc - knc = (m-kn)c;
  故gcd(b,a mod b) = gcd(b,r) = gcd(nc,(m-kn)c) = gcd(n,m-kn)c;
  则c为b与a mod b的公约数;
  假设d = gcd(n,m-kn), 则存在x,y, 使n = xd, m-kn = yd; 故m = yd+kn = yd+kxd = (y+kx)d;
  故有a = mc = (y+kx)dc, b = nc = xdc; 可得 gcd(a,b) = gcd((y+kx)dc,xdc) >= dc;
  由于gcd(a,b) = c, 【故 c >= dc, d <= 1 ,又d = gcd(n,m-kn)，所以d >= 1, 】（自己删改的部分）综上：d = 1;
  即gcd(n,m-kn) = 1, 故可得gcd(b,a mod b) = c;
  故得证gcd(a,b) = gcd(b,a mod b).

原解法来源