MathLabs

第1题

设 mm 和 nn 是满足 1≤m<n1 \le m < n 的正整数。已知 1978m1978^m 的十进制表示的末三位数字与 1978n1978^n 的末三位数字相同。求使 mm 取最小值的 nn 和 m+nm+n。
第 2/8 步:用中国剩余定理分解模数
通俗地说

分别处理模 8 与模 125,比直接处理模 1000 容易得多。

1000=23⋅53=8⋅125,gcd⁡(8,125)=11000 = 2^3\cdot 5^3 = 8\cdot 125,\qquad \gcd(8,125)=1
详细分析

由于 88 与 125125 互素,条件 1978m(1978 n−m−1)≡0(mod1000)1978^m\left(1978^{\,n-m}-1\right)\equiv 0 \pmod{1000} 分解为模 88 与模 125125 两个相互独立的条件。