Chapter 1. 数学基础 数论(一)
Sylvia's I. 欧几里得算法.
欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数(gcd).
内容:gcd(a,b) = gcd(b,a%b).
证明:设a=kb+r , 则r=a%b;
①设d为a,b的公约数,则有d|a , d|b;
且r=a-kb,故d|r;
所以d也是b , a%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,a)=gcd(-a,b)=gcd(|a|,|b|)
②gcd(a/m ,b/m)=gcd(a,b)/m
③gcd(ma,mb)=m*gcd(a,b) -------Stein算法
④ a*b=gcd(a,b)*lcm(a,b)
⑤gcd(a+b,b)=gcd(a,b)
⑥若gcd(k,b)=1,则gcd(ka,b)=gcd(a,b) -------Stein算法
代码:
int gcd(int a,int b){ if (!b) return a; return gcd(b,a%b);}
Sylvia's Ⅱ.Stein算法.
优势:与欧几里得相比,Stein抛弃除法以及取模,只有整数的移位以及加减法,对于大素数Stein将更有优势.
理论基础:
①gcd(a,0) = a
②gcd(ka,kb) = k* gcd(a,b)
③gcd(a+b,b)=gcd(a,b)---->gcd(a,b)=gcd(min(a,b),abs(a-b))
代码:
int Stein(int a,int b){ if (a==0||b==0) return a==0?b:a;//gcd(a,0) = a if (a&1==0&&b&1==0) return 2*Stein(a>>1,b>>1);//gcd(ka,kb) = k* gcd(a,b),k=2,此时是a,b都是偶数 if (a&1==0) return Stein(a>>1,b);//只有a为偶数,那么2一定不是a,b的公因数,因此将a除2 if (b&1==0) return Stein(a,b>>1);//同理 return Stein(min(a,b),abs(a-b));//如果二者都不是偶数,那么gcd(a,b)=gcd(min(a,b),abs(a-b))}
Sylvia's Ⅲ.扩展欧几里德.
内容:给出 a 和 b,解方程 ax+by=gcd(a,b)
思想:
①求其中一解x,y
gcd(a,b)=gcd(b,a%b)
ax+by=gcd(a,b)
bx'+(a%b)y'=gcd(b,a%b)
ax+by=bx′+(a%b)y′ (a%b<=>a-[a/b]*b)
ax+by=bx′+(a−⌊a/b⌋∗b)y′
ax+by=ay′+b(x′−⌊a/b⌋∗y′)
故x=y′, y=x′−⌊a/b⌋∗y′
边界条件为 gcd(a,0)=a;
②对于其通解,设已求得的一组解为(x0,y0),其他解(x,y)
有ax0+by0=ax+by (都等于gcd(a,b))
变形得a(x0-x)=b(y-y0) 两边同除gcd(a,b)
设a'=a/gcd(a,b),b'=b/gcd(a,b)
则 a'(x0-x)=b'(y-y0) 此时a'和b'必然互质,因此(x0-x)是b'的倍数,设(x0-x)=kb' 代入得 y=y0+a'k
同理,(y-y0)是a'的倍数,设(y-y0)=ka' 代入得 x=x0-b'k
所以对于方程ax+by=gcd(a,b)的任意整数解可以写成
x=x0-k*b/gcd(a,b)
y=y0+k*a/gcd(a,b) k取任意整数.
注:①推导过程并未用到“ax+by的右边是什么”
②如果gcd(a,b)=0,则意味着a和b等于0
代码:
int ex_gcd(int a,int b,int &x,int &y){ if (b==0){ x=1; y=0; return a; } int ans=ex_gcd(b,a%b,x,y); int temp=x; x=y; y=temp-a/b*y; return ans;}
Sylvia's Ⅳ. 模运算.
公式:①(a+b) % p=((a % p) + (b % p)) % p
②(a-b) % p = ((a % p) - (b % p)+p) % p
③(a*b) % p = (a % p) * (b % p) % p
注意:对于公式②,由于(a % p)可能小于(b % p),所以需要在结果上加上p.
对于公式③,需要注意(a % p) 和 (b % p) 相乘是否会溢出.
Sylvia's Ⅴ. 剩余系.
内容:对于一个正整数n,一个整数集模n所得的余数域。如7的剩余系包括7个数字:0,1,2,3,4,5,6.
Sylvia's Ⅵ. 同余.
定义:两个整数a,b,除以正整数m,若余数相同,则称"a和b关于模m同余",记作a≡b(mod m),这叫作同余式.
说明:a≡b(mod m)<=>a=km+b(k取任意整数)<=>m|(a-b)
那么对于方程ax≡b (mod m),可以理解为(ax-b)为m的倍数,设这个倍数为y,则ax-b=my,m为任意整数,所以可以写成ax+my=b
该方程有整数解的充要条件是gcd(a,m)|b.
特殊情况:当b=1时,ax≡1 (mod m)的解称为a关于模m的逆,而对于此方程有解必须满足gcd(a,m)|1,那么a和m必须互质(即gcd(a,m)=1),在此种情况下,方程有唯一解.
性质:
①反身性 a≡a (mod m).
②对称性 若a≡b(mod m),则b≡a (mod m).
③传递性 若a≡b (mod m),b≡c (mod m),则a≡c (mod m).
④ 加法 若a≡b (mod m),c≡d(mod m),则a±c≡b±d (mod m)
特别地,若a≡b (mod m),则a±k≡b±k (mod m).
定理一:若gcd(a,b)=d,则必能找到整数集中的x和y,使d=a∗x+b∗y.
定理二:若gcd(a,b)=1,则方程ax≡c(%b)在[0,b−1]上有唯一解.
证明:由定理一知,我们总可以求出ax ≡ 1 (mod b)的解x0,那么两边同时乘 c 有 a(c*x0) ≡ c (mod b),所以有x = c*x0就是 ax ≡ c (mod b)的解。由于加上或减去若干倍b都是该方程的解,所以x在[0, b-1]上有解。那么怎样确定它的唯一性呢?假设x1和x2都是[0, b-1]上的解且x1>=x2,那么就有ax1 ≡ c (mod b),ax2 ≡ c (mod b),两式相减就有a(x1-x2) ≡ 0 (mod b),即a(x1-x2)可以被b整除,但是gcd(a, b) = 1,所以只能是(x1-x2)被b整除了,但x1和x2都在[0, b-1]上,所以x1-x2也在[0, b-1]上,那么只能是x1-x2=0,因此x1=x2,所以解在[0,b−1]一定是唯一的.
定理三:若gcd(a,b)=d,则方程ax≡c(%b)在[0,b/d−1]上有唯一解.
证明:这个方程等价于ax + by = c,如果有解,两边同除d,就有a/d * x + b/d * y = c/d,即a/d * x ≡ c/d (mod b/d),同除以gcd(a,b)后一定有gcd(a/d, b/d) = 1,所以由定理二知x在[0, b/d - 1]上有唯一解。所以ax + by = c的x在[0, b/d - 1]上有唯一解,即ax ≡ c (mod b)在[0, b/d - 1]上有唯一解.
模互质与非互质求解:
对于方程组x≡a1 (mod b1)①
x≡a2 (mod b2)②x=a1*b2*c1+a2*b1*c2 (c1,c2为任意整数)
这样构造的好处是对于①式(a1*b2*c1+a2*b1*c2)mod b1 则结果只有a1*b2*c1,a1*b2*c1≡a1 (mod b1) 即b2*c1≡1 mod b1
对于②式(a1*b2*c1+a2*b1*c2)mod b2 则结果只有a2*b1*c2, a2*b1*c2≡a2 (mod b2) 即b1*c2≡1 mod b2
即 b2*c1≡1 mod b1
b1*c2≡1 mod b2 相当于求逆元
但是这样求解的必须满足的前提条件是gcd(b1,b2)=1.
那么对于不互质的情况求解如下:
对于不互质的模线性方程组,可以进行方程组合并,求出合并后的方程的解,这样就可以很快地推出方程的最终解.
鱼丽之宴
木心
”我曾见过生命
都只是行过
无所谓完成“
Sylvia
二零一七年五月六日