求解同余方程

同余方程求解方法

同余方程的一般形式为：

[ ax \equiv b \pmod{m} ]

其中，(a, b, m) 是已知整数，(x) 是未知数。我们需要找到所有满足该方程的整数 (x)。

求解步骤

1. 检查是否有解：

   • 计算 (d = \gcd(a, m))。
   • 如果 (d \nmid b)（即 (b) 不能被 (d) 整除），则方程无解。
   • 否则，方程有 (d) 个解。

2. 化简方程：

   • 如果 (d > 1)，将方程两边除以 (d)：

     [ \frac{a}{d} x \equiv \frac{b}{d} \pmod{\frac{m}{d}} ]

   • 此时 (\gcd\left(\frac{a}{d}, \frac{m}{d}\right) = 1)，可以求逆元。

3. 求逆元：

   • 我们需要找到一个整数 (y)，使得：

     [ \frac{a}{d} \cdot y \equiv 1 \pmod{\frac{m}{d}} ]

   • 这个 (y) 称为 (\frac{a}{d}) 在模 (\frac{m}{d}) 下的逆元，可以用扩展欧几里得算法求解。

4. 求特解：

   • 方程的解为：

     [ x_0 \equiv y \cdot \frac{b}{d} \pmod{\frac{m}{d}} ]

5. 求通解：

   • 所有解的形式为：

     [ x \equiv x_0 + k \cdot \frac{m}{d} \pmod{m}, \quad k = 0, 1, \dots, d-1 ]

C++ 代码实现

```cpp #include #include using namespace std;

// 扩展欧几里得算法，返回 gcd(a, b)，并找到 x, y 使得 ax + by = gcd(a, b) int extended_gcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1; y = 0; return a; } int x1, y1; int gcd = extended_gcd(b, a % b, x1, y1); x = y1; y = x1 - (a / b) * y1; return gcd; }

// 求解同余方程 a x ≡ b (mod m)，返回所有解（模 m 意义下） vector solve_congruence(int a, int b, int m) { vector solutions; int x, y; int d = extended_gcd(a, m, x, y); // 计算 gcd(a, m) 和 x, y

if (b % d != 0) {
    return solutions; // 无解，返回空 vector
}

int a1 = a / d, b1 = b / d, m1 = m / d;
// 求 a1 在模 m1 下的逆元
extended_gcd(a1, m1, x, y);
int inv = (x % m1 + m1) % m1; // 最小正整数解

int x0 = (inv * b1) % m1; // 特解
for (int k = 0; k < d; k++) {
    solutions.push_back((x0 + k * m1) % m);
}

return solutions; }

int main() { int a, b, m; cout « “输入 a, b, m（求解 a x ≡ b mod m）：”; cin » a » b » m;

vector<int> sols = solve_congruence(a, b, m);
if (sols.empty()) {
    cout << "无解" << endl;
} else {
    cout << "解为（模 " << m << " 意义下）：";
    for (int x : sols) {
        cout << x << " ";
    }
    cout << endl;
}

return 0; }