线性同余方程与中国剩余定理学习笔记

线性同余方程介绍

形如 ax \equiv c \pmod b 的方程被称为 线性同余方程(Congruence Equation)。

求解方法

根据以下两个定理，我们可以求出同余方程 ax \equiv c \pmod b 的解。

Theorem 1 states that the equations ax + by = c and ax \equiv c \pmod{b} are equivalent, and they possess integer solutions if and only if the greatest common divisor of a and b, denoted as \gcd(a, b), divides c.

按照定理 1，在讨论方程的形式时

定理 2 ：当且仅当 \gcd(a,b)=1 时，在方程 ax + by = c 中存在一个特解 (x_0, y_0) 。基于此特解的所有其他整数解均可表示为以下形式：对于某个整数参数 t, x = x_0 + bt, 而 y = y_0 - at. 这种通式适用于所有整数值 t.

由定理 2 可得方程的所有解。然而，在实际问题中我们常被要求求取一个最小整数解即一个特解 其中 t = \d