Demostrar que $n$ debe ser un primo.

Question

Aquí está la pregunta completa:

Supongamos que $n=2^{m}h+1$, donde m es un entero y $h$ es un entero positivo impar menor que $2^{m}$. Supongamos que existe un número entero $a$ tal que $a^{\frac{1}{2}(n-1)}\equiv -1 (mod \space n)$. Demostrar que $n$ debe ser un primo.

[Sugerencia: primero que si $p$ es cualquier divisor primo de $n$ $ord_{p}(a)$ debe ser un divisor de a $n-1=2^{m}k$ y no es un divisor de a $\frac{1}{2}(n-1)=2^{m-1}h$, y el uso de Fermat Poco Teorema deducir que $p\equiv1 (mod \space 2^{m})$.]

Este es uno de los más difíciles de la práctica de un examen de preguntas de mi clase, y he estado pensando sobre este tema hace unos días y creo que estoy cerca, pero sólo necesito un poco de ayuda. Estoy tratando de seguir la pista tanto como puedo. Aquí es lo que tengo hasta ahora:

Suponga $p$ es un divisor primo de n.

Desde $p|n$ $n|a^{\frac{1}{2}(n-1)}+1 = a^{2^{m-1}h}+1$

$\implies p\nmid a$

Entonces por el Teorema de Fermat,

$a^{p-1}\equiv 1 (mod \space p) $ y tenemos que $p|a^{\frac{1}{2}(n-1)}+1 = a^{2^{m-1}h}+1$

$\implies a^{\frac{1}{2}(n-1)}\equiv -1 (mod \space p)$ $\implies a^{(n-1)}\equiv 1 (mod \space p)$ (después de cuadrar ambos lados)

Así que tenemos que $p | a^{p-1}-1$ $p | a^{n-1}-1$

$\implies a^{p-1}\equiv a^{n-1} \equiv 1 (mod \space p)$

(aquí es donde yo estoy un poco confusa. Soy una clase de sólo asumiendo $ord_p(a) = p-1$)

por lo $(p-1)|(n-1) = 2^{m}h$ (también, no muy seguro de eso?)

De ello se desprende que $2^{m}|(p-1)$ es decir $(p-1) = 2^{m}h$

Así $n = (p-1)+1$ $\implies n$ debe ser un primo, ya que nuestra hipótesis era que $p$ es un primo.

Sé que no he utilizado la sugerencia exactamente y también no he hecho uso de el hecho de que $h$ es un impar menor que $2^{m}$.

Si alguien me puede ayudar, sería muy apreciada!!

Answer 1

Usted no puede simplemente asumir $\operatorname{ord}_p(a) = p-1$. Sin embargo, se le da

$$a^{\frac12(n-1)} \equiv -1 \pmod{n} \Rightarrow a^{\frac12(n-1)} \equiv -1 \pmod{p} \Rightarrow a^{n-1} \equiv 1 \pmod{p}.$$

Desde $\operatorname{ord}_p(a)$ es el número positivo menor que $k$$a^k \equiv 1 \pmod{p}$, se puede deducir que el $\operatorname{ord}_p(a) \mid n-1$.

Deje $p = 2^s\cdot u + 1$ $u$ impar. A continuación,$a^{p-1} = a^{2^su} \equiv 1 \pmod{p}$. Pero $a^{2^{m-1}h} \equiv -1 \pmod{p}$, por lo tanto $(a^{2^{m-1}u})^h \equiv -1 \pmod{p}$, y por lo tanto $s \geqslant m$, lo $p \equiv 1 \pmod{2^m}$, por lo tanto $p \geqslant 2^m + 1$.

Ahora, si $n$ no prime, habría al menos dos factores primos, todos de los cuales son $\equiv 1 \pmod{2^m}$, y por lo tanto el producto de dos números primos serían $\geqslant (2^m+1)^2$.

---

Más exposición detallada:

Tenemos un entero $n = 2^m\cdot h +1$ $0 < h < 2^m$ impar, y estamos seguros de la existencia de un número entero $a$$a^{\frac12(n-1)} \equiv -1 \pmod{n}$.

Para mostrar que $n$ es primo, tomamos cualquier prime $p$ dividiendo $n$ - un primer existe, ya que tenemos $1 < 2^m$, por lo tanto $1 < n$ $0 < h < 2^m$ - y, a continuación, mostrar que $p = n$. Desde $m \geqslant 1$, se deduce que el $n$ es impar, y por lo tanto también lo es $p$. Escribir $p = 2^s\cdot u + 1$ $u$ impar. Desde asunción

$$n \mid \left(a^{\frac12(n-1)} +1\right),$$

y $p$ divide $n$, también tenemos

$$p \mid \left(a^{\frac12(n-1)} +1\right) \iff a^{\frac12(n-1)} \equiv -1 \pmod{p}.$$

En particular, $a$ no es un múltiplo de a $p$. Por el teorema de Fermat, sabemos que $\operatorname{ord}_p(a) \mid (p-1)$, por lo tanto

$$a^{p-1} = a^{2^s\cdot u} \equiv 1 \pmod{p}.$$

Pero $\frac12(n-1) = 2^{m-1}h$, y

$$\left(a^{2^{m-1}u}\right)^h = \left(a^{2^{m-1}h}\right)^u \equiv (-1)^u \equiv -1 \pmod{p},$$

por lo $a^{2^{m-1}u} \not\equiv 1 \pmod{p}$, pero $a^{2^su} \equiv 1 \pmod{p}$, por lo tanto $s > m-1$, o, equivalentemente,$s \geqslant m$.

Así tenemos a $2^m \mid 2^s\cdot u = (p-1)$. En particular, $p \geqslant 2^m + 1$. Pero

$$\left(2^m+1\right)^2 = 2^{m}\cdot 2^m + 2\cdot 2^m + 1 = 2^m\cdot h + 1 + \left(2^m(2^m-h) +2\cdot 2^m\right) > 2^mh+1 = n,$$

por lo $p > \sqrt{n}$.

Si $n$ fueron compuestos, habría al menos un factor primo $\leqslant \sqrt{n}$, pero acabamos de ver que todos los factores primos de a$n$$> \sqrt{n}$, por lo tanto $n$ debe ser un primo.