MathLabs

第1题

设 mm 和 nn 是满足 1≤m<n1 \le m < n 的正整数。已知 1978m1978^m 的十进制表示的末三位数字与 1978n1978^n 的末三位数字相同。求使 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。