1.逆元
a 和 p互質，a*x ≡ 1 (mod p)，那麼稱x為a關于p的逆元。
費馬小定理：假如p是質數，且gcd(a,p)=1，那麼 a^(p-1) ≡ 1（mod p）,則左右同時除以a，可以得到a的逆元為a^(p-2)
2.中國剩餘定理
中國剩餘定理給出了以下的一進制線性同餘方程組：
假設整數m1,m2, ... ,mn兩兩互質，則對任意的整數：a1,a2, ... ,an，方程組 有解，并且通解可以用如下方式構造得到：
設
是整數m1,m2, ... ,mn的乘積，并設 是除了mi以外的n- 1個整數的乘積。
設
為
模
的數論倒數(逆元)
在模
的意義下，方程組 隻有一個解：
3.組合數取模
組合數取模就是求
的值，當然根據n，m和p的取值範圍不同，采取的方法也不一樣。
（1）1<=m<=n<=1000 組合數可以采用 楊輝三角 （2）1<=m<=n<=10^18和 2<=p<=10^5,并且p是素數 可以采用Lucas定理
那麼
（3）1<=m<=n<=10^9和 2<=p<=10^5,并且p合數 先把p因素分解，然後用CRT中國剩餘定理合并