定义
若整数a和整数b，除以正整数m得到的余数相等，成a，b模m同余，记作。
费马小定理
若p是质数，gcd(a,p)=1,那么有
欧拉定理
若p是质数，gcd(a,n)=1,那么有
欧拉定理推论
若正整数a，n互质，则对于任意的
当a，n不一定互质时也满足
原因在于指数循环节，第
个往后一定会循环，
扩展欧几里得算法
对于任意整数a，b，存在一对整数x，y，满足ax+by=gcd(a,b)。
证明：
当b=0时显然x=1，y=0是一组解。
若b>0，则,假设存在一对整数满足x，y满足
令就得到了
对欧几里得算法的递归过程应用数学归纳法，显然成立。
这里求出的是一组特解。
d = gcd(a,b)
对于更为一般的方程：ax+by=c,它有解当且仅当
他的通解为
乘法逆元
若b，m互质，并且b|a,则存在一个整数x，使得,称x为b的模m乘法逆元，记为
如果m是质数根据费马小定理,显然
是乘法逆元。
如何只满足b，m互质那么求解同余方程
线性同余方程的求解
可以变为另一种形式，求解这个方程的方法在前面已经讲解过了。最后我们需要得到一个在区间0到m的逆元
a
a
a
a
a
a
a
a
