同余的一些性质

 1 a*b=lcm[a,b]*gcd(a,b); 
 2 证明：
 3 令lcm[a,b]=c=ab/(a,b);
 4 因为a|c , b|c，所以c为a,b的公倍数，所以[a,b]|c；
 5 由裴蜀定理
 6 存在x,y使得
 7 ax+by=(a,b); 
 8 ax/(a,b)+by/(a,b)=1;
 9 ax[a,b]/(a,b)+by[a,b]/(a,b)=[a,b];
10 因为 c|a[a,b]/(a,b),c|b[a,b]/(a,b) ,所以换元，c是A,B,的公因数，又因为[a,b]是此时，A,B的最大公因数
11 c|[a,b],即c=[a,b]证毕；
12 
13 
14 同余
15 同余加法，减法，乘法等价，除法要互质
16 a ≡b(mod m1),  a ≡b(mod m2)--> a ≡b(mod [m1,m2])
17 m1|(a-b) ,m2|(a-b) 所以[m1,m2]|(a-b)
18 
19 ac ≡bc(mod m) -->a ≡b(mod m/(c,m));
20 m|c(a-b) 所以 (m/gcd(c,m))|(a-b);
21 
22 求解线性同余方程
23 求ax+by=c;的解
24 通过拓展欧几里得--> ax0+by0=gcd(a,b)；
25 ax0*c/(gcd(a,b))+by0*c/(gcd(a,b))=c;
26 特解就是x=c*x0/gcd(a,b),y=c*y0/gcd(a,b);
27 
28 ax0+by0=c;
29 a(x0+bt)+b(y0-at)=c;
30 ab=gcd(a,b)*[a,b]
31 xmin=x0+b/gcd(a,b)*t;
32 x0=b/gcd(a,b)*t-xmin, 把xmin看成x0/b/gcd(a,b)的余数r；
33 换元令p=b/gcd(a,b) 
34 xmin=x0%p要求正整数解 (x0+p)%p;
35 如果是ax ≡1(mod b)即 ax+by=1; 
36 因为a.b互质
37 所以xmin=(x0+b)%b; 其中x0可以用拓展欧几里得求；