MathLabs

第1問

mm を満たす正の整数 nn, 1≤m<n1 \le m < n について、1978m1978^m の十進表示における下3桁が 1978n1978^n の下3桁と等しいとする。mm が最小となるような nn, m+nm+n を求めよ。
ステップ 4/8: 法125の部分を位数の条件に帰着させる
ざっくり言うと

1978^m は法125で可逆なので、合同式から完全に消去できる。

gcd⁡(1978,125)=1  ⇒  1978 n−m≡1(mod125)\gcd(1978,125)=1 \;\Rightarrow\; 1978^{\,n-m}\equiv 1 \pmod{125}
詳しい解説

19781978 は法 125125 で可逆であるから、法125125の条件 1978m(1978 n−m−1)≡01978^m\left(1978^{\,n-m}-1\right)\equiv 0 は 1978 n−m≡1(mod125)1978^{\,n-m}\equiv 1\pmod{125} に依存せず直接 mm に帰着する。