Es la declaración $b^n\equiv 1\pmod n$ equivalente a " $x\mapsto b^x-x\pmod n$ es una biyección"?

Question

Supongamos que $n$ es un número natural y $b$ es uno coprimo a él tal que $b^n\equiv 1\pmod n$ . ¿Se deduce que, si $b^x-x\equiv b^y-y\pmod n$ entonces $x\equiv y\pmod n$ ?

Esto se inspira en los comentarios de un respuesta que escribí lo que me hizo pensar en los puntos fijos de la exponenciación. Jugando con Mathematica, me di cuenta de que $$x\mapsto 9^x-x\pmod{1000}$$ es una función inyectiva. De hecho, me he dado cuenta de que si sustituimos $9$ por cualquier otro número coprimo a $1000$ Esto sigue siendo válido. Jugando un poco más, me di cuenta de que la lista de números $n$ que no sea $1000$ tal que todas las bases coprimas $b$ tiene esta propiedad comienza de la misma manera que esta secuencia en OEIS que es exactamente la secuencia de $n$ tal que $b^n\equiv 1\pmod n$ para $b$ coprima a $n$ . No puedo probar que las listas sean iguales (pero parece que lo son), pero puedo ver que $b^n\equiv 1\pmod n$ es una condición necesaria para $x\mapsto b^x-x$ sea inyectiva (ya que de lo contrario no está bien definida).

La única idea que tengo sobre el problema es que claramente se mantiene si $b=1$ o $-1$ . Esto último puede argumentarse como si $(-1)^n\equiv 1\pmod n$ entonces $n$ es par y $x\mapsto (-1)^x-x$ asigna pares a probabilidades y viceversa y es una función lineal con unidad ( $-1$ ) coeficiente de $x$ sobre esos dominios - y por lo tanto es biyectiva. Me parece que puede haber alguna generalización de este enfoque mediante la partición $(\mathbb Z/n\mathbb Z,+)$ en $\text{ord}_n(b)$ cosets (donde $\text{ord}$ es el orden multiplicativo de $b$ mod $n$ ), pero no he conseguido encontrarlo si es que existe. Sin duda, restringiendo el mapa en cuestión a un único coset de este tipo se obtiene una biyección entre él y otro coset (como $b^{x}-x$ y $b^{x+\text{ord}_n(b)}-x-\text{ord}_n(b)$ son iguales mod $\text{ord}_n(b)$ ) - pero no puedo demostrar que dos cosets distintos no se mapean en el mismo lugar, ya que esto requiere considerar el mapa sobre el dominio más grande, donde se comporta peor.

Me interesa principalmente la respuesta a esta pregunta, independientemente de la técnica, sin embargo, me interesaría especialmente saber si los métodos que he esbozado pueden extenderse provechosamente a una prueba.

Answer 1

Podemos realizar el esbozo de prueba en la pregunta como una prueba por inducción sobre $n$ . La afirmación se cumple trivialmente para $n=1$ . A continuación, elija cualquier $b$ y $n$ tal que $b^n\equiv 1\pmod n$ . Si dejamos que $k$ sea el orden multiplicativo de $b$ mod $n$ podemos ver claramente que $k$ divide $n$ , como $b^x\equiv 1$ sólo para los múltiplos de $k$ y además que $k<n$ , como $k$ es el orden del subgrupo multiplicativo generado por $b$ y esto debe dividir el orden del grupo multiplicativo mod $n$ que es menor que $n$ .

Supongamos ahora que $$b^x-x\equiv b^y-y\pmod n.\tag{1}$$ Obsérvese que esto implica la afirmación más débil de que $b^x-x\equiv b^y-y \pmod k$ . Sin embargo, como $b^k\equiv 1\pmod k$ y $k<n$ podemos aplicar la hipótesis inductiva y concluir que $x\equiv y\pmod k$ . Sin embargo, esto implica $b^x\equiv b^y\pmod n$ . Restando la ecuación (1) se obtiene $x\equiv y\pmod n$ , según se desee.