Si [math] p [/ math] es un número primo, ¿cómo mostrarías que existe un primo [math] q [/ math] tal que [math] q [/ math] no divide [math] n ^ pp [/ math] para cualquier número entero [math] n [/ math]?

Answer 1

Alguna motivación:

Este problema se planteó como la última pregunta en la Olimpiada Internacional de Matemáticas (OMI) en 2003, así que espera que sea difícil, ¡no te avergüences si no puedes resolverlo en un par de horas! Incluso si ha analizado la solución, aún podría preguntarse: “Sí, puedo ver cómo esto resuelve el problema, pero ¿cómo se llega a tal solución en primer lugar? ¿Qué pasa dentro de la cabeza de los chicos que lo resuelven? ”. Por lo tanto, trataré de motivar los pasos que conducen a la solución (y algunos que no lo hacen), pero no espere demasiado: el problema parece bastante artificial …

Bien, entonces el problema nos pide que encontremos una [matemática] q [/ matemática] tal que [matemática] n ^ p \ equiv p \ pmod {q} [/ matemática] no se cumple para ningún entero [matemática] n [ /matemáticas]. Esto es equivalente a probar que existe un primo tal que el polinomio [math] x ^ pp [/ math] es un módulo irreducible este primo, y con esto ganamos confianza en la declaración: [math] x ^ pp [/ math] es claramente irreducible sobre los enteros, por lo que sería extraño que fuera modulable cualquier primo!

Sin embargo, no parece que este tipo de pensamiento conduzca a una solución, por lo que damos un par de pasos hacia atrás e intentamos obtener una visión general. En un nivel estratégico, la solución puede ser una construcción explícita (algo así como [matemática] q = 2p + 1 [/ matemática]), una prueba por contradicción (suponga que la afirmación es falsa y deduzca una contradicción a partir de esta suposición), o podríamos tratar de ver qué haría que un [matemático] q [/ matemático] funcionara o no y optar por un enfoque no constructivo. Esto último parece muy prometedor, ya que todavía no tenemos idea de cómo construir [matemáticas] q [/ matemáticas], y la contradicción parece difícil de hacer.

Entonces intentemos jugar con aritmética modular en su lugar; primos y exponentes funcionan bien en esta configuración. Como vimos anteriormente, el problema ahora se lee [matemática] n ^ p \ equiv p \ pmod {q} [/ matemática], pero esto no es muy útil, principalmente porque no tenemos idea de cuándo los poderes evalúan a [matemática] p \ bmod q [/ math]. El mejor residuo cuando se trata de multiplicación es [matemática] 1 [/ matemática], así que elevemos ambos lados a la potencia de [matemática] q-1 [/ matemática] – espera, podemos hacerlo mejor eligiendo [matemática] \ operatorname {ord} _q (n) [/ math] en su lugar. Llame a este número [math] d [/ math] por brevedad:

[matemáticas] \ displaystyle n ^ {p \ cdot d} \ equiv p ^ d \ iff p ^ d \ equiv 1 \ pmod {q}, [/ math]

que se ve mejor ¡Pero todavía nos encontramos con un problema! Como [math] d [/ math] es el orden de [math] n [/ math], y [math] n [/ math] era arbitrario, significa que [math] d = q-1 [/ math] cuando [math] n [/ math] es un módulo raíz primitivo [math] q [/ math] – haciendo que la ecuación anterior sea trivial. La única forma de evitar este obstáculo es hacer que [math] q-1 [/ math] sea un múltiplo de [math] p [/ math], y elegir [math] d = \ frac {\ operatorname {ord} _q ( n)} {p} [/ matemáticas]. Tenga en cuenta que esto implica que [math] q [/ math] está en la forma [math] q = kp + 1 [/ math], y en este caso hemos terminado si [math] \ operatorname {ord} _q (p) = q-1 [/ matemáticas]. ¿Cuándo es este el caso? (En este punto, probablemente valga la pena mencionar que hay infinitos números primos en la forma [math] kp + 1 [/ math] como consecuencia del teorema de Dirichlet sobre números primos en progresiones aritméticas).

Jugando un poco más, parece difícil señalar un caso específico en el que esto sea cierto (¿se da cuenta de una tendencia aquí?), Pero al mirarlo de manera más general, vemos que nuestro enfoque requiere que comprendamos los factores primos de expresiones como [ matemáticas] p ^ r-1 [/ matemáticas] mejor. Si conoces alguna teoría sobre polinomios ciclotómicos (deberías antes de intentar preguntas como estas) y sus principales divisores, es posible que puedas extraer algo de ella, pero al menos para mí, se convirtió en un callejón sin salida. Estamos atascados!

Retrocedemos un paso y consideramos la situación: [matemáticas] q [/ matemáticas] es probablemente congruente con [matemáticas] 1 [/ matemáticas] módulo [matemáticas] p [/ matemáticas], y la aritmética modular parece funcionar, pero nosotros Necesitamos un mejor enfoque que el que teníamos. Como mencioné anteriormente, para resolver estos problemas solo tiene que intentarlo, intentarlo, intentarlo nuevamente, dejarse mamar e intentar nuevamente. ¡Jugar!

Ahora voy a presentar la solución, y aunque realmente intenté motivar el último paso de este problema, tengo que admitir que no pude encontrar un camino claro de pistas que condujeran al paso final. Sin embargo, dada la discusión anterior, no es irracional pensar en ello; solo requiere una mente creativa y, tal vez, un poco de suerte.

Solución

Deje que [math] q [/ math] sea un divisor primo de

[matemáticas] \ displaystyle \ frac {p ^ p-1} {p-1} [/ matemáticas]

eso no es congruente con [math] 1 \ bmod p ^ 2 [/ math]. Esto es posible porque la expresión anterior es congruente con [math] \ frac {-1} {p-1} \ equiv \ frac {p ^ 2-1} {p-1} \ equiv p + 1 \ pmod {p ^ 2} [/ matemáticas]. Como [math] n ^ p \ equiv p [/ math], obtenemos

[matemáticas] \ displaystyle n ^ {p ^ 2} \ equiv p ^ p \ equiv 1 \ equiv n ^ {q-1} \ pmod {q}, [/ math]

lo que implica [matemáticas] n ^ {\ gcd (p ^ 2, q-1)} \ equiv 1 \ implica n ^ p \ equiv 1 \ pmod {q} [/ matemáticas], y hemos terminado trivialmente. [matemáticas] \ blacksquare [/ matemáticas]

Inteligente, ¿no es así?