Prueba de primalidad para números de la forma $2p+1$

Question

¿Es correcta esta prueba?

Reclamación

Sea $p \equiv 5 \pmod 6$ sea primo , entonces $2p+1$ es primo si $2p+1 \mid 3^p-1$ .

Prueba

Supongamos que $q=2p+1$ es primo. $q \equiv 11 \pmod{12}$ así que $3$ es un módulo cuadrático de residuos $q$ y se deduce que existe un número entero $n$ tal que $n^2 \equiv 3 \pmod{q}$ . Esto demuestra $3^p=3^{(q-1)/2} \equiv n^{q-1} \equiv 1 \pmod{q}$ mostrando $2p+1$ divide $3^p-1$ .

A la inversa $2p+1$ ser factor de $3^p-1$ . Supongamos que $2p+1$ es compuesto y $q$ sea su factor primo menor. Entonces $3^p \equiv 1 \pmod{q}$ y así tenemos $p=k \cdot \operatorname{ord_q(3)}$ para algún número entero $k$ . Desde $p$ es primo hay dos posibilidades $\operatorname{ord_q(3)} =1$ o $\operatorname{ord_q(3)} =p$ . La primera posibilidad no puede ser cierta porque $q$ es un número primo impar por lo que $\operatorname{ord_q(3)} =p$ . Por otra parte $\operatorname{ord_q(3)} \mid q-1$ Por lo tanto $p$ divide $q-1$ . Esto demuestra $q>p$ y se deduce $2p+1>q^2>p^2$ lo cual es contradictorio ya que $p>3$ Por lo tanto $2p+1$ es primo .

Q.E.D.

Answer 1

Podrías cambiar la última frase de tu prueba por:

Esto demuestra $q\ge p+1$ y se deduce que $2p+1\ge q^2\ge(p+1)^2=p^2+2p+1$ lo cual es una contradicción, ya que $p\gt0$ . Por lo tanto $2p+1$ es primo.

Answer 2

La desigualdad estricta $2p+1>q^2$ no se justifica explícitamente. Yo diría que tiene dos opciones:

• Menciona que $2p+1\equiv 3\pmod 4$ Así que $2p+1$ no es un cuadrado y la desigualdad es estricta.
• Sólo escribe $2p+1\ge q^2$ en su lugar.

Answer 3

Tu prueba es bastante correcta (las otras respuestas ya han mencionado cómo podrías mejorar la última línea), así que permíteme dar una prueba algo más fácil de la segunda parte. Sólo utiliza el teorema de Fermat-Euler y algunas propiedades de la $\phi$ función.

Sea $d$ sea el menor número entero positivo con: $$3^d\equiv 1\pmod {2p+1}$$ Si $2p+1\mid 3^p-1$ se deduce que $d\mid p$ y así $d=1$ o $d=p$ pero $2p+1>2$ y por lo tanto $d=p$ . Esto significa que $p\mid\phi(2p+1)$ y puesto que $\phi(2p+1),<2p+1$ tenemos $\phi(2p+1)=2p$ o $\phi(2p+1)=p$ . En el segundo caso tenemos $p\mid 2p+1$ lo cual es imposible. De ello se deduce que $\phi(2p+1)=2p$ y por lo tanto $2p+1$ es primo.