MathLabs

第1問

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

元の位数は常に群の指数を割り切る。ここでは φ(125) = 100 である。

φ(125)=100  ⇒  1978100≡1(mod125),ord125(1978)∣100\varphi(125)=100 \;\Rightarrow\; 1978^{100}\equiv 1 \pmod{125},\quad \mathrm{ord}_{125}(1978)\mid 100
詳しい解説

オイラーの定理より 1978φ(125)≡1(mod125)1978^{\varphi(125)}\equiv 1\pmod{125}、ここで φ(125)=100\varphi(125)=100。したがって合同式を満たす最小の n−mn-m は乗法位数 ord125(1978)\mathrm{ord}_{125}(1978) であり、これは 100100 の約数でなければならない。