一些相关基本概念：群论、模运算、费马小定理、公约数、最大公约数、互质、逆元。
公约数：如果 $ d $ 是 $ a $ 的约数并且 $ d $ 也是 $ b $ 的约数，则 $ d $ 是 $ a $ 与 $ b $ 的公约数。
最大公约数：两个不同时为 $ 0 $ 的整数 $ a $ 与 $ b $ 的公约数中最大的数称为最大公约数，记作 $ gcd(a, b) $ 。
$ gcd $ 函数的基本性质：
$$ egin{align} gcd(a, b) &= gcd(b, a) \ gcd(a, b) &= gcd(-a, b) \ gcd(a, b) &= gcd(|a|, |b|) \ gcd(a, 0) &= |a| \ gcd(a, ka) &= |a| quad 对任意k in mathbb{Z} end{align} $$
推论：
$$ gcd(an, bn) = n gcd(a, b) $$
互质：当 $ gcd(a, b) = 1 $ 时，称 $ a $ 与 $ b $ 互质。
一些常用的判断条件：两个质数一定为互质数；一个质数与另一个不为其倍数的数为互质数；相邻的两个自然数是互质数；相邻的两个奇数是互质数。。。详细可见互质-百度百科。
逆元：
对每个 $ a in S $，存在唯一的元素 $ b in S $，称为a的逆元，满足 $ a oplus b = b oplus a = e $
其中$ e $为该群的单位元，乘法逆元的存在且唯一的条件是 $ gcd(a, b) = 1 $ 。
现在来考虑一个模线性方程：
$$ ax equiv b(mod n) $$
P.S.该方程可用在RSA公钥加密系统中。
几条很有用的定理及推论：
定理1
对任意正整数 $ a $ 和 $ n $ ，如果 $ d=gcd(a, n) $ ，则在 $ mathbb{Z}_n $ 中，
$ <a> = <d> = {0,d,2d, cdot cdot cdot ,(frac{n}{d} - 1)d} $
因此， $ |<a>| = frac{n}{d} $ ，其中 $ <a> $ 表示由 $ a $ 生成的 $ mathbb{Z}_n $ 的子群。
推论1 当且仅当 $ d|b $ 时，方程 $ ax equiv b(mod n) $ 对于未知量 $ x $ 有解，这里 $ d = gcd(a, n). $
推论2 方程 $ ax equiv b(mod n) $ 或对模 $ n $ 有 $ d $ 个不同的解，或者无解，这里 $ d = gcd(a, n). $
定理2
令 $ d = gcd(a, n) $ ，假设对某些整数 $ x' $ 和 $ y' $ ，有 $ ax' + ny'. $
如果 $ d|b $ ，则方程 $ ax equiv b (mod n) $ 有一个解的值为 $ x_0 $ ，这里 $ x_0 = x' frac{b}{d} mod n. $
定理3
假设方程 $ ax equiv b(mod n) $ 有解（即 $ d|b $ ， 这里 $ d = gcd(a, n) $ ），且 $ x_0 $ 是该方程的任意一个解。 $
因此，该方程对模 $ n $ 恰有 $ d $ 个不同的解，分别为 $ x_i = x_0 + i frac{n}{d} $ ，这里 $ i = 0,1, cdot cdot cdot ,d - 1. $
推论3 对于任意 $ n > 1 $，如果 $ gcd(a, n) = 1 $（即互质）， 则方程 $ ax equiv b(mod n) $ 对模 $ n $ 有唯一解。如果 $ b = 1 $ ，则要求的 $ x $ 是 $ a $ 对模 $ n $ 的乘法逆元。
推论4 对于任意 $ n > 1 $ ，如果 $ gcd(a, n) = 1 $ ， 那么方程 $ ax equiv 1(mod n) $ 对模 $ n $ 有唯一解；否则方程无解。在 $ a $ 和 $ n $ 互质时，可以用记号 $ a^{-1} mod n $ 来表示 $ a $ 对模 $ n $ 的乘法逆元。此时 $ gcd(a, n) = 1 = ax + ny $ 意味着 $ ax equiv 1(mod n). $
上面这两条推论我认为很重要，证明暂且略过不写了，因为证明还是看书最好。
费马小定理：
费马小定理实际上是欧拉函数的一个特殊情况，可以利用费马小定理求逆元：
$$ egin{aligned} a^{p - 1} &equiv 1 (mod p) \ a cdot a^{p - 2} &equiv 1 (mod p) end{aligned} $$
$$ ax equiv 1 (mod p) Rightarrow x = a^{p - 2} mod p $$
现在来考虑如下同余方程组：
$$ left{egin{aligned} x &= a_1 (mod m_1) \ x &= a_2 (mod m_2) \ & cdot cdot cdot \ x &= a_n (mod m_n) end{aligned} ight. $$
前面做的题中提到过，该方程组有解的条件是 mi 两两互质，并且通解形式为：
$$ x = kM + sum a_i t_i M_i , quad k in mathbb{Z} $$
而在模 M 的意义下才有唯一解，解的形式为：
$$ x = egin{pmatrix} sum a_i t_i M_i end{pmatrix} mod M $$
其中 $ M = prod m_i , M_i = frac{M}{m_i} $， $ t_i $ 为 $ M_i $ 的逆元， $ a_i $ 为余数。
最后，用之前做的例题来计算一下：
$ m = 3,5,7 $ ，将其写为方程组形式：
$$ left{egin{aligned} x &= a_1 (mod 3) \ x &= a_2 (mod 5) \ x &= a_3 (mod 7) end{aligned} ight. $$
于是 $ M = 105, M_1 = 35, M_2 = 21, M_3 = 15 $ 。下面求逆元，这里可以用费马小定理来求解，也可以通过扩展欧几里得算法来求解，或者还可以肉眼计算。
由 $ M_i t_i equiv 1 (mod m_i) $
费马小定理：
$$ egin{aligned} 35 t_1 &equiv 1 (mod 3) \ \ 35 cdot 35^1 &equiv 1 (mod 3) Rightarrow egin{aligned} t_1 &= 35^1 mod 3 \ &= (3 cdot 11 + 2) mod 3 \ &= 2 end{aligned} end{aligned} $$
$$ egin{aligned} 21 t_2 &equiv 1 (mod 5) \ \ 21 cdot 21^3 &equiv 1 (mod 5) Rightarrow egin{aligned} t_2 &= 21^3 mod 5 \ &= (21^2 cdot 21) mod 5 \ &= 21 mod 5 \ &= (4 cdot 5 + 1) mod 5 \ &= 1 end{aligned} end{aligned} $$
$$ egin{aligned} 15 t_3 &equiv 1 (mod 7) \ \ 15 cdot 15^5 &equiv 1 (mod 7) Rightarrow egin{aligned} t_3 &= 15^5 mod 7 \ &= (15^4 cdot 15) mod 7 \ &= 15 mod 7 \ &= (2 cdot 7 + 1) mod 7 \ &= 1 end{aligned} end{aligned} $$
肉眼观察法：
$$ egin{aligned} 35 t_1 &equiv 1 (mod 3) \ \ 35 cdot 2 &equiv 1 (mod 3) Rightarrow t_1 = 2 end{aligned} $$
$$ egin{aligned} 21 t_2 &equiv 1 (mod 5) \ \ 21 cdot 1 &equiv 1 (mod 5) Rightarrow t_2 = 1 end{aligned} $$
$$ egin{aligned} 15 t_3 &equiv 1 (mod 7) \ \ 15 cdot 1 &equiv 1 (mod 7) Rightarrow t_3 = 1 end{aligned} $$
两种方法都求出了t1 = 2, t2 = 1, t3 = 1，又
$$ x = egin{pmatrix} sum a_i t_i M_i end{pmatrix} mod M $$
且 M = 105, M1 = 35, M2 = 21, M3 = 15。于是可得到公式 x = [a·(35×2) + b·21 + c·15]%105。
主要参考：
1.https://baike.baidu.com/item/%E4%BA%92%E8%B4%A8/577412?fr=aladdin
2.https://baike.baidu.com/item/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86/4776158?fr=aladdin
3.https://baike.baidu.com/item/%E4%B9%98%E6%B3%95%E9%80%86%E5%85%83/5831857?fr=aladdin
4.https://baike.baidu.com/item/%E5%AD%99%E5%AD%90%E5%AE%9A%E7%90%86/2841597?fr=aladdin
5.https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0
6.算法导论
其他参考：
7.https://www.cnblogs.com/dupengcheng/p/5487362.html