Usando la prueba de fermat para demostrar que 513 no es primo

Question

Me han pedido que utilice la prueba de Fermat para la base a=2 para demostrar que 513 no es un número primo.

¿Podría alguien explicar qué es exactamente una base en este contexto?

Gracias de antemano.

Answer 1

La teoría

El teorema de Fermat dice que si $n$ es primo, entonces $a^{n-1} \equiv 1\bmod n$ para todos $0 < a < n$ . Comprobar si esto es cierto para un $n$ se denomina Prueba de primalidad de Fermat . En este contexto, $a$ se denomina base . La prueba de primalidad de Fermat puede demostrar que $n$ es no un primo si encuentras una base que no supera la prueba de Fermat. Por desgracia, la prueba de Fermat no puede demostrar que $n$ es primo porque hay números que cumplen la prueba de Fermat para todas las bases pero no son primos; se llaman pseudoprimes .

El ejemplo

Como @lab bhattacharjee ha notado, $2^9=512\equiv-1\bmod 513 $ y así $2^{18}\equiv 1 \bmod 513$ .

Ahora, $512 = 28 \cdot 18 + 8$ y así $2^{512} \equiv 2^8 = 256 \not\equiv 1 \bmod 513$ .

Si $513$ fuera un primo, tendríamos $2^{512} \equiv 1 \bmod 513$ por el teorema de Fermat.

Answer 2

Por ejemplo

$$3^3\cdot19=513=0\pmod{513}\implies 3^{512}=(3^3)^{170}\cdot3^2\neq1\pmod{513}$$

ya que, como se muestra, $\;3^3\;$ es un divisor nulo, por lo que la prueba de Fermat falla aquí.

Utilización de la base $\;a=2\;$ : ya que

$$2^9=512=-1\pmod{513}\;\;\text{and also}\;\;512=9\cdot56+8\;,\;\;\text{we get}$$

$$2^{512}=(2^9)^{56}\cdot2^8=(-1)^{56}\cdot256=256\neq1\pmod{513}$$

Answer 3

Demostramos que $2^{512}\not\equiv1\pmod {513}$

$$2^{512}=2^{2^9}=\left(2^{2^5}\right)^{2^4}\equiv (481)^{2^4}\pmod{513}\equiv(-32)^{16}\pmod {513}$$

$$(-32)^{16}\equiv256\pmod{513}\ne 1\pmod{513}$$

Así $513$ no es un primo.