1. 概念#

当我们需要解决形如 $ax \equiv b \pmod{m}$ 的问题时，其中 $a, b, m$ 为已知整数，$x$ 为未知整数，这个问题就被称为线性同余方程（linear congruence equation）。其中 $\equiv$ 符号表示模同余关系，即两个数在模 $m$ 意义下相等。

线性同余方程在密码学、计算机科学有着广泛的应用，例如在模运算中的加密算法和概率论中的随机数生成。解决线性同余方程可以通过求出 $x$ 的所有可能值，使得模运算意义下 $ax$ 与 $b$ 相等。

2. 求解#

要解线性同余方程，首先要判断是否有解。如果有解，那么必须满足b≡0(mod d)，其中d是a和m的最大公约数。如果没有解，那么方程无解。

如果有解，那么可以用欧几里得算法或欧拉方法来求出一个特解 $x_0<\frac{m}{d}$ 。然后所有的解都可以表示为 $x=x_0+k(\frac{m}{d})$ ，其中 $k$ 是任意整数。如果 $d=1$ ，那么只有一个解 $x_0<m$ 。

接下来我们介绍一个定理¹， 这个定理给出了一个关于线性同余方程的解的等价条件：

$n$ 和 $a$ 是已知的正整数，$d$ 是 $a$ 和 $n$ 的最大公约数，$t$ 是模 $\frac{n}{d}$ 意义下 $\frac{a}{d}$ 的逆元 (inverse) ，$x$ 是待求的未知数。

如果 $d\ |\ b$，则 $ax \equiv b \pmod{n} \longleftrightarrow x \equiv \frac{b}{d}t \pmod{\frac{n}{d}}$ 。

1. 概念#

线性同余方程组（System of Linear Congruences）指的是多个形如 $ax \equiv b \pmod{m}$ 的线性同余方程组成的集合。其中，$a, b, m$ 是已知的整数，$x$ 是未知的整数。

2. 求解#

求解线性同余方程组可以使用中国剩余定理，所以首先我们应该先了解什么是中国剩余定理。

中国剩余定理（Chinese Remainder Theorem，CRT）是一种用于解决一组同余方程的方法，其中每个方程的模数两两互质。该定理可以有效地解决在计算机科学、密码学、数字信号处理、编码理论和其它领域中的一些问题。

具体来说，中国剩余定理指出：如果 $m_1, m_2, \ldots, m_k$ 是一组两两互质的正整数，那么对于任意整数 $a_1, a_2, \ldots, a_k$ ，则下列同余方程组有唯一的解 $x \pmod M$，其中 $M = m_1 m_2 \cdots m_k$： $x \equiv a_1 \pmod{m_1}$ $x \equiv a_2 \pmod{m_2}$ $\vdots$ $\ x \equiv a_k \pmod{m_k}$ 即对于任意 $i\in[1,n]$，都有 $x\equiv a_i\pmod{m_i}$，且对于任意 $j\in[1,n],j\neq i$，都有 $x\not\equiv a_j\pmod{m_j}$。

而其中的解 $x = \sum_{i=1}^n a_i M_i (M_i)^{-1}$

那么接下来我们使用它来解一个同余方程组：

具体来说，设给定的线性同余方程组为：

$a_1 x \equiv b_1 \pmod{m_1}$ $a_2 x \equiv b_2 \pmod{m_2}$ $\vdots$ $a_n x \equiv b_n \pmod{m_n}$

其中，$n$ 表示方程组中方程的个数。为了使用中国剩余定理求解这个方程组，我们需要先求出方程组中每个方程对应的模数 $M_i$：

$M_i = \prod_{j=1,j\neq i}^n m_j$

然后，对于每个方程 $i$，求出 $M_i$ 在模 $m_i$ 意义下的逆元 $t_i$：

$t_i \equiv (M_i)^{-1} \pmod{m_i}$

最后，我们可以计算方程组的一个特解 $x_0$：

$x_0 = \sum_{i=1}^n b_i t_i M_i$

得到 $x_0$ 后，方程组的通解为 $x = x_0 + kM$，其中 $k \in \mathbb{Z}$。这个通解表示了所有满足方程组的条件的 $x$ 的集合。

3. 中国剩余定理映射#

中国剩余定理映射（CRT Map）是指将给定的同余方程组通过中国剩余定理得到一个从整数集到模数之积的映射。

具体地，设 $n_1, n_2, \ldots, n_k$ 是一组互质的正整数，$a_1, a_2, \ldots, a_k$ 是 $k$ 个整数，则中国剩余定理映射

$\varphi: \mathbb{Z} \to {\mathbb{Z}}_{n_1} \times {\mathbb{Z}}_{n_2} \times \cdots \times {\mathbb{Z}}_{n_k}$

定义为:

$\varphi(x) = (x \bmod n_1, x \bmod n_2, \ldots, x \bmod n_k)$

其中 $\bmod$ 表示取模运算，$\mathbb{Z}_{n_i}$ 表示模 $n_i$ 的剩余类环 (ring) 。根据中国剩余定理，如果 $n_1, n_2, \ldots, n_k$ 互质，则 $\varphi$ 是一个双射（即一一映射）。

根据中国剩余定理映射，我们可以将一个同余方程组的解转化为在模数之积下的唯一解。这对于计算同余方程组的解非常有用，因为在模数之积下计算通常比在单个模数下计算更容易。

1. 概念#

欧拉函数（Euler’s Phi Function）通常用符号 $\varphi(n)$ 表示。对于正整数 $n$，欧拉函数定义为小于等于 $n$ 的正整数中与 $n$ 互质的数的个数。

换言之，如果 $n$ 是正整数，那么 $\varphi(n)$ 等于小于等于 $n$ 的正整数中与 $n$ 互质的数的个数。

例如，如果 $n = 6$，则小于等于 $6$ 且与 $6$ 互质的正整数是 $1$，$5$，所以 $\varphi(6) = 2$。

欧拉函数在数论和密码学等领域有着广泛的应用，它是许多数论定理的关键部分，例如欧拉定理和欧拉-费马定理等。

2. 相关定理#

1. 欧拉定理（Euler’s Theorem）

   如果 $a$ 和 $n$ 是正整数，且它们互质，那么 $a^{\varphi(n)} \equiv 1 \pmod{n}$。这个定理是在模 $n$ 意义下的。

2. 欧拉函数乘性定理

   $n_1, \ldots, n_k$ 是两两互质的正整数，$n = n_1 \cdot n_2 \cdots n_k$，则有 $\varphi(n) = \varphi(n_1) \cdot \varphi(n_2) \cdots \varphi(n_k)$

3. 前两个定理的引申定理

   当 $n = ab$ 且 $a$ 和 $b$ 互质时，有 $\varphi(n) = \varphi(ab) = \varphi(a) \cdot \varphi(b) = (a-1) \cdot (b-1)$。因此，我们可以得到 $\forall a,b \in \mathbb{Z}^+$，如果 $a$ 和 $b$ 互质，那么有 $a^{(b-1)(a-1)} \equiv 1 \pmod {ab}$，即 $\varphi(ab) = (a-1) \times (b-1)$