一次同余方程
前面已经提到，剩余类可以看作一个特殊的“数”，剩余类环可以看作定义了剩余类加法和乘法的“数集”.类似于实数集情形，我们也可以在剩余类环中解方程或方程组。
例如，在模6的剩余类环中解方程[5][x]=3，这里[x]是模6的剩余类环中的未知剩余类，注意到
$$[5][x] = [3]\Leftrightarrow [5x]=[3]\Leftrightarrow 6|5x-3 \Leftrightarrow 5x\equiv 3(mod \ 6)$$
通常，我们把含有未知数的同余式叫做同余方程，方程$5x\equiv 3(mod \ 6)$是一类形式最简单的同余方程，叫做一次同余方程，形式为
$$ax\equiv b(mod \ n)$$
注意，同余方程的解并不是一个数，而是模n下的一个剩余类.
对于一次同余方程，我们关心下面几个问题：
- $ax\equiv b(mod \ n)$在什么情况下有解？
- 有几个解？
- 有解时如何求解？
$ax\equiv b(mod \ n) \ \Rightarrow ax+nt=b$，由裴蜀不等式知，$ax+nt=b$有解的充分必要条件是$(a, n) | b$，且解的个数为，.
因此，得到如下结论：
一次同余方程$ax\equiv b(mod \ n)$有解，则$(a,\ n) | b$，反过来，当$(a, \ m)|b$时，一次同余方程$ax\equiv b(mod \ n)$恰有$(a, \ n)$个解.
下面看一个一次同余方程的例子：
例1.解一次同余方程9x≡6(mod 15).
解：注意到(9, 15)=3，且3 | 6，故同余方程有3个解，原同余方程可简化为3x≡2(mod 5)，由于3x2≡1(mod 5)，故x≡2x2=4(mod 5)。所以同余方程的3个解分别为x≡4+0x5=4(mod 15)，x≡4+1x5=9(mod 15)，x≡4+2x5=14(mod 15).
大衍求一术
大衍求一术是解一次同余方程ax≡1(mod n)，其中a为正整数，a<n且(a, n)=1的一种算法程序.
用现代数学语言，算法步骤可表示为：
先规定$k_0 = 0,k_1=1,r_1=a$
对$n,a$做带余除法，$n=a q_2+r_2$，记$k_2 = k_0 - q_2 k_1$;
对$a,r_2$做带余除法，$a=r_2 q_3+r_3$，记$k_3 = k_1 - q_3 k_2$;
对$r_2,r_3$做带余除法，$r_2=r_3 q_4+r_4$，记$k_4 = k_2 - q_4 k_3$;
对$r_3,r_4$做带余除法，$r_3=r_2 q_5+r_5$，记$k_5 = k_3 - q_5 k_4$;
......
重复这种运算，直到余数$r_n=1$，那么最后所得的$k_n = k_{n-2} - q_n k_{n-1}$满足$ak_n \equiv 1 (mod \ n)$.于是$x \equiv a_k (mod \ n)$就是解。
下面考察大衍求一术的算法原理：
$r_1=a\equiv ak_1(mod \ n)\\r_2=n-r_1 q_2 \equiv a(-q_2 k_1)=ak_2(mod \ n)\\r_3=r_1-r_2 q_3 \equiv a(k_1 - q_3 k_2) = ak_3(mod \ n)\\r_4=r_2-r_3 q_4 \equiv a(k_2 - q_4 k_3) = ak_4(mod \ n)$
而$r_n=1$，故$ak_n\equiv 1(mod \ n)$.这就是大衍求一法的原理。
例2.解同余方程33x≡1(mod 74).
解：显然(33, 74)=1
由于74=33x2 + 8，33=8x4 + 1，故$q_2=2,q_3=4,r_3=1$，依次可计算出
$$k_2=-2 \times 1 = -2,k_3= 1-4 \times (-2)=9.$$
因此原方程的解为
$$x\equiv 9(mod \ 74)$$
个性签名：时间会解决一切