关于数论的知识整理——待更新

一.整除

　　性质:

1. 如果$amid b$且$bmid c$,则$amid c$
2. 若$amid b$且$amid c$,则对于任意整数$x,y$有$amid (b*x+c*y)$
3. 若$amid n,bmid n$且$gcd(a,b)==1$,则$(a*b)mid n$
4. 若$amid n,bmid n$,则$(a*b/gcd(a,b))mid n$     （因为$gcd(a,b/gcd(a,b))==1$）

二.同余

　　性质：

1. 自反性:$aequiv a(mod m)$
2. 对称性:若$aequiv b(mod m)$,则$bequiv a(mod m)$
3. 传递性:若$aequiv b(mod m)$,$bequiv c(mod m)$,则$aequiv c(mod m)$
4. 同加性:若$aequiv b(mod m)$,则$a+cequiv b+c(mod m)$
   若$aequiv b(mod m)$,$cequiv d(mod m)$,则$a+cequiv b+d(mod m)$
5. 同乘性:若$aequiv b(mod m)$,则$a*cequiv b*c(mod m)$
   若$aequiv b(mod m)$,$cequiv d(mod m)$,则$a*cequiv b*d(mod m)$
6. 同幂性:若$aequiv b(mod m)$,则$a^cequiv b^c(mod m)$
7. 若$aequiv x(mod p)$,$aequiv x(mod q)$且$(p,q)$互质,则$aequiv x(mod p*q)$
   　　证明:$a*qequiv x*q(mod p*q)$且$a*pequiv x*p(mod p*q)$
   　　则$a*(q-p)equiv x*(q-p)(mod p*q)$
   　　进一步可以得出$a*(q\%p)equiv x*(q\%p)(mod p*q)$
   　　如此反复取模可以得出$a*(gcd(q,p))equiv x*(gcd(q,p))(mod p*q)$

三.最大公约数

　　求法

1. 辗转相除法:
   原理gcd(a,b)=gcd(a-b,b).(a>b)

   int gcd(int a,int b){
       return b?gcd(b,a%b):a;
   }

2. Stein算法
   思想：
   1. 如果$x==0$,则$gcd(x,y)=y$
   2. 如果$y==0$,则$gcd(x,y)=x$
   3. 如果$x,y$都为偶数,则$gcd(x,y)=2*gcd(x/2,y/2)$
   4. 如果$x$为偶数,$y$为奇数,则$gcd(x,y)=gcd(x/2,y)$
   5. 如果$y$为偶数,$x$为奇数,则$gcd(x,y)=gcd(x,y/2)$
   6. 如果$x,y$都为奇数,则$gcd(x,y)=gcd(x-y,y)$