同余方程欧拉定理C++

欧拉定理是指在模数为 m 的情况下，对于任意整数 a 和 m，满足 a 与 m 互质，那么 a 的欧拉函数值 φ(m) 就是满足 a^φ(m) ≡ 1 (mod m) 的最小正整数指数 φ(m)。即：

a^φ(m) ≡ 1 (mod m)

其中，a 与 m 互质，φ(m) 为欧拉函数值。

例如，对于模数 m = 7 和整数 a = 3，因为 3 与 7 互质，且 φ(7) = 6，所以有：

3^6 ≡ 1 (mod 7)

这个定理可以用来求解同余方程，例如：

3x ≡ 2 (mod 7)

因为 3 与 7 互质，所以可以使用欧拉定理，得到：

3^6 ≡ 1 (mod 7)

两边同时乘以 3，得到：

3^7 ≡ 3 (mod 7)

再将 2 乘以 3^6，得到：

2 × 3^6 ≡ 2 (mod 7)

因为 3^6 ≡ 1 (mod 7)，所以：

2 × 3^6 ≡ 2 × 1 ≡ 2 (mod 7)

因此，原同余方程的解为：

x ≡ 2 × 3^5 ≡ 2 × 243 ≡ 6 (mod 7)。

相关问题

C++写一篇同余方程的欧拉定理求解

同余方程是数论中常见的问题，欧拉定理是求解同余方程的一种重要方法。假设a、m是正整数，且它们互质，即gcd(a,m)=1，则欧拉定理表示：a^(φ(m)) ≡ 1 (mod m)，其中φ(m)表示小于等于m的正整数中与m互质的数的个数（欧拉函数）。这个公式可以用来求解同余方程a^x ≡ b (mod m)。

具体步骤如下：

1. 求出φ(m)的值。如果m是质数，则φ(m)=m-1；如果m不是质数，则φ(m)=m×(1-1/p1)×(1-1/p2)×...×(1-1/pn)，其中p1、p2、...、pn是m的所有质因数。

2. 判断a和m是否互质，如果不互质则无解，如果互质则继续。

3. 利用欧拉定理，求出a^(φ(m))的余数r。

4. 如果b不等于r，则无解；如果b等于r，则设x=k×φ(m)+j，其中k为非负整数，j为0到φ(m)-1之间的整数。则a^x ≡ a^(k×φ(m))×a^j ≡ (a^(φ(m)))^k × a^j ≡ 1^k × b ≡ b (mod m)。

因此，同余方程a^x ≡ b (mod m)的解为x=k×φ(m)+j，其中k为非负整数，j为0到φ(m)-1之间的整数。

例如，假设要解同余方程2^x ≡ 5 (mod 17)，则φ(17)=16，2和17互质，因此2^(φ(17)) ≡ 1 (mod 17)，即2^16 ≡ 1 (mod 17)。因此，2^x ≡ 5 (mod 17)的解为x=k×φ(17)+j，其中k为非负整数，j为0到15之间的整数。将2^x在模17意义下的余数列出来如下：

2^0 mod 17 = 1
2^1 mod 17 = 2
2^2 mod 17 = 4
2^3 mod 17 = 8
2^4 mod 17 = 16
2^5 mod 17 = 13
2^6 mod 17 = 7
2^7 mod 17 = 14
2^8 mod 17 = 9
2^9 mod 17 = 18 ≡ 1 (mod 17)
2^10 mod 17 = 2×2^9 ≡ 2 (mod 17)
2^11 mod 17 = 4×2^9 ≡ 4 (mod 17)
2^12 mod 17 = 8×2^9 ≡ 8 (mod 17)
2^13 mod 17 = 16×2^9 ≡ 16 (mod 17)
2^14 mod 17 = 13×2^9 ≡ 13 (mod 17)
2^15 mod 17 = 7×2^9 ≡ 7 (mod 17)

因此，2^x ≡ 5 (mod 17)的解为x=k×φ(17)+j，其中k为非负整数，j=14，因为2^14 ≡ 13 (mod 17)。因此，2^x ≡ 5 (mod 17)的解为x=16k+14，其中k为非负整数。

同余方程组c++

在C++中，可以使用扩展欧几里得算法来解决同余方程组，以下是一个实现示例：

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int mod_inverse(int a, int m) {
    int x, y;
    gcd(a, m, x, y);
    return (x % m + m) % m;
}

int solve_congruences(const vector<int>& a, const vector<int>& m) {
    int x = 0, M = 1;
    for (int i = 0; i < m.size(); i++) {
        int Mi = M / gcd(M, m[i]) * m[i];
        int ti = mod_inverse(Mi / m[i], m[i]);
        x = (x + a[i] * ti * Mi) % M;
        M = Mi;
    }
    return (x + M) % M;
}

int main() {
    vector<int> a = {2, 3, 2};
    vector<int> m = {3, 5, 7};
    int x = solve_congruences(a, m);
    cout << "x = " << x << endl; // 输出 x = 23
    return 0;
}

其中，“gcd”函数用于计算最大公约数和扩展欧几里得算法，它返回最大公约数d，并通过引用参数x和y返回贝祖等式ax + by = d 的解。这里使用递归实现，将x和y的顺序颠倒以便计算ti时使用。

“mod_inverse”函数用于计算a模m的逆元，即满足ax ≡ 1 (mod m)的x。

“solve_congruences”函数实现了中国剩余定理。首先计算M = m1 * m2 * ... * mn，然后对于每个同余方程，计算Mi = M / mi，以及它在模mi下的逆元ti，最后计算解x = Σ(ai * ti * Mi) (mod M)。注意到这里使用了M逆元而非mi逆元，因为后者可能不存在。

最后在主函数中输入系数和模数，调用solve_congruences函数求解同余方程组，并输出结果。