Si $n \mid a^n - 1$, probar $ a + 1 $, $ a^2 + 2 $,…, $ a^n + n $ son distintos $ \bmod n $.
He intentado el siguiente problema:
Dejar $ a $ y $ n $ ser dos números naturales para los cuales $ n \mid a^n - 1 $. Pruebalo$ a + 1 $, $ a^2 + 2 $, ..., $ a^n + n $ son distintos $ \bmod n $.
Estoy pensando en la inducción (obviamente), tal vez en el orden de los elementos (teoría de números elemental). No tengo una idea a seguir. El problema ha sido elegido para un curso de matemáticas junior, del libro:
<< Inducción matemática: un método de prueba poderoso y elegante >> Andreescu Titu, Crișan Vlad, XYZ Press, 2017.
Respuestas
Esta es una pregunta bastante interesante, así como también bastante desafiante para un curso de matemáticas junior. Si$n = 1$, entonces cualquiera $a$ obras, dando $a + 1 \equiv 0 \pmod{1}$. De lo contrario para$n \gt 1$, el siguiente conjunto de pasos muestra que, al utilizar órdenes multiplicativos, hay un conjunto de factores decrecientes de $n$ hasta $a \equiv 1$módulo algún factor. Empezar con$m_1 = n$ y $r = 1$.
- Si $a \equiv 1 \pmod{m_r}$, establecer $j = r$ y salga de este conjunto de pasos.
- Sea el orden multiplicativo de$a$ modulo $m_r$ ser $m_{r+1} = \operatorname{ord}_{m_{r}}(a) \gt 1$. Ya que$a^{m_r} \equiv 1 \pmod{m_r}$, luego $m_{r+1} \mid m_{r}$. Junto con$a^{m_{r+1}} \equiv 1 \pmod{m_{r}}$, esto significa $a^{m_{r+1}} \equiv 1 \pmod{m_{r+1}}$. Además, con la función totient de Euler , dado que$m_{r+1} \mid \varphi(m_r)$ y $\varphi(m_r) \lt m_r$, usted obtiene $m_{r+1} \lt m_{r}$.
- Incremento $r$ y ve al paso #$1$.
Desde cada uno $m_r$ está disminuyendo, pero debe ser $\gt 1$, el procedimiento anterior debe salir eventualmente, es decir, hay un $j \ge 1$. El siguiente conjunto de pasos se muestra para cada$m_r \; \forall \; 1 \le r \le j$ que cada $a^i + i \; \forall \; 1 \le i \le m_r$ es único $\bmod m_r$.
- Desde el paso #$1$, ya que $a \equiv 1 \pmod{m_j}$, tienes $a^{i} + i \equiv 1 + i \pmod{m_j} \; \forall \; i$. Esto significa$a^i + i \; \forall \; 1 \le i \le m_{j}$ es distinto $\bmod m_j$. Conjunto$r = j$.
- Si $r = 1$, ya que $m_1 = n$, sal de estos pasos.
- Para cualquier $k \ge 1$, considere cualquier $s \gt k$ dónde $a^{k} + k \equiv a^{s} + s \pmod{m_{r-1}}$. Tenga en cuenta que también deben ser congruentes entre sí módulo$m_r$ ya que $m_r \mid m_{r-1}$. Ya que$a^{i} + i \; \forall \; 1 \le i \le m_{r}$ son todos distintos $\bmod m_r$, luego $s \equiv k \pmod{m_{r}}$. Así,$s = qm_{r} + k$ por algún entero $q \ge 1$. Utilizando$a^{m_{r}} \equiv 1 \pmod{m_{r-1}}$, luego $a^{s} + s \equiv a^{qm_{r} + k} + qm_{r} + k \equiv a^k + qm_{r} + k \pmod{m_{r-1}}$. Esto da$qm_{r} \equiv 0 \pmod{m_{r-1}}$, es decir, para algunos $t \ge 1$, tienes $s = tm_{r-1} + k$. Esto significa que los valores se repiten cada$m_{r-1}$, entonces $a^{i} + i \; \forall \; 1 \le i \le m_{r-1}$ debe ser distinto $\bmod m_{r-1}$.
- Decremento $r$ y ve al paso #$5$.
Ya que $r$ está disminuyendo cada vez en el paso #$7$, $r$ debe eventualmente convertirse $1$ por lo que el procedimiento sale en el paso #$5$, con un resultado como se explica en el paso #$4$ o al final del paso #$6$, es decir, cada $a^{i} + i \; \forall \; 1 \le i \le n$ son distintos $\bmod n$.
Un ejemplo es $n = 18$ y $a = 5$. Esto da$m_1 = 18$, $m_2 = 6$ y $m_3 = 2$, entonces $j = 3$.
Tenga en cuenta el bucle en los pasos #$1$ a $3$ incrementos $r$ cada vez, mientras que el bucle en los pasos #$5$ a $7$ decrementos $r$cada vez, lo que los hace similares a la inducción (elegí usar bucles en su lugar porque pensé que sería más simple de explicar y más fácil de entender que usar la inducción con varias condiciones adicionales para verificar). Esta es probablemente la razón por la que se incluyó la pregunta en el libro sobre la inducción matemática.