MathLabs

第1問

mm を満たす正の整数 nn, 1≤m<n1 \le m < n について、1978m1978^m の十進表示における下3桁が 1978n1978^n の下3桁と等しいとする。mm が最小となるような nn, m+nm+n を求めよ。
ステップ 1/8: 桁の条件を合同式に翻訳する
前のステップ次のステップ
ざっくり言うと

「下3桁が同じ」とは、法1000での合同関係にほかならない。

1978n≡1978m(mod1000)  ⟺  1978m(1978 n−m−1)≡0(mod1000)1978^n \equiv 1978^m \pmod{1000} \iff 1978^m\left(1978^{\,n-m}-1\right)\equiv 0 \pmod{1000}
詳しい解説

2つの正の整数の下3桁が等しいことは、その差が 10001000 の倍数であることと同値である。これを 1978n1978^n と 1978m1978^m に適用し、1978m1978^m をくくり出すと同値な乗法的条件が得られる。