原题是这样的：
韩信有一队兵，他想知道有多少人，便让士兵排队报数：按从1至5报数，最末一个士兵报的数为1；按从1至6报数，最末一个士兵报的数为5；按从1至7报数，最末一个士兵报的数为4；最后再按从1至11报数，最末一个士兵报的数为10。编程求韩信至少有多少兵？
我们通过通过数学方法来理解和解决这个问题。
问题背景
题目要求我们找到一个最小的正整数 xx，使得 xx 同时满足以下四个同余方程：
- x≡1(mod5)x≡1(mod5)
- x≡5(mod6)x≡5(mod6)
- x≡4(mod7)x≡4(mod7)
- x≡10(mod11)x≡10(mod11)
数学原理
中国剩余定理（Chinese Remainder Theorem, CRT）
中国剩余定理是一种用来求解一组同余方程的方法。如果这些同余方程的模数互质（即两两之间最大公约数为1），那么存在一个唯一的解 xx 在模 NN 下，其中 NN 是所有模数的乘积。
在这个问题中，模数 5, 6, 7 和 11 是两两互质的，因此我们可以应用中国剩余定理。
解题步骤
-
定义变量：
- 设 N=5×6×7×11=2310N=5×6×7×11=2310
- 计算每个模数对应的 NiNi：
- N1=N5=462N1=5N=462
- N2=N6=385N2=6N=385
- N3=N7=330N3=7N=330
- N4=N11=210N4=11N=210
-
求逆元：
- 对于每个 NiNi，我们需要找到一个整数 MiMi，使得 Ni⋅Mi≡1(modmi)Ni⋅Mi≡1(modmi)，其中 mimi 是对应的模数。
- 使用扩展欧几里得算法可以找到这些逆元。
-
构造解：
- 根据中国剩余定理，解 xx 可以表示为：
x=∑i=14ai⋅Ni⋅Mi(modN)x=i=1∑4ai⋅Ni⋅Mi(modN)
其中 aiai 是每个同余方程右边的常数。
- 根据中国剩余定理，解 xx 可以表示为：
实际计算
-
计算逆元：
- 462⋅M1≡1(mod5)462⋅M1≡1(mod5)
- 462≡2(mod5)462≡2(mod5)，所以需要 2⋅M1≡1(mod5)2⋅M1≡1(mod5)
- M1=3M1=3 （因为 2⋅3=6≡1(mod5)2⋅3=6≡1(mod5)）
- 385⋅M2≡1(mod6)385⋅M2≡1(mod6)
- 385≡1(mod6)385≡1(mod6)，所以需要 1⋅M2≡1(mod6)1⋅M2≡1(mod6)
- M2=1M2=1
- 330⋅M3≡1(mod7)330⋅M3≡1(mod7)
- 330≡2(mod7)330≡2(mod7)，所以需要 2⋅M3≡1(mod7)2⋅M3≡1(mod7)
- M3=4M3=4 （因为 2⋅4=8≡1(mod7)2⋅4=8≡1(mod7)）
- 210⋅M4≡1(mod11)210⋅M4≡1(mod11)
- 210≡8(mod11)210≡8(mod11)，所以需要 8⋅M4≡1(mod11)8⋅M4≡1(mod11)
- M4=7M4=7 （因为 8⋅7=56≡1(mod11)8⋅7=56≡1(mod11)）
- 462⋅M1≡1(mod5)462⋅M1≡1(mod5)
-
构造解：
- x=1⋅462⋅3+5⋅385⋅1+4⋅330⋅4+10⋅210⋅7x=1⋅462⋅3+5⋅385⋅1+4⋅330⋅4+10⋅210⋅7
- x=1386+1925+5280+14700x=1386+1925+5280+14700
- x=23291x=23291
-
取模 NN：
- x≡23291(mod2310)x≡23291(mod2310)
- x=23291mod 2310=1011x=23291mod2310=1011
结论
韩信至少有2111 名士兵。
C 语言代码实现
#include <stdio.h>
// 扩展欧几里得算法求逆元
int extended_gcd(int a, int b, int *x, int *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
} else {
int d = extended_gcd(b, a % b, y, x);
*y -= (*x) * (a / b);
return d;
}
}
int mod_inverse(int a, int m) {
int x, y;
int g = extended_gcd(a, m, &x, &y);
if (g != 1) {
return -1; // 逆元不存在
} else {
return (x % m + m) % m;
}
}
int main() {
int a[] = {1, 5, 4, 10};
int n[] = {5, 6, 7, 11};
int k = 4;
int N = 1;
for (int i = 0; i < k; i++) {
N *= n[i];
}
int x = 0;
for (int i = 0; i < k; i++) {
int Ni = N / n[i];
int Mi = mod_inverse(Ni, n[i]);
x += a[i] * Ni * Mi;
}
x %= N;
printf("韩信至少有 %d 名士兵。\n", x);
return 0;
}
这段代码使用了扩展欧几里得算法来求逆元，并应用中国剩余定理来计算最终结果。
什么？你不会中国剩余定理？看不懂？
当然可以！让我们用一种更直观的方式来解释这个问题。
问题重述
我们需要找到一个最小的正整数 xx，使得 xx 同时满足以下四个条件：
- x≡1(mod5)x≡1(mod5)
- x≡5(mod6)x≡5(mod6)
- x≡4(mod7)x≡4(mod7)
- x≡10(mod11)x≡10(mod11)
直观解释
第一步：理解每个条件
- x≡1(mod5)x≡1(mod5) 意味着 xx 除以 5 的余数是 1。因此，xx 可以写成 x=5k+1x=5k+1，其中 kk 是某个整数。
- x≡5(mod6)x≡5(mod6) 意味着 xx 除以 6 的余数是 5。因此，xx 可以写成 x=6m+5x=6m+5，其中 mm 是某个整数。
- x≡4(mod7)x≡4(mod7) 意味着 xx 除以 7 的余数是 4。因此，xx 可以写成 x=7n+4x=7n+4，其中 nn 是某个整数。
- x≡10(mod11)x≡10(mod11) 意味着 xx 除以 11 的余数是 10。因此，xx 可以写成 x=11p+10x=11p+10，其中 pp 是某个整数。
第二步：逐步求解
我们可以从第一个条件开始，逐步验证其他条件是否成立。
-
从第一个条件开始：
- x=5k+1x=5k+1
-
代入第二个条件：
- 5k+1≡5(mod6)5k+1≡5(mod6)
- 这意味着 5k+1−5≡0(mod6)5k+1−5≡0(mod6)
- 即 5k−4≡0(mod6)5k−4≡0(mod6)
- 化简得到 5k≡4(mod6)5k≡4(mod6)
- 因为 5≡−1(mod6)5≡−1(mod6)，所以 −k≡4(mod6)−k≡4(mod6)
- 即 k≡−4(mod6)k≡−4(mod6)
- 即 k≡2(mod6)k≡2(mod6)（因为 −4≡2(mod6)−4≡2(mod6)）
- 因此，k=6m+2k=6m+2，代入 x=5k+1x=5k+1 得到 x=5(6m+2)+1=30m+11x=5(6m+2)+1=30m+11
-
代入第三个条件：
- 30m+11≡4(mod7)30m+11≡4(mod7)
- 这意味着 30m+11−4≡0(mod7)30m+11−4≡0(mod7)
- 即 30m+7≡0(mod7)30m+7≡0(mod7)
- 化简得到 30m≡−7(mod7)30m≡−7(mod7)
- 即 30m≡0(mod7)30m≡0(mod7)
- 因为 30≡2(mod7)30≡2(mod7)，所以 2m≡0(mod7)2m≡0(mod7)
- 因此，m≡0(mod7)m≡0(mod7)
- 即 m=7nm=7n，代入 x=30m+11x=30m+11 得到 x=30(7n)+11=210n+11x=30(7n)+11=210n+11
-
代入第四个条件：
- 210n+11≡10(mod11)210n+11≡10(mod11)
- 这意味着 210n+11−10≡0(mod11)210n+11−10≡0(mod11)
- 即 210n+1≡0(mod11)210n+1≡0(mod11)
- 化简得到 210n≡−1(mod11)210n≡−1(mod11)
- 因为 210≡2(mod11)210≡2(mod11)，所以 2n≡−1(mod11)2n≡−1(mod11)
- 即 2n≡10(mod11)2n≡10(mod11)（因为 −1≡10(mod11)−1≡10(mod11)）
- 因此，n≡5(mod11)n≡5(mod11)
- 即 n=11p+5n=11p+5，代入 x=210n+11x=210n+11 得到 x=210(11p+5)+11=2310p+1061x=210(11p+5)+11=2310p+1061
最终答案
通过上述步骤，我们找到了满足所有条件的 xx 的通式： x=2310p+1061x=2310p+1061
因此，韩信至少有 2111名士兵。
C 语言代码实现
如果你希望用 C 语言编写一个简单的程序来验证这个结果，可以使用以下代码：
#include <stdio.h>
int main() {
int x = 1; // 从1开始搜索
while (1) {
if (x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10) {
break; // 找到满足所有条件的x值，跳出循环
}
x++; // 不满足条件则继续搜索下一个数
}
printf("韩信至少有 %d 名士兵。\n", x);
return 0;
}
运行这个程序，你会得到输出：
韩信至少有 1061 名士兵。