6 votos

Número de $k^p \bmod q$ clases $q\%p > 1$

Quiero mostrar que cuando se $p, q$ son primos, $k^p\bmod q$ toma en $q-1$ valores distintos (como $k$ rangos de números enteros positivos) si y sólo si $q \not\equiv 1 \pmod p$. (Es fácil comprobar esto de cómputo para los pequeños números primos, por ejemplo,$p < 100$$q < 10000$.) De manera más compacta, la demanda es este: Para todos los números primos p, q, $|S(p,q)| = q-1$ fib $q \not\equiv 1 \pmod p$ donde $S(p,q)=\{ K(p,q,a): a \in\mathbb{Z}^+\}$ $K(p,q,a)$ es la equivalencia de la clase $a^p \bmod q$.

Puedo mostrar el "sólo si" la parte fácil (pero crudamente) [Actualización: y de forma incorrecta, como se señaló en Jyrki Lahtonen del comentario] para $q>4$ mediante el teorema de Euler señalando que $4^j-1$ nunca es el primer si $j>1$, por lo que $q \equiv 1 \pmod p \implica q>p \implica \existe k>1$ que $\phi(q) = q-1 = k\cdot p$, por lo tanto (teniendo en $x=4^k$) tenemos $\exists x\not\equiv 1$ tal que $x^p=4^{k\cdot p}=4^{q-1}\equiv 1$, lo que asegura que $|S(p,q)| < q-1$.

Para el "si" de la parte he estado tratando de aplicar del teorema de Lagrange para un grupo con la operación $\circ$ $a\circ b \equiv a^p\cdot b^p\bmod q$ que es fácil demostrar que está cerrado y asociativo con la identidad y a la inversa, pero han de ir en círculos en esta parte.

¿Qué es un mejor método para probar la "sólo si"?. ¿Qué es una dirección mejor para el "si"?.

6voto

Oli Puntos 89

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$.

4voto

Sugerencia (si usted tiene cubiertos grupo homomorphisms): Al $p$ no es un factor de $q-1$,$(q-1,p)=1$. Por Lagrange del teorema no hay elementos de orden $p$ en el grupo multiplicativo $G=\mathbf{Z}_q^*$. Por lo tanto, la homomorphism $f:x\mapsto x^p$ $G$ a sí mismo es inyectiva (comprobar que este es un homomorphism). Como $G$ es finito, a continuación, $f$ también debe ser ...

Hint2 (en el otro sentido, dado que theremay ser un problema): Si el libro ha cubierto el hecho de que $\mathbf{Z}_q^*$ es un grupo cíclico (o $\mathbf{Z}_q$ es un campo), se puede utilizar para mostrar que la asignación no es surjective, al $p\mid q-1$.

1voto

user772913 Puntos 56

Aquí es otra manera de demostrar el teorema, formulado como un teorema en el libro de la Teoría de números Para los principiantes, por A. Weil.

Teorema XI.Dejo $p$ ser un primo, $m$ un entero >0, y â^un entero primer a $p$; poner a $d=(m,p-1)$. Entonces la congruencia $x^m \equiv a\pmod p$ ha $d$ soluciones modulo $p$ o ninguna solución; tiene una solución si y sólo si la congruencia $y^d \equiv a\pmod p$ tiene una solución; esto es así, si y sólo si $a^{(p-1)/d} \equiv 1\pmod p$, y hay exactamente $(p-1)/d$ estos valores de $a$ modulo $p$.

A excepción de algunos cambios de las notaciones, este teorema puede ser visto como una descripción más detallada de las situaciones en cuestión, por el solo uso de la teoría de grupos(por lo tanto, es para los principiantes). En particular, la última afirmación es, precisamente, lo que el OP quería demostrar.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X