一、首先复习一下模运算对于模运算，有以下等式成立：

二、求解线性同余方程：

首先考虑实数状况下求解方程ax = b因为a存在倒数a^-1，所以在方程两边同时乘上a^-1可以解出x = b * a^-1

现茬对于线性同余方程ax ≡ b (a mod bm)如果有满足ay ≡ 1 (a mod bm) 这样的和实数情况下a的倒数一样的数y存在，就能很快利用y = a^-1代入到原方程中来求解线性同余方程我們把这样的数y叫做a的逆元，求出了逆元之后就有x = a^-1·ax =

逆元的求法&逆元和线性同余方程解的关系：

现在我们要如何求出这个线性同余方程的逆元呢？对于方程ax ≡ 1 (a mod bm)其实等价于：存在整数k使得ax = 1 + mk，稍加变形之后就变成了ax - mk =

• [可以得出结论：当线性同余方程不存在逆元并且b%gcd(a,m)!=0时必定无解]

• [存茬逆元的情况下一定有多个解]

也可以用费马小定理来求出逆元：
费马小定理(Fermat’s little theorem)是数论中的一个重要定理，在1636年提出其内容为： 假如p是質数，且gcd(a,p)=1那么 a^(p-1) ≡ 1（a mod bp），例如：假如a是整数p是质数，则a,p显然互质(即两者只有一个公约数1)那么我们可以得到费马小定理的一个特例，即當p为质数时候

当p是合数的时候，费马小定理就不适用了这时可以用欧拉函数和欧拉定理来求值

三、求解线性同余方程组

当线性同余方程组满足一定条件的情况下我们可以用中国剩余定理来求解问题。