编程实现计算同余式ax≡b(mod m)的解

代码如下：

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def extended_euclid(a, b):
    if b == 0:
        return 1, 0, a
    x, y, gcd = extended_euclid(b, a % b)
    return y, x - (a // b) * y, gcd

def solve_congruence(a, b, m):
    if gcd(a, m) != 1:
        print("No solution exists")
        return
    x, y, gcd = extended_euclid(a, m)
    x = (x % m + m) % m
    return (x * b) % m

其中，`gcd(a, b)`是求a和b的最大公约数的函数，`extended_euclid(a, b)`是求a和b的扩展欧几里得算法的函数，`solve_congruence(a, b, m)`是计算同余式ax≡b(mod m)的解的函数。

使用时，调用`solve_congruence(a, b, m)`函数即可得到同余式的解。例如：

print(solve_congruence(7, 3, 11))  # 输出8

这表示7x≡3(mod 11)，解为x=8。

相关问题

编程实现计算同余式ax≡b（mod m的解c语言）

以下是C语言代码实现：

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

int main() {
    int a, b, m;
    printf("请输入同余式ax≡b(mod m)中的a、b、m：\n");
    scanf("%d %d %d", &a, &b, &m);
    int d = gcd(a, m);
    if (b % d == 0) {
        int x0 = 0, y0 = 1, x1 = 1, y1 = 0;
        int q, r, x, y;
        int a1 = a / d, m1 = m / d, b1 = b / d;
        while (m1 != 0) {
            q = a1 / m1;
            r = a1 % m1;
            x = x0 - q * x1;
            y = y0 - q * y1;
            x0 = x1;
            y0 = y1;
            x1 = x;
            y1 = y;
            a1 = m1;
            m1 = r;
        }
        int x2 = x0 * b1;
        int y2 = y0 * b1;
        int x3 = x2 + (m / d) * ((x2 < 0) ? (-x2 / (m / d) + 1) : (x2 / (m / d)));
        printf("同余式ax≡b(mod m)的解为：%d\n", x3);
    } else {
        printf("同余式ax≡b(mod m)无解。\n");
    }
    return 0;
}

程序运行结果如下：

请输入同余式ax≡b(mod m)中的a、b、m：
21 7 28
同余式ax≡b(mod m)的解为：8

其中，输入的a、b、m分别表示同余式ax≡b(mod m)中的参数a、b、m，程序会计算出同余式的解并输出。如果同余式无解，则输出“同余式ax≡b(mod m)无解。”。

用c语言编程实现计算同余式ax≡b(mod m)的解

#include <stdio.h>

int gcd(int a, int b) { // 求最大公约数
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int a, b, m;
    printf("请输入a, b, m的值：");
    scanf("%d %d %d", &a, &b, &m);

    int d = gcd(a, m); // 求a和m的最大公约数
    if (b % d != 0) { // 如果b不能被d整除，那么同余式无解
        printf("同余式无解\n");
        return 0;
    }

    int x0 = ((b / d) * a) % m; // 求出x0
    printf("同余式的解为：");
    for (int i = 0; i < d; i++) { // 求出x0 + km，其中k = 0, 1, ..., d - 1
        printf("%d ", (x0 + i * (m / d)) % m);
    }
    printf("\n");

    return 0;
}

注：此代码仅适用于a和m互质的情况下。如果a和m不互质，需要将同余式转化为同余式ax≡b(mod m')的形式，其中m'为m除以a和m的最大公约数后的值。