MathLabs

第1問

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

法125での関係は法5でも必ず成り立つため、法5での振る舞いが候補の位数を絞り込む。

1978≡3(mod5), ord5(3)=4  ⇒  4∣ord125(1978)1978\equiv 3 \pmod 5,\ \mathrm{ord}_5(3)=4 \;\Rightarrow\; 4 \mid \mathrm{ord}_{125}(1978)
詳しい解説

1978r≡1(mod125)1978^r\equiv 1\pmod{125} ならば 1978r≡1(mod5)1978^r\equiv 1\pmod 5 も成り立つ。1978≡3(mod5)1978\equiv 3\pmod 5 であり 33 の法44での位数は 55 である（34=81≡13^4=81\equiv 1 より）から、法125125での位数は 44 の倍数でなければならず、4,20,1004, 20, 100 の約数のうち残るのは 100100 のみとなる。