Si es divisible por $a^{n}-1$ $n$ $a+1,a^2+2, \ldots a^n+n$ deje restos diferentes cuando dividido por $n$

Question

Se da que el % es divisible por $a^n-1$ % números naturales $n$% #% y $a$. Demostrar que los números $n$$$a+1,a^2+2, \ldots a^n+n$n$.

He intentado aplicar algunos modulo relaciones que probaron fracasadas. Algunas sugerencias, por favor. Gracias.

Answer 1

La condición de $a^n \equiv 1 \mod n$ motiva la introducción de $ord_n(a)$. Entonces vemos que podemos partición de la $n$ números en grupos específicos de modular las propiedades. La inducción parece conveniente. En conjunto, esto motiva la siguiente solución...

Vamos a probar esto mediante el uso de potentes inducción sobre $n$.

Para $n=1$ es claramente cierto.

Asumir que hemos probado para $n=1,2,\dotsc,m-1$. Vamos a probarlo para $n=m$.

Deje $a$ ser cualquier número tal que $m|a^m-1$. Denotar $ord_m(a)=k$. Tenemos $m=k \cdot r$$a^k \equiv 1 \mod m$. También, desde la $ord_m(a)|\phi(m)$ por FLT llegamos a la conclusión de $k \le \phi(m)<n$.

Denotar $a^{i}+i=x_i$. Ahora arreglar cualquier $s$ $1 \le s \le k$ y mirar los números $x_s,x_{k+s}, x_{2k+s}, \dotsc$.

Tenga en cuenta que $x_{ik+s} \equiv a^s+ik+s \equiv x_s+ik \mod m$. Por lo tanto (desde $k|m$) sabemos que los números de $x_s, x_{k+s},x_{2k+s},\dotsc$ dejar a todos el mismo residuo $\mod k$.

También desde $x_{ck+s}-x_{dk+s} \equiv ck-dk \equiv (c-d)k \mod m$ $r \not \mid c-d$ todas salen diferentes residuos de $\mod n$.

Ya que hay sólo $r$ valores de la forma $ik+x_s \mod n$ llegamos a la conclusión de que todos estos residuos son de hecho asumido por algunos $x_j$.

Podemos repetir el mismo argumento para todos los $s$$1$$k$.

Ahora, supongo que algo de residuo $x \mod n$ no es asumida por cualquiera de las $x_j$. A continuación, nos fijamos en $x \mod k$ y encontrar que este residuo no es asumida por cualquiera de $x_1,x_2,\dotsc,x_k$ (de lo contrario, sería asumido por nuestro argumento anterior).

Pero nuestra hipótesis de inducción a los estados que los números de $x_1,x_2,\dotsc,x_k$ asume todos los residuos de $\mod k$, por lo que la hipótesis debe ser malo.

Por tanto, hemos establecido la inducción paso y así demostró la reclamación original.