¿Competencias como un sistema completo de residuos módulo $p$?

Question

Pregunta 1.

¿$0 < a < p$, Primer #% de %#% y $p$, es cierto que $\gcd(a,p-1)=1$ es un sistema completo de residuos módulo $0, 1, 2^a, ...,(p-1)^a$? ¿Si no es así, llevará a cabo una declaración similar?

Pregunta 2.

Me dijo trabaja para $p$, ¿alguien sabe una simple prueba de en este caso en particular?

Answer 1

Nota. Pregunta Original leer "$\gcd(a,p)=1$" en lugar de $\gcd(a,p-1)=1$".

Pregunta 1. No. Tenga en cuenta que la condición de $\gcd(a,p)=1$ es redundante: si $p$ es primo, entonces $\gcd(a,p)=1$ para todos los $a$, $0\lt a\lt p$. Si usted toma $a=p-1$, luego por Fermat Poco Teorema tiene que $r^a = r^{p-1}\equiv 1\pmod{p}$ por cada $r$ que no es divisible por $p$, por lo que su lista se compone de $0$ $1$ (el último,$p-1$) y sólo esos.

De manera más general: por cada apropiado divisor $d$$p-1$, existe un $r$, $1\lt r\lt p$, tal que $r^d\equiv 1\pmod{p}$ (esto se deduce del hecho de que el grupo multiplicativo de los números enteros modulo $p$ es cíclico de orden $p-1$). En particular, la lista no puede contener todos los residuos de clases.

Sin embargo, si $\gcd(a,p-1)=1$, entonces la respuesta es sí (se que lo que su condición estaba destinado a ser?) Para $p=2$ este es inmediata. Para $p$ extraño, deje $g$ ser una raíz primitiva módulo $p$. A continuación, $g^a$ también es una raíz primitiva módulo $p$ (desde su multiplicativo orden es $(p-1)/\gcd(a,p-1) = p-1$), lo que produce el resultado.

Pregunta 2. Es falso. Tome $p=7$. Entonces $$\begin{align*} 1^3 &\equiv 1 \pmod{7}\\ 2^3 &\equiv 1 \pmod{7}\\ 3^3 &\equiv 6\pmod{7}\\ 4^3 &\equiv 1\pmod{7}\\ 5^3 &\equiv 6\pmod{7}\\ 6^3 &\equiv 6\pmod{7} \end{align*}$$ tan sólo obtendrá $1$$6$. Su lista, a continuación, consta de $0$, tres copias de $1$, y tres copias de $6$, no incluye todos los residuos del sistema de modulo $p$. $3$ funciona para los números primos que son congruentes a $2$ modulo $3$$p=2$$p=3$, y eso es todo; no para cada primer que es congruente a $1$ modulo $3$.

Answer 2

1. Compruebe lo que sucede para $a=2$.
2. Un puntero a la prueba (que también muestra el camino para una prueba más general): para cada $p$ allí existe un «elemento primitivo» $g$ tal que $g^0,g^1,g^2,\dots,g^{p-1}$ es un sistema completo de residuos módulo p. por lo tanto, usted necesita sólo pregúntese cuál es $g^0,g^3,g^6,\dots,g^{3(p-1)}$.

Nota que como se dijo en los comentarios, necesitarás $\gcd(a,p-1)=1$ en orden para que funcione (tratar de ver donde esto aparece en la prueba).

Answer 3

% Toque $\rm\ (a,p-1)=1\ \Rightarrow\ \exists\: b,\ b\:a\:\equiv\: 1\pmod{p-1}\ \Rightarrow\ (n^b)^{\:a}\equiv\: n\pmod{p}\ $$\rm\:x\:\to\: x^{\:a}\:$es en