今天写密码学实验报告放射密码一题的时候，看到线性同余式\(c = ma+ b \mod n\)，感觉到自己对于同余方程的掌握一点也不牢固，所以又拿出来《数论概论》重新回顾了一下，后续会写一个数论专题，本章主要讨论线性同余式定理。

同余式

对于同余式我们已经很熟悉了，如果\(m\)整除\(a-b\)我们就说\(a\)与\(b\)模\(m\)同余。

记为

\[a \equiv b \mod m \]

同余式满足一些我们熟悉的通常的等式的性质，例如：\(a_1 \equiv b_1 \mod m\)，且，\(a_2 \equiv b_2 \mod m\)，那么我们可以得到\(a_1 \pm b_1 \equiv a_2 \pm b_2 \mod m\)（类似等式两边相加），以及\(a_1 a_2 \equiv b_1 b_2 \mod m\)（类似等式两边相乘），但是需要指出的是，用数除同余式并不总是可能的，这个问题详见拓展性质 2。

数\(m\)叫做同余式的模，我们也很容易得知，每个整数必然与 0~m-1 的一个数模\(m\)同余。

一些同余式的拓展性质

1. 同余式 \(ab \equiv (a \mod m)(b \mod m) \mod m\) 恒成立。

   证明：已知\(a \equiv (a \mod m) \mod m\)，\(b \equiv (b \mod m) \mod m\)，所以由相乘的性质德政。

2. 当满足\(\gcd (c,m) = 1\)，则同余式\(a c \equiv b c \mod m\)可从同余式两边消去\(c\)。

   证明：对于同余式\(a c \equiv b c \mod m\)成立，则有等式\(ac-bc = km, k \in Z\)，即\((a-b)c = km\)成立，我们容易观察得等式左边为\(c\)的倍数，所以等式右侧也应为\(c\)的倍数，而我们又知道\(\gcd (c,m) = 1\)，也即\(c \nmid m\)，所以\(c \mid k\)，不妨设\(k'c = k\)，所以我们可以得到\(a - b = k' m\)，故有，\(a \equiv b \mod m\)，得证。

同余方程

我们的任务是解同余式\(ax \equiv c \mod m\)，包括判断其有没有解，有几个解，各个解是什么。

当然，可以应用同余式的性质解决一些简单的带未知数的同余式，如\(4x \equiv 3 \mod 19\)，我们两边乘以\(5\)得出，\(20x \equiv 15 \mod 19\)，应用性质 1，可得到\(x \equiv 15 \mod 19\)，代入可检测我们的答案。事实上，该式也只有这一个解。

我们接下来回归到一般形的求解过程中。对于同余式：

\[ax \equiv c \mod m\]

我们需要求整数\(x\)使得\(m \mid ax-c\)，如果可以求得整数\(y\)使得\(ax-c = my\)，则数\(m\) 就整除数\(ax-c\)，移项后我们看到\(ax \equiv c \mod m\)有解当且仅当线性方程\(ax-my =c\)有解（等价推导），这个问题很像线性方程和最大公因数里讨论的问题（拓展欧几里得算法）。

设\(g = \gcd(a,m)\)，我们观察到，形如\(ax-my\)的每个数都是\(g\)的倍数。因此：

1. \(g \nmid c\)，则\(ax-my = c\)无解，从而由等价性，原同余方程也没有解。

2. \(g \mid c\)，则由线性方程定理我们可以知道

   \[au+mv = g\]

   总是有解的，不妨假设通过拓展欧几里得算法求得\(u = u_0\)，\(v = v_0\)，则有：

   \[a u_0 + m v_0 = g\]

   我们可以与原同余方程等价的线性方程的一个解。

   \[a \frac{c u_0}{g} + m \frac{c v_0}{g} = c\]

   即我们得到了\(x_0 \equiv \frac{c u_0}{g} \mod m\)式原同余方程的一个解，那其他解呢？假设\(x_1\)是同余式的其他解，则\(a x_1 \equiv a x_0 \mod m\)，那么\(m \mid a x_1 - a x_0\)，这蕴含：

   \[\frac{m}{g} \mid \frac{a(x_1 -x_0)}{g}\]

   我们已知\(\frac{m}{g}\)与\(\frac{a}{g}\)没有大于 1 的公因数（除以最大公因数），从而\(\frac{m}{g} \mid x_1 - x_0\)。

   \[x_1 = x_0 + k \bullet \frac{m}{g}\]

   但是相差为\(m\)的倍数的两个解在模数意义下被认为是相同的，所以原同余方程恰好有\(g\)个不同的解，即

   \[x_i = x_0 + i \bullet \frac{m}{g}, i = 0,1,2 \cdots , g-1\]

   子证明，假设有\(g+1\)个不同解，则由鸽笼定理知，必存在\(i_p \equiv i_q \mod g\)，则\(x_p - x_q = (p-q) \bullet \frac{m}{g} = k'g \bullet \frac{m}{g} = k'm\)，那么这两个解是相同的，矛盾。

这就完成了对同余式\(ax \equiv c \mod m\)的分析，结果为如下定理

线性同余定理

设\(a,c,m \in Z\),\(m \geq 1\)，且设\(g = \gcd (a,m)\).

(a)如果\(g \nmid c\)，则同余式\(ax \equiv c \mod m\)没有解。

(b)如果\(g \mid c\)，则同余式子\(ax \equiv c \mod m\)恰好有\(g\)个不同的解，先利用拓展欧几里得算法求得线性方程

\[au+mv = g\]

的一个解\((u_0,v_0)\)，则\(x_0 = \frac{c u_0}{g}\)是同余方程的一个解，完全集由

\[x = x_0 + k \bullet \frac{m}{g} \mod m , k = 0,1,2 \cdots , g-1\]

重要注记

线性同余式定理的最重要的情形是\(\gcd (a,m) = 1\)，在这种情形下，同余式恰好有一个解。我们甚至可以把解写成分数

\[x \equiv \frac{c}{a} \mod m\]

模\(p\)多项式根定理

设\(p\)为素数，\(f(x) = a_0 x^{d} + a_1 x^{d-1} +\cdots +a_d\)是次数为\(d ≥ 1\)的整系数多项式，且\(p\)不整除\(a_0\)，则同余式\(f(x) \equiv 0 \mod p\)最多有\(d\)个模\(p\)不同余的解。

反证法：

假设：存在一个首项系数不被\(p\)整除的整系数多项式\(F(x)\)，使得同余式\(F(x) \equiv 0 \mod p\)模\(p\)不同余的根的个数大于\(F(x)\)的次数。

在所有这样的多项式中选择一个次数最低的\(F(x)\)，为 d 次，则\(r_1,r_2,\cdots,r_{d+1}\)是同余式的\(d+1\)个模\(p\)不同余的解。对于任意值\(x\)，\(r\)，\(F(x)-F(r)\)都是可约的（利用\(a^t - b^t = (a-b)(a^{t-1}+a^{t-2}b+ \cdots + b^{t-1})\)），我们可以得到，\(F(x) = F(r)+(x - r)G(x)\)，而\(G(x)\)的次数为\(d-1\)次，我们已经假设原\(F(x) \equiv 0\)有\(r+1\)个互不同余的解，令\(x=r_1\)，\(r\)取剩下其中任意一个\(r_k\)，由于\(p\)为素数，我们可以得到\(G(r_k) \equiv 0 \mod p\)，我们发现\(G(x)\)也是一个符合要求的多项式，这就与我们的假设条件相互矛盾，\(F(x)\)不是最小次的。得证。