首先，这是个方程，所以x是变量，剩下的就是在确定a,b,m的值之后，确定x的可选值有哪些。解题思路是这样的： $$ gcd(a,m)=1，且 a,m \in N，则必然存在一个数：\overline{a},称为a模m的逆，能够使得 a \cdot \overline{a} \equiv 1 (mod\ m)。 $$ 这里先举一个现实的例子： $$ 假设 a=3,m=7，则 -2 \cdot 3 \equiv 1 (mod\ 7) $$ 在上面的基础之上，再来看下面的推论，让我们先假定这个逆一定存在（接下来会证明这个值一定存在）。这个值如何帮助我们解决最开始的问题呢？ $$ \because ax \equiv b\ (mod\ m) \ a \cdot \overline{a} \cdot x \equiv b \cdot \overline{a}\ (mod\ m) \ a \cdot \overline{a} \cdot x\ mod\ m = ((a \cdot \overline{a}\ mod\ m) \times (x\ mod\ m))\ mod\ m \ a \cdot \overline{a} \equiv 1\ (mod\ m) \ x\ mod\ m = b \cdot \overline{a} \mod m \ \therefore x \equiv b \cdot \overline{a}(\mod m) $$ 这样就能获得了x的表达式。
那么问题就来了：
- a模m的逆一定存在吗？
- 如果存在，如何计算呢？
先是证明这个值一定存在。 $$ \because gcd(a,m)=1\ \therefore \exists s,t，as+tm=1 \ \therefore (as+tm) \equiv 1 (mod\ m) \ (as+tm)(mod\ m)=((as\ mod\ m)+(tm\ mod\ m))\ mod\ m \ \because tm\ mod\ m=0 \ \therefore (as)\equiv 1 (mod\ m)，这里s就是作为a的逆存在，因为s一定存在，所以 \overline{a} 一定存在 $$ 接着就是这个值如何求，其实就是求贝祖系数
比如这里的 $$ 线性同余方程：3x \equiv 4\ (\mod 7) 的解是什么？ $$ 解题过程： $$ \because 5 \cdot 3 - 2 \cdot 7=1 \ \therefore x \equiv 5 \cdot 4 (\mod 7) \equiv 6 (\mod 7) $$ 当然，答案不止一个，因为 $$ -8 \equiv 6(\mod 7)，所以上面也可以写成 x \equiv -8 (\mod 7) $$
上面介绍了一个线性方程组的解，但是如果有多个线性方程组的解需要整合时，该怎么处理呢？
比如： $$ x \equiv 2(\mod 3)\ x \equiv 3(\mod 5)\ x \equiv 2(\mod 7) $$ 问，这个时候如何求解？
暂时先不管上面的具体问题，我们把上面的方程组类比成下面的形式： $$ x \equiv {a}{1}(\mod {m}{1}) \ x \equiv {a}{2}(\mod {m}{2}) \ \vdots \ x \equiv {a}{n}(\mod {m}{n}) \ 且 gcd({m}{i},{m}{j})=1 $$ 解： $$ 令 {M}{k}=\frac{ {m}{1} \times {m}{1} \cdots {m}{n} }{ {m}{k} }，令{y}{k}为\ {y}{k} \equiv {M}{k} (\mod {m}{k})，即 {y}{k}为 {M}{k}模{m}{k}的逆 \ 则 x = {a}{1}{M}{1}{y}{1}+{a}{2}{M}{2}{y}{2} \cdots {a}{n}{M}{n}{y}{n} $$ 首先说明为什么上面的这种解法有效： $$ \because （{a}{1}{M}{1}{y}{1}+{a}{2}{M}{2}{y}{2} \cdots {a}{n}{M}{n}{y}{n}）\ mod\ {m}{j}= (({a}{1}{M}{1}{y}{1} \mod {m}{j})+({a}{2}{M}{2}{y}{2} \mod {m}{j}) \cdots ({a}{n}{M}{n}{y}{n} \mod {m}{j}))(mod\ {m}{j}) \ 当 n \neq j时，{M}{n} \equiv 0 (\mod {m}{j})，因为{M}{n}中有{m}{j}，所以上面可以化简为 \ {a}{j}{M}{j}{y}{j} \mod {m}{j} \ 同时，(({a}{j} \mod {m}{j})({M}{j}{y}{j} \mod {m}{j}))(mod\ {m}{j}) 可以化简为 \ {a}{j} \mod {m}{j} \ \therefore x={a}{j} \mod {m}{j} $$ 然后上面可以得到一个x的值，但是我们看上面，我们可以得出，其实x可以写成 $$ 令M=lcm({m}{1},{m}{2},{m}{3} \cdots {m}{n})，d=x mod M，则 \ x=d\ (mod\ M) $$
具体例子见书上248页的例5.
这一章简单来说就是如何通过减少值来加快计算速度，比如让你计算1+3的速度总是快过10000+30000。说具体的计算方法前，书上的原话
“ $$ m={m}{1} \times {m}{2} \cdots {m}{n}，且 gcd({m}{i},{m}{j})=1，\ 则一个0<=a<=m的整数是否可以唯一表示成 (a\mod {m}{1},a\mod {m}{2},a\mod {m}{3}, \cdots a\mod {m}_{n}) $$ ”
这样表示肯定没有问题的，因为在上面的中国剩余定理中我们证明了这样的数字是肯定存在的，至于在0~m之间是否唯一的问题了，在上面的最后我们也证明了这样的x的值是唯一的。
或者换个角度思考这个问题。
这样的数字差一点都不行：
例子：
将 123684和413456的加法转换成100内的加减
然后12368+413456可以归纳为 $$ ((33+32)\mod 99,(98+92)\mod 98,(97+42)\mod 97,(95+16)\mod 95) \ 即\ (65,2,51,10) $$ 上面计算的原理见这里的同余种的公式
然后如果要原始的值，需要计算 $$ x \equiv 65 (mod\ 99) \ x \equiv 2 (mod\ 98) \ x \equiv 51 (mod\ 97) \ x \equiv 10 (mod\ 95) $$ 这样的方式，可以加快计算速度，只有需要原来的值时，才需要进行100之外的计算。
“ $$ 如果p为素数，且a \in N，a不能被p整除，则\ {a}^{p-1} \equiv 1 (mod\ p)，并且 \ a^p \equiv a (mod\ p) $$ ”
证明：
二项式展示公式 $$ a^p=(1+(a-1))^p= \ \sum^{p}{k=0} {C}^{k}{p} {1}^{(p-k)} {(a-1)}^{k},{C}^{k}{p}=\frac{p!}{(p-k)!k!}=\frac{p \cdot (p-1) \cdots (p-k+1)}{k!} \ 其中因为 {C}^{k}{p} \in N，所以 k!|(p \cdot (p-1) \cdots (p-k+1))，同时因为0<k<p，所以 gcd(k!,p)=1，即\ k!|(p-1)\cdots (p-k+1)，即\ p|{C}^{k}{p}，然后我们将上面二项式展开公式进行 mod 2的处理，化简为:\ a^p \mod p =(\sum^{p}{k=0} {C}^{k}_{p} {1}^{(p-k)}) \mod p \ a^p \mod p \equiv 1+(a-1))^p (mod\ m) \ 上面我们将 a^p 拆分成 (1+(a-1))^p，那么是不是同样可以拆分成 \ (2+(a-2))^p\ (3+(a-3))^p\ \vdots (a+(a-a))^p\ 最终递归得出 \ a^p \equiv a (mod\ p) $$ 参考B站视频