辗转相除法和扩展欧几里得算法
参考自https://www.cnblogs.com/bljfy/p/9316784.html
https://blog.csdn.net/weixin_44073496/article/details/85225355
辗转相除法
证明
设q = a / b;
r = a % b;
1)若r == 0,则b为a的最大公因数
2)设a和b有公因数d,则d为r的因数
3)设b和r有公因数d,则d为a的因数
先证明2):设a = xd, b = yd,则r = a - bq = d(x - yq)
所以,a和b的公因数都为r的因数,也为b和r的公因数
在证明3):b = xd,r = yd,a = bq + r = d(xq+y)
所以,b和r的公因数都为a的因数,也为a和b的公因数
所以二者公因数集相等,那么gcd也相等
所以gcd(a, b) == gcd(a, a%b)
结合1,当a%b为0时,gcd(a, 0) ==…==gcd(a, b)
代码
1 | int gcd(int a, int b) |
扩展欧几里得算法
证明
贝祖定理及其证明
贝祖定理:
ax + by = c, x ∈ Z*
成立的充要条件是gcd(a, b) | c
证明:
设s = gcd(a, b)
,显然s | a
,并且s | b
又因为x, y ∈ Z*
所以s | ax
, s | by
s | ax + by
ax + by = s * t
(t为整数)
所以,c是s的倍数,即,c是a,b最大公因数的倍数
扩展欧几里得算法证明
利用数学归纳法
当b == 0时:在扩展欧几里得算法的最后一步,即b == 0 时候,显然存在一对整数x = 1, y = 0,使得
a * 1 + 0 * 0 = gcd(a,0)
成立设
若b > 0, 则gcd(a,b) = gcd(b, a mod b)。假设存在一对整数x, y满足 b * x + (a mod b) * y = gcd(b, a mod b)
成立因为
a mod b = a - [a / b] * b
,所以式子可以变为bx + (a - [a / b] * b) y = ay + (x - [a / b] y) b
. 这时候令x ’ = y, y ’ = ( x - [a / b] y)
就有ax’ + by’ = gcd(a, b)
.(这一步推出了下一步)
由1和2,归纳得出命题成立
代码
来自开头参考中的第二个链接
1 | typedef long long ll; |
扩展欧几里得算法的应用
以下有点超出我的知识范围orz,先copy下来,以后慢慢看,慢慢改
解线性同余方程:
描述
给定整数a,b,m,求一个整数x 使得 a * x ≡ b (mod m)
, 无解则给出无解。a * x ≡ b (mod m)
等价于a * x - b
是 m的倍数,不妨设为 -y 倍,于是该方程可以变为a * x + m * y = b
.
由前面可知该线性同余方程有解当且仅当 gcd(a,m) | b
.
代码
1 | ll exgcd(ll a, ll b,ll &x,ll &y){ |
特殊的线性同余方程a * x ≡ 1 (mod m)
(等价于求解乘法逆元)
代码
1 | ll exgcd(ll a, ll b,ll &x,ll &y){ |
扩展求解线性同余方程组
描述
先考虑两个方程组的情况t ≡ r1 ( mod a1)
(1),t ≡ r2( mod a2)
(2)
(a1,a2不一定互质) 要求t(t > 0)
则有 t = a1 * x1 + r1
, t = a2*x2 + r2
;
变形为:a1 * x1 + a2 * (-x2) = ( r2 - r1)
;
方程组有解等价于: (r2 - r1) | gcd(a1, a2)
;
我们可用扩展欧几里得算法求出 特解x10, x20; 求出最小正整数解x10;
那么要求的 t0 = a1 * x10 + r1
;
显然 t0 满足1) 式和2)式
由此推论:t0 + k * lcm(a1,a2)
是(1),(2)两个方程组的通解,lcm(a1,a2)
都可消去。
在此通解基础上可以得到新的线性同余方程 t ≡ t0 (mod lcm(a1,a2))
(3)
两个以上的时候就等价于在先求出两个线性同余方程的通解t,在和第三个方程联立又求解一次t’,不断合并。
未完待续……
hexo的markdown渲染把*都当成斜体标志来处理,本地的typora都没有!!
害得我还得一个个加上引用来避免渲染……