MathLabs

第1問

mm を満たす正の整数 nn, 1≤m<n1 \le m < n について、1978m1978^m の十進表示における下3桁が 1978n1978^n の下3桁と等しいとする。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 に関する2つの独立な条件に分解される。