跳到主要内容

最大公约数、扩展欧几里得算法和最小公倍数

参考资料: 1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c

2.余红兵:《数学奥林匹克小丛书(第二版)高中卷10————数论》

最大公约数​

设a,b∈Za,b\in Z,如果d∈Zd\in Z且d∣a,d∣bd|a,d|b,则称dd是aa和bb的公因子(公约数)。 若d≥0d\ge 0,且aa和bb的所有公因子都整除dd,则称dd是aa和bb的最大公约数,记作gcd⁡(a,b)\gcd(a,b)。

之前CSDN上我也写过一篇gcd筛: https://blog.csdn.net/hustle28214/article/details/128601837?spm=1001.2014.3001.5501

互素​

设a,b∈Za,b\in Z,若gcd⁡(a,b)=1\gcd(a,b)=1,则称aa和bb互素。 互素的a,ba,b公因子仅有±1\pm 1,该条件可反推出a,ba,b两数互素。

根据定义有结论: 设gcd⁡(a,b)=d\gcd(a,b)=d,则存在q1,q2∈Zq_1,q_2\in Z,使得a=q1d,b=q2da=q_1 d,b=q_2 d,且gcd⁡(q1,q2)=1\gcd(q_1,q_2)=1。

若gcd⁡(q1,q2)=t>1\gcd(q_1,q_2)=t>1,则gcd⁡(a,b)=td>d\gcd(a,b)=td>d,与“最大”矛盾。

欧几里得算法(辗转相除法)​

设a≥b≥0a\ge b\ge 0,求gcd⁡(a,b)\gcd(a,b) 对于上述条件下的a,ba,b,有a=qb+ra=qb+r; b=0b=0时,gcd⁡(a,0)=a\gcd(a,0)=a b>0b>0时,gcd⁡(a,b)=gcd⁡(b,r)=gcd⁡(r1,r2)\gcd(a,b)=\gcd(b,r)=\gcd(r_1,r_2)

gcd⁡(a,b)=gcd⁡(b,r)\gcd(a,b)=\gcd(b,r)这条推广有必要演示一下: gcd⁡(40,3)=1\gcd(40,3)=1 gcd⁡(40,3)=gcd⁡(3,1)=gcd⁡(1,0)=1\gcd(40,3)=\gcd(3,1)=\gcd(1,0)=1 依次如此操作直到见到0

int gcd(int x, int y)
{
int r = x % y;
while (r != 0)
{
x = y;
y = r;
r = x % y;
}
return y;//最大公约数实现

}

扩展欧几里得算法​

(重要)定理5-1(最大公约数表示定理)(裴蜀定理)

设a,b∈Za,b\in Z,d=gcd⁡(a,b)d=\gcd(a,b),则存在s,t∈Zs,t\in Z,使得as+bt=das+bt=d。

特别地:gcd⁡(a,b)=1\gcd(a,b)=1 ———— as+bd=1as+bd=1(充要)

推论:d∣vd|v ———— as+bt=vas+bt=v

证明:

设b≥ab\ge a,b=ax1+r1b=ax_1+r_1,那么b mod ab \bmod a后b=r1b=r_1。

重复辗转相除直至余数为0。

b=ax1+r1b=ax_1+r_1, a=r1x2+r2a=r_1x_2+r_2, ......, rk−3=rk−2xk−1+rk−1r_{k-3}=r_{k-2}x_{k-1}+r_{k-1} (2) rk−2=rk−1xk+rkr_{k-2}=r_{k-1}x_k+r_k,(1) rk−1=rkxk+1+rk+1r_{k-1}=r_kx_{k+1}+r_{k+1}。

此时rk+1=0r_{k+1}=0(余数)。由此得出rk=dr_k=d(最大公约数)。将此式代入(1)式,移项得到d=rk−2−rk−1xkd=r_{k-2}-r_{k-1}x_k。

将此式与(2)式联立,得到d=rk−2−(rk−3−rk−2xk−1)xkd=r_{k-2}-(r_{k-3}-r_{k-2}x_{k-1})x_k。

展开,得到d=m1rk−2−n1rk−3d=m_1 r_{k-2}-n_1 r_{k-3}。

上述所有提及皆为整数,则m1(1−xk−1xk)m_1(1-x_{k-1}x_k),n1(−xk)n_1(-x_k)必为整数。

相同的操作可以重复做,不断带入之前的式子可以发现最后可以化成d=mka+nkbd=m_k a+n_k b。

而显然mk,nkm_k,n_k为整数。

证毕。

对于第二条“特别地”的证明如下:

假设gcd⁡(a,b)≠1\gcd(a,b)\neq 1。

那么,将aa表示为k1gcd⁡(a,b)=ak_1 \gcd(a,b)=a,b=k2gcd⁡(a,b)b=k_2 \gcd(a,b)。

代入as+bd=1as+bd=1:k1gcd⁡(a,b)s+k2gcd⁡(a,b)r=1k_1 \gcd(a,b)s + k_2 \gcd(a,b)r = 1。

即,(k1s+k2r)=1/gcd⁡(a,b)(k_1 s + k_2 r) = 1/\gcd(a,b)

那么右式取值区间为(0,1)(0,1),显然无法满足整数解性质。

所以gcd⁡(a,b)=1\gcd(a,b)=1才能使as+bd=1as+bd=1有整数解。

想一想,如果要证其必要性,则假设as+bd=1as+bd=1没有整数解,右式=1=1,也必定存在s,d∈Zs,d\in Z使得方程有解。

第三条推论自不必说,vv是dd的整数倍。

所以,扩欧相对于欧几里得算法的扩展性就是:使用欧几里得算法时,利用余数和商向上迭代出sn,tns_n,t_n。这同样也是在计算二元一次不定方程。

通过扩欧我们可以找到判断二元一次不定方程是否有整数解的方法:

对于方程ax+by=zax+by=z,只有满足gcd⁡(a,b)∣z\gcd(a,b)|z,方程才有整数解。

最小公倍数​

设a,b∈Za,b\in Z,若m∈Zm\in Z分别是aa和bb的倍数,mm称为aa和bb的公倍数。

记a,ba,b的最小公倍数为lcm(a,b)\mathrm{lcm}(a,b),若mm是aa和bb所有正的公倍数中最小,mm称作aa和bb的最小公倍数。

lcm(a,b)=abgcd⁡(a,b)\mathrm{lcm}(a,b) = \frac{ab}{\gcd(a,b)}。

我在CSDN那篇上写“最小公倍数的求算依赖于最大公约数的求算”,其实这有些以偏概全,求最小公倍数的算法并不止这一种。下面就记录一下这种不需要找最大公约数的神奇算法(更相增益术/更相减损术): 设有两正整数0\<a\<b0\<a\<b。

aa更小,aa自加成2a2a;此时若发现bb更小,bb自加,成2b2b;...;若发现aa更小,aa自加,直到2ka=2k−1b2k a = 2k-1 b。那么2ka2k a就等于lcm(a,b)\mathrm{lcm}(a,b)。

int lcm(int a,int b)
{
while(a!=b)
{
if(a\<b)
a+=a;
else if(b\<a)
b+=b;

}
return a;
}