一次同余方程

像一般的等式可以引入未知数以及方程的概念那样，我们对同余式也引入方程的概念。

同余方程

有一确定整数$m$，设有关于$x$的函数$f: \Z \mapsto \Z$，那么$f(x) \equiv 0 \pmod{m}$就称作关于$x$的一元同余方程。未知数的个数称为元数，元数多于$1$个的方程叫做不定方程。

若函数$f(x)$是一次的，就称这个方程是（一元）一次同余方程，它是一类最简单的同余方程。它总有形式$ax \equiv b \pmod{m}$，未特别说明时我们总假设$a\ne0$的非平凡情况。

一次同余方程的解

定理：同余方程$ax \equiv b \pmod{m}$有解的充要条件是$(a, m) \mid b$。

由此，当$(a, m) = 1$时，该方程一定可解，我们先解这一种特殊情况：
对于$ax \equiv b \pmod{m}$，我们可以找到整数$k$，使得$a \mid b+km$，于是$a x \equiv b + k m \pmod{m}$
进一步约去$a$：$x \equiv \dfrac{b+km}{a} \pmod{m}$。 实际上，这一过程可以逐步进行，$a$是多个素数的乘积时可以一个数一个数消。
对于$(a, m) \ne 1$，方程两边约去$(a,m)$：$\dfrac{a}{(a, m)}x \equiv \dfrac{b}{(a, m)} \pmod{\dfrac{m}{(a, m)}}$，这样就化为了上面互素的情况。

定理：一次同余方程$ax \equiv b \pmod{m}$可解时解在模$m$同余意义下解数有$(a. m)$个。

我们解出一次同余方程后，其结果就直接写作模$m$同余类形式：$x \equiv c \pmod{m}$。

示例

例如，解同余方程$42 x \equiv 12 \pmod{33}.$
由于$(42, 33) = 3 \mid 12$，故此方程有解，同余式两边约去$3$，即有

$$\begin{align} 14 x & \equiv 4 \pmod{11} \\ 7 x & \equiv 2 \pmod{11} \\ 7 x & \equiv 2 + 3 \times 11 = 35 \pmod{11} \\ x & \equiv 5 \pmod{11} \\ x & \equiv 5, 16, 27 \pmod{33}. \end{align}$$

解$14 x \equiv 4 \pmod{11}$的过程还可简写为 $x \equiv \dfrac{4}{14} = \dfrac{2}{7} \equiv \dfrac{2 + 3 \times 11}{7} = \dfrac{35}{7} = 5 \pmod{11}.$
每次对分子做加减$m$的倍数的操作，约分时保证约去的因数要与$m$互素，最后将分数化为整数时得到结果。

高次同余方程

上面我们讨论了一次同余方程的解的问题，但是如果整系数多项式$f(x)$的次数变高，一般来说求解方程$f(x) \equiv 0 \pmod{m}$并不容易，正因为此，高次同余方程在密码通讯中有广泛应用。

Lagrange 定理：设$p$为素数，$a_i \in \Z, 1 \leqslant i \leqslant n$且$p \nmid a_n$，那么关于$x$的同余方程

$$a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \equiv 0 \pmod{m}$$

至多有$n$个解。 这个定理给出了确定整系数多项式$f(x)$的依据。

在引入原根和指数的概念后，我们会尝试解一些简单的高次方程以及指数方程，在介绍二次剩余的概念后我们会对解二次同余方程做一个完整具体的刻画。

同余方程组

将多个同余方程联立起来

$$\begin{cases} f_1 (x) \equiv 0 \pmod{m_1} \\ f_2 (x) \equiv 0 \pmod{m_2} \\ \cdots \\ f_n (x) \equiv 0 \pmod{m_n} \end{cases}$$

它就是把每个同余方程的解取交集。我们知道，对于一个非常大的数$m$，求解同余方程$f(x) \equiv 0 \pmod{m}$一般是件困难的事，但是如果能将它化成模数较小的几个同余方程来求解，是比较简单的，只要我们最后在取交集即可。下一节我们将会给出取交集的方法——中国剩余定理。

上下节

• 上一节：同余类的代数结构
• 下一节：中国剩余定理