Que $n=2047$. Usando el hecho de que $3^{88} \equiv 1\pmod {n}, 3^{55} \equiv 1565\pmod {n}.$ mostrar que n es un número compuesto.

Question

Que $n=2047$.

Usando el hecho de que %#% $ de #% mostrar que n es un número compuesto.

Esta es una pregunta en un examen pasado que encuentro dificultad para responder. ¿Puede alguien ayudarme?

Answer 1

Si $n$ es primo, entonces

$3^{GCD(88,n-1)}\equiv 3^{22}\equiv 1\pmod n,3^{11}\equiv \pm 1 \pmod n,3^{55}\equiv \pm 1\neq 1565 \pmod n$

Answer 2

Una respuesta de la teoría del Grupo: si $\;n=2047\;$ es primo, entonces $\;\Bbb F_n^*\;$ es un grupo (cíclico), así que por el teorema de Lagrange

$$3^{88}=1\pmod n\implies 88\mid |\Bbb F_n^*|=n-1=2046$$

Pero, por supuesto, es falso que $\;88\mid 2046\;$...for ejemplo, es fácil ver que $\;2046=2\pmod 4\;$, que $\;88=0\pmod 4\;$.

Answer 3

Un toque rápido (que debe ser un comentario): si $n$ es primer, $x^{n}=x \pmod{n}$ % todos $x$.