Si $n \mid a^n - 1$, prouver $ a + 1 $, $ a^2 + 2 $,…, $ a^n + n $ sont distincts $ \bmod n $.

Question

J'ai essayé le problème suivant:

Laisser $ a $ et $ n $ être deux nombres naturels pour lesquels $ n \mid a^n - 1 $. Prouve-le$ a + 1 $, $ a^2 + 2 $, ..., $ a^n + n $ sont distincts $ \bmod n $.

Je pense à l'induction (évidemment), peut-être à l'ordre des éléments (théorie élémentaire des nombres). Je n'ai pas d'idée à suivre. Le problème a été choisi pour un cours de mathématiques junior, à partir du livre:

<< L'induction mathématique: une méthode de preuve puissante et élégante >> Andreescu Titu, Crișan Vlad, XYZ Press, 2017.

Answer 1

C'est une question assez intéressante, ainsi qu'une question assez difficile pour un cours de mathématiques junior. Si$n = 1$, puis tout $a$ travaux, donner $a + 1 \equiv 0 \pmod{1}$. Sinon pour$n \gt 1$, l'ensemble d'étapes suivant montre qu'en utilisant des ordres multiplicatifs, il existe un ensemble de facteurs décroissants de $n$ jusqu'à $a \equiv 1$modulo un certain facteur. Commencer avec$m_1 = n$ et $r = 1$.

1. Si $a \equiv 1 \pmod{m_r}$, ensemble $j = r$ et quittez cet ensemble d'étapes.
2. Soit l' ordre multiplicatif de$a$ modulo $m_r$ être $m_{r+1} = \operatorname{ord}_{m_{r}}(a) \gt 1$. Depuis$a^{m_r} \equiv 1 \pmod{m_r}$, puis $m_{r+1} \mid m_{r}$. De même que$a^{m_{r+1}} \equiv 1 \pmod{m_{r}}$, ça signifie $a^{m_{r+1}} \equiv 1 \pmod{m_{r+1}}$. De plus, avec la fonction totient d'Euler , puisque$m_{r+1} \mid \varphi(m_r)$ et $\varphi(m_r) \lt m_r$, vous obtenez $m_{r+1} \lt m_{r}$.
3. Incrément $r$ et passez à l'étape #$1$.

Depuis chaque $m_r$ diminue, mais doit être $\gt 1$, la procédure ci-dessus doit finir par se terminer, c'est-à-dire qu'il y a un $j \ge 1$. L'ensemble d'étapes suivant montre pour chaque$m_r \; \forall \; 1 \le r \le j$ que chaque $a^i + i \; \forall \; 1 \le i \le m_r$ est unique $\bmod m_r$.

1. À partir de l'étape #$1$, depuis $a \equiv 1 \pmod{m_j}$, vous avez $a^{i} + i \equiv 1 + i \pmod{m_j} \; \forall \; i$. Ça signifie$a^i + i \; \forall \; 1 \le i \le m_{j}$ est distinct $\bmod m_j$. Ensemble$r = j$.
2. Si $r = 1$, depuis $m_1 = n$, quittez ces étapes.
3. Pour toute $k \ge 1$, considérez tout $s \gt k$ où $a^{k} + k \equiv a^{s} + s \pmod{m_{r-1}}$. Notez qu'ils doivent également être congruents les uns aux autres modulo$m_r$ depuis $m_r \mid m_{r-1}$. Depuis$a^{i} + i \; \forall \; 1 \le i \le m_{r}$ sont tous distincts $\bmod m_r$, puis $s \equiv k \pmod{m_{r}}$. Donc,$s = qm_{r} + k$ pour un entier $q \ge 1$. En utilisant$a^{m_{r}} \equiv 1 \pmod{m_{r-1}}$, puis $a^{s} + s \equiv a^{qm_{r} + k} + qm_{r} + k \equiv a^k + qm_{r} + k \pmod{m_{r-1}}$. Cela donne$qm_{r} \equiv 0 \pmod{m_{r-1}}$, c'est-à-dire pour certains $t \ge 1$, vous avez $s = tm_{r-1} + k$. Cela signifie que les valeurs se répètent chacune$m_{r-1}$, alors $a^{i} + i \; \forall \; 1 \le i \le m_{r-1}$ doit être distinct $\bmod m_{r-1}$.
4. Décrémenter $r$ et passez à l'étape #$5$.

Depuis $r$ est décrémenté à chaque fois à l'étape #$7$, $r$ doit finalement devenir $1$ donc la procédure se termine à l'étape #$5$, avec un résultat comme expliqué à l'étape #$4$ ou la fin de l'étape #$6$, c'est-à-dire, chacun $a^{i} + i \; \forall \; 1 \le i \le n$ sont distincts $\bmod n$.

Un exemple est $n = 18$ et $a = 5$. Cela donne$m_1 = 18$, $m_2 = 6$ et $m_3 = 2$, alors $j = 3$.

Notez la boucle aux étapes #$1$ à $3$ incréments $r$ à chaque fois, tandis que la boucle par étapes #$5$ à $7$ décrémente $r$à chaque fois, ce qui les rend tous deux similaires à l'induction (j'ai choisi d'utiliser des boucles à la place car je pensais que ce serait plus simple à expliquer et plus facile à comprendre que d'utiliser l'induction avec diverses conditions supplémentaires à vérifier). C'est probablement pourquoi la question a été incluse dans le livre sur l'induction mathématique.