线性同余式定理

作者: 摇摆苏丹 | 来源:发表于2021-01-25 02:27 被阅读0次

线性同余式定理
中国剩余定理
近世代数理论基础7：同余式·中国剩余定理
模p多项式根定理
产品经理数学课（3）
2020-01-22（学习笔记附录）
信息安全数学基础3——同余式
2019-04-22
矩阵代数（三）- 可逆矩阵的特征
线性相关的本质

引言

当同余式中存在未知数的时候，我们会关心未知数的取值，这可以与解方程类比。其中最简单的一种带未知数的同余式就是线性同余式。如 $ax \equiv c \ (mod \ m)$ ，其中 $x$ 是未知数，其余的 $a,c,m$ 都是常数。求解未知数 $x$ 的过程就可以被表述为线性同余式定理。

表述

设 $a,c,m \in \mathbb{Z}$ ，且 $m \geq 1$ ， $g = gcd(a,m)$ ，对于同余式 $ax \equiv c \ (mod \ m)$ ，如果 $g \nmid c$ ，则同余式没有解。否则求线性方程 $au+mv=g$ 的一个特解 $(u_0,v_0)$ ，此时 $x_0 = c \frac{u_0}{g}$ 是同余式的解，所有解可以用 $x_0 + k \frac{m}{g},k \in \mathbb{Z}$ 表示，共 $g$ 个不同的解。

证明

显然， $ax \equiv c \ (mod \ m) \iff m \mid ax-c \iff ax-my=c$ 。由裴蜀定理，可知当 $g = gcd(a,m) \mid c$ 的时候，同余式 $ax-my=c$ 有解。使用欧几里得算法求出 $au-mv=g$ 的一个特解为 $(u_0,v_0)$ ，那么 $ax-my=c$ 的一个对应的特解就是 $(x_0,y_0)=(u_0 \frac{c}{g},v_0 \frac{c}{g})$ 。最后由线性方程定理，得到该同余式的所有解为 $(x_0-k \frac{m}{g},y_0-k\frac{a}{g})$ ， $k$ 的正负号无关紧要，又只关心 $x$ ，因此所有解为 $x_0 + k \frac{m}{g}$ 。

例子

求同余式 $893x \equiv 266 \ (mod \ 2432)$ 。
首先， $gcd(893,2432)=19 \mid 266$ ，说明原同余式有解，且有19个解。然后解得方程 $893u-2423v=19$ 的一个特解为 $(u_0,v_0)=(79,29)$ ，对应方程 $893x-2423y=266$ 的一个特解为 $(x_0,y_0)=(u_0 \frac{266}{19},v_0 \frac{266}{19})=(1106,406)$ ，取 $x_0=1106$ ，其余解为 $x_0 + k \frac{2432}{19}=1106+128k$ 。