一、整除
定义：
a、b是两个整数，b≠0 ，如果存在一个整数m使等式a=m*b成立，则称b整除a，记为b|a,a是被除数，b是除数

性质：
·若b|a,c|b,则c|a；
·若b|g,b|h,则对任意整数m，n有b|(mg+nh)

二、素数
定义：
一个大于q且只能被1和它本身整除的整数，称为 素数（质数）否则称为 合数

性质：
·若p是素数，p|ab,则p|a或p|b。
·若p是素数，a是任意整数，则有p|a(整除)或gcd(p,a)=1(互素），即素数与任意数之间可能是整除或互素的关系

三、最大公约数
定义：
最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个

性质：
欧几里得定理
设a，b，c，q是任意不全为0的整数，且
a=qb+c,其中q是整数，则有:
◆gcd(a, b)= gcd(b, c)
◆或写成gcd (a, b)=gcd (b, a mod b)
即被除数和除数的最大公因子与除数和余数的最大公因子相同。例如:
◆gcd(18, 12)= gcd(12, 6) = gcd(6, 0)=6
◆gcd(11, 10)= gcd(10, 1)= gcd(1, 0)=1

四、模运算与同余
定义：
模运算：设n是正整数，a是整数， 如果用n除a，得商为q，余数为r,即a =qn+r, 0Sr m|(a-b)
a ≡ b(mod m),b ≡ c(mod m),则a ≡ c(mod m)

五、欧拉函数
定义：
n是一个正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n) 
如小于6且与6互素的数只有1和5，因此φ(6)=2

性质：
若n是素数，则φ(n)=n-1；
若n=pq，p、q是素数且p≠q，则φ(n)=(p-1)(q-1)；
若gcd(m,n)=1，则φ(m)φ(n)=φ(mn)
若n=p₁a₁p₂a₂…pa，其中p₁，p₂，…，p为素数，a₁，a₂，…，a为正整数，则有:φ(n) = n(1-1/p₁)(1-1/p₂)…(1-1/p)

欧拉定理：
若a和n都是正整数，且gcd (a, n)=1,则有aφ(n) mod n=1，即aφ(n)≡1(mod n)

欧拉定理的应用：求解 3102 mod 11
解：因为gcd(3,11)=1，则有310mod 11=1
所以 310*10 mod 11=110=1，3100+2 mod 11=32 mod 11=9
推论：若a与n互素，则a与aφ(n)-1互为乘法逆元

六、费马小定理
定义：
如果p是一个质数，而整数a不是p的倍数，则有a(p-1)≡1(mod p)

七、扩展欧几里得定理
定义：
对于不完全为 0 的非负整数 a，b，gcd(a，b)表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd(a，b) = ax+by

·当b=0时，gcd(a,b)=a，此时x=1，y=0；
·当ab!=0时，设ax₁+by₁=gcd(a,b)，欧几里得原理有gcd(a,b)=gcd(b,a%b)
则有，gcd(b,a%b)=bx₂+(a%b)y₂
即bx₂+(a%b)y₂=ax₁+by₁
ax₁+by₁=bx₂+(a-[a/b]*b)y₂=x₂b+y₂a-[a/b]y₂b=y₂a+(x₂-[a/b]y₂)b
可以得到：x₁=y₂，y₁=x₂-[a/b]y₂
将上面思想以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归结束

八、乘法逆元
定义：
如果满足下列等式，则称x是a模p的乘法逆元：ax≡1 (mod p)且gcd(a,p)=1（a与p互质)，通常记为：x = a-1 mod p
一个数可能存在多个乘法逆元，也可能没有乘法逆元

乘法逆元的求法：
费马小定理
当p为质数时，由费马小定理得a(p-1)≡1(mod p)，为了求ax≡1 (mod p)中a模p的乘法逆元x，因为a与p互质，a*ap-2≡1 (mod p)，则x=ap-2
扩展欧几里得
ax≡1 (mod p)可以写成ax+py=1的形式，则可以用扩展欧几里得算法解出二元一次方程解出x

九、中国剩余定理
一般来讲，p₁，…，p为素数
k ≡ a₁(mod p₁)
k ≡ a₂(mod p₂)
…
k ≡ a(mod p)
有解
﹛x₁ ≡ 1( p₁)，x₁ ≡ 0( p₂)，…，x₁ ≡ 0( p) ﹜
﹛x₂ ≡ 0( p₁)，x₂ ≡ 1( p₂)，…，x₂ ≡ 0( p) ﹜
…
﹛x ≡ 0( p₁)，x ≡ 1( p₂)，…，x ≡ 1( p) ﹜

k = a₁x₁ + a₂x₂ + … + ax (mod p₁p₂…p)

例如：
k ≡ a(mod 3)
k ≡ b(mod 4)
k ≡ c(mod 5)
→k = ax + by + cz (mod 105)
﹛x ≡ 1(3)，x ≡ 0(5)，x ≡ 0(7) ﹜ x = 70
﹛y ≡ 0(3)，y ≡ 1(5)，y ≡ 0(7) ﹜ y = 21
﹛z ≡ 0(3)，z ≡ 0(5)，z ≡ 1(7) ﹜ z = 15
→k = 70a + 21b + 15c (mod 105)

十、威尔逊定理
(p-1)! ≡ -1(mod p)，(p-2)! mod p =1 ，p为质数