Primero le damos un número de la teoría de la prueba para la dirección en la que no tratar. Después de eso, le damos un par de pruebas para la otra dirección. Estos son similares a la prueba de que usted describe, pero llenar el vacío mencionado en el comentario de @Jyrki Lahtonen.
Tanto como sea posible, su notación es utilizada. La primalidad de $p$ está en ninguna parte de usa, y no es necesario. No creo que la asunción de primalidad permite para cualquier simplificación.
Supongamos que $q \not \equiv 1 \pmod{p}$, e $a^p \equiv b^p \pmod{q}$. Vamos a mostrar que el $a\equiv b \pmod{q}$. Podemos suponer que ni $a$ ni $b$ es congruente a $0$ modulo $q$.
Desde $q\not\equiv 1 \pmod{p}$, los números de $q-1$ $p$ son relativamente primos. Por el Teorema de Bezout existen enteros $m$, $n$ tal que $m(q-1)+np=1$. Así
$$a=a^1=a^{m(q-1)+np}=a^{(q-1)m}a^{pn}\qquad\qquad\text{(Equation $1$)}$$
Por el Teorema de Fermat, $a^{(q-1)m} \equiv 1\pmod{q}$.
A partir de la Ecuación de $1$, llegamos a la conclusión de que
$$a\equiv (a^p)^n \pmod{q}.$$
Del mismo modo,
$$b \equiv (b^p)^n \pmod{q}.$$
De ello se sigue que si $a^p \equiv b^p \pmod{q}$$a \equiv b \pmod{q}$.
Nota: Los números enteros $m$ $n$ no son ambos positivos. Como de costumbre, podemos interpretar una potencia negativa como la inversa del modulo $q$ de la correspondiente potencia positiva.
La otra dirección: Supongamos que $q \equiv 1 \pmod{p}$. Nos muestran que no existen $a$, $b$ que son incongruentes modulo $q$ tal que $a^p \equiv b^p \pmod{q}$. Como en su prueba, vamos a $pk=q-1$.
Deje $b=1$. Nos muestran que no existe $a$ no congruentes a $1$ modulo $q$ tal que $a^p \equiv 1^p \pmod{q}$.
Por el Teorema de Fermat, los candidatos naturales para $a$ forma $c^k$, $c$ no congruentes a $0$ modulo $q$. Esto es debido a que
$(c^k)^p =c^{kp}=c^{q-1}\equiv 1 \pmod{p}$.
Así que todo lo que tenemos que hacer es demostrar que no existe $c$ no congruentes a $0$ tal que $c^k$ no es congruente a $1$ modulo $q$.
(yo): Si se nos permite utilizar un poco de información acerca de los campos, esto es inmediata. Para la ecuación de $x^k=1$ tiene más de $k$ soluciones en los enteros modulo $q$. Desde $k \le (q-1)/2$, de hecho hay muchos $c$ con la propiedad deseada.
Si no se nos permite utilizar ese hecho, se puede probar . El hecho de que en nuestro campo (o de hecho cualquier campo) un polinomio de grado positivo $k$ tiene más de $k$ raíces puede ser demostrado por inducción sobre el grado. Si no queremos usar el campo de la teoría de la lengua, la inducción paso es que si $r$ es una raíz modulo $q$ del polinomio $P(x)$, entonces no es un polinomio $Q(x)$ con coeficientes enteros tales que $P(x)\equiv (x-r)Q(x) \pmod{q}$. La prueba es esencialmente la misma que la de la escuela secundaria de la prueba del Teorema del Resto. Divida $P(x)$ $x-r$ en la forma habitual, y demostrar que el resto es congruente a $0$ modulo $q$ poniendo $x=r$.
(ii): Si se nos permite utilizar el hecho de que $q$ tiene una primitiva de la raíz, es decir, en el grupo de teoría de términos, que el grupo multiplicativo modulo $q$ es cíclica, es decir, cualquier raíz primitiva de $q$ puede ser tomado como $c$.