場合 $n \mid a^n - 1$、証明する $ a + 1 $、 $ a^2 + 2 $、…、 $ a^n + n $ 明確です $ \bmod n $。
私は次の問題を試しました：
しましょう $ a $ そして $ n $ 2つの自然数である $ n \mid a^n - 1 $。証明してください$ a + 1 $、 $ a^2 + 2 $、...、 $ a^n + n $ 明確です $ \bmod n $。
私は誘導（明らかに）、多分元素の次数（元素数論）について考えています。従う考えがありません。この問題は、本からジュニア数学コースに選ばれました。
<<数学的誘導：強力でエレガントな証明方法>> Andreescu Titu、Crișan Vlad、XYZ Press、2017年。
回答
これは非常に興味深い質問であり、ジュニア数学コースにとってはかなり難しい質問です。場合$n = 1$、その後任意 $a$ 動作し、与える $a + 1 \equiv 0 \pmod{1}$。それ以外の場合$n \gt 1$、次の一連の手順は、乗法次数を使用して、の減少係数のセットがあることを示しています。 $n$ まで $a \equiv 1$いくつかの係数を法として。皮切りに$m_1 = n$ そして $r = 1$。
- 場合 $a \equiv 1 \pmod{m_r}$、 セットする $j = r$ この一連の手順を終了します。
- の乗法順序をしましょう$a$ モジュロ $m_r$ あります $m_{r+1} = \operatorname{ord}_{m_{r}}(a) \gt 1$。以来$a^{m_r} \equiv 1 \pmod{m_r}$、その後 $m_{r+1} \mid m_{r}$。に加えて$a^{m_{r+1}} \equiv 1 \pmod{m_{r}}$、 これの意味は $a^{m_{r+1}} \equiv 1 \pmod{m_{r+1}}$。さらに、オイラーのトーティエント関数を使用すると、$m_{r+1} \mid \varphi(m_r)$ そして $\varphi(m_r) \lt m_r$、あなたは得る $m_{r+1} \lt m_{r}$。
- インクリメント $r$ ステップ＃に進みます$1$。
それぞれ以来 $m_r$ 減少していますが、 $\gt 1$、上記の手順は最終的に終了する必要があります。つまり、 $j \ge 1$。次の一連の手順は、それぞれについて示しています$m_r \; \forall \; 1 \le r \le j$ そのそれぞれ $a^i + i \; \forall \; 1 \le i \le m_r$ ユニークです $\bmod m_r$。
- ステップ＃から$1$、以来 $a \equiv 1 \pmod{m_j}$、 あなたが持っている $a^{i} + i \equiv 1 + i \pmod{m_j} \; \forall \; i$。これの意味は$a^i + i \; \forall \; 1 \le i \le m_{j}$ 明確です $\bmod m_j$。セットする$r = j$。
- 場合 $r = 1$、以来 $m_1 = n$、これらの手順を終了します。
- どんな場合でも $k \ge 1$、考慮してください $s \gt k$ どこ $a^{k} + k \equiv a^{s} + s \pmod{m_{r-1}}$。また、モジュロを法として互いに合同である必要があることに注意してください$m_r$ 以来 $m_r \mid m_{r-1}$。以来$a^{i} + i \; \forall \; 1 \le i \le m_{r}$ すべて異なる $\bmod m_r$、その後 $s \equiv k \pmod{m_{r}}$。したがって、$s = qm_{r} + k$ いくつかの整数の場合 $q \ge 1$。使用する$a^{m_{r}} \equiv 1 \pmod{m_{r-1}}$、その後 $a^{s} + s \equiv a^{qm_{r} + k} + qm_{r} + k \equiv a^k + qm_{r} + k \pmod{m_{r-1}}$。これは与える$qm_{r} \equiv 0 \pmod{m_{r-1}}$、すなわち、いくつかのために $t \ge 1$、 あなたが持っている $s = tm_{r-1} + k$。これは、値がそれぞれ繰り返されることを意味します$m_{r-1}$、 そう $a^{i} + i \; \forall \; 1 \le i \le m_{r-1}$ 明確でなければなりません $\bmod m_{r-1}$。
- デクリメント $r$ ステップ＃に進みます$5$。
以来 $r$ ステップ＃で毎回デクリメントされています$7$、 $r$ 最終的になる必要があります $1$ したがって、プロシージャはステップ＃で終了します。$5$、ステップ＃で説明した結果$4$ またはステップ＃の終わり$6$、すなわち、それぞれ $a^{i} + i \; \forall \; 1 \le i \le n$ 明確です $\bmod n$。
例は $n = 18$ そして $a = 5$。これは与える$m_1 = 18$、 $m_2 = 6$ そして $m_3 = 2$、 そう $j = 3$。
手順のループに注意してください＃$1$ に $3$ インクリメント $r$ 毎回、ステップ＃のループ中$5$ に $7$ デクリメント $r$毎回、両方を誘導に似たものにします（さまざまな追加条件で誘導を使用してチェックするよりも、説明が簡単で理解しやすいと思ったので、代わりにループを使用することにしました）。これが、数学的帰納法に関する本に質問が含まれている理由である可能性があります。