Utilizando el Pequeño Teorema de Fermats para demostrar $2^{17} -1$ es primo

Question

Demuestre que $n = 2^{17} - 1$ es primo utilizando el Pequeño Teorema de Fermat $2^{p-1} \equiv 1 \mod p$ para cualquier $p$ dividiendo $n$ .

Dije, que por FLT, obtenemos $2^{16} \equiv 1 \mod 17$ y podemos ver que $1 \equiv 1 \mod 17$ y así obtenemos

$$n = 1 - 1 = 0 \mod 17$$

pero entonces todo esto me dice que $n = 17k$ para algunos $k$ y no que sea de primera. ¿Dónde me he equivocado?

Answer 1

Si $p|n$ es primo, entonces $2^{p-1}\equiv 1\pmod p$ pero también $2^{17}\equiv 1\pmod p$ , por lo tanto si $k=(p-1)a+17b$ entonces $2^k\equiv 1\pmod p$ . Si $p-1$ es no un múltiplo de $17$ podemos encontrar una combinación lineal con $k=a(p-1)+b17=1$ es decir $2\equiv 1\pmod p$ contradicción. Por lo tanto $p\equiv1\pmod{17}$ para cualquier $p|n$ . Ahora usa divisiones de prueba con primos de la forma $p=17m+1<\sqrt n\approx 362$ es decir $p=103$ , $137$ , $239$ y $307$ .