¿Por qué el $\{1\cdot a\! \! \pmod p, 2\cdot a\! \! \pmod p,\ldots, (p-1)\cdot a\! \! \pmod p\}$ $= \{1, 2,\ldots, p-1\}$ cuando $a$ y $p$ son coprimos?

Question

¿Por qué es que $\{1\cdot a \pmod p, 2\cdot a \pmod p,\ldots, (p-1)\cdot a \pmod p\} = \{1, 2,\ldots, p-1\}$ (aunque en un orden diferente) cuando a y p son coprimes?

Yo no puedo entender esto y he estado golpeando mi cabeza durante todo el fin de semana.

Con el google he encontrado mención de Fermat Poco Teorema (por ejemplo aquí), pero no puedo ver cómo me ayuda.

He verificado con la mano, parece perfectamente creíble para mí (sobre todo porque me encuentro a mí mismo pensando en la forma en que el círculo de quintas partes de obras), pero no puedo encontrar una buena prueba.

Cualquier ayuda, bonita por favor?

Muchas gracias.

P. S.: Perdón por mi inglés. Yo soy de la tierra de la pizza y mandolinas.

Answer 1

Supongamos $ra$ $sa$ son los mismos, modulo $p$. A continuación, $sa-ra$ es un múltiplo de a $p$. Por lo $(s-r)a$ es un múltiplo de a $p$. Pero por hipótesis de $a$ $p$ son coprime, por lo $s-r$ es un múltiplo de a $p$. Pero si $r$ $s$ tienen entre 1 y $p-1$, inclusive, a $s-r$ no puede ser un múltiplo de $p$ si $r=s$.

Esto demuestra que todos los números en la primera parte de su pregunta son diferentes. Desde cero no aparece en el set, y desde allí se $p-1$ números de la serie, que debe ser el mismo que el de los números en el segundo set en su pregunta.

Answer 2

Si no fuera el caso, eso significaría que usted puede volver al mismo lugar en pasos de $n\lt p$de % de $a$; es decir, tendríamos $na=kp$ % entero $k$. $a$ Y $p$ son coprimos, para todos los factores de $p$de % de $n$, que contradice $n\lt p$.

Answer 3

Esto puede ser interpretado como un grupo de teoría de resultado: el conjunto de los números coprime a $n$ forma un grupo bajo la multiplicación modulo $n$. La parte más difícil de esto es mostrar que existen inversos. Esto se deduce a partir del teorema de Bézout, que establece que para cualquier $a$ $n$ existe $x$ $y$ coprime tal que $ax + yn = \gcd(a,n)$. A partir de esto podemos ver que si $a$ $n$ son coprime, es decir,$\gcd(a,n)=1$, $ax$ $1$ mod $n$, e $x$ debe ser coprime a $n$ (debido a $\gcd(r,s)$ divide cualquier combinación de $r$$s$, y aquí tenemos una combinación de $x$ y $n$ que da 1), por lo $a$ tiene un inverso multiplicativo modulo $n$.

De todos modos, una vez que has conseguido que el conjunto de los números coprime a $n$ forma un grupo bajo la multiplicación modulo $n$, que es esencialmente equivalente a decir que el mapa de "multiplicar por $a$" es un bijection modulo $n$. Eso es esencialmente el mismo que el de su declaración original.

(Tecnicismo: se demostró que multiplicar por$a$ es invertible en el grupo de números de coprime a $n$ modulo $n$, cuando en realidad lo que quería era ser invertible en el conjunto de los números modulo $n$, pero no es difícil ver que el argumento anterior se extiende a ese caso. Supongo que lo que realmente estoy haciendo es mostrar que $a$ es una unidad en el anillo de los números modulo $n$, y el grupo que he mencionado es el grupo de unidades de ese anillo).

Esta respuesta se utiliza algo más de peso pesado de la maquinaria de la necesaria, pero creo que es una buena manera de mirar el resultado.