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为非负整数。