Calcula: $x=2^{12} \pmod{13}$ en $\mathbb{Z}_{13}$

Question

Calcula: $x=2^{12} \pmod{13}$ en $\mathbb{Z}_{13}$ utilizando el Pequeño Teorema de Fermat.

Lo he intentado así, pero no sé si lo he hecho bien.

Desde el $\text{gcd}(2,13)=1$ podemos utilizar a Fermat que dice que

$$2^{12}\equiv1\pmod{13}$$

Así que podemos escribir:

$$x \equiv 2^{12}\equiv1\pmod{13}$$

Así, la solución será $1 \pmod{13}$ ?

Answer 1

Quizá valga la pena señalar que su solución es fácil de comprobar en este caso: vale la pena memorizar sus potencias de $2$ o, al menos, algunas específicas (por ejemplo $2^{10}$ ). En este caso, $2^{12} = 4,096$ , lo que deja un remanente de $1$ cuando se divide por $13$ . En este caso, se utiliza eso para verificar que se está en lo cierto, pero es comprensible que este (a) no es el método que se pretende utilizar y (b) podría no ser factible para el caso general.

---

En cualquier caso, recordemos El pequeño teorema de Fermat :

El pequeño teorema de Fermat: Dejemos que $p$ sea primo, y $a$ un número entero. Entonces $a^p - a$ es un múltiplo de $p$ . Esto se puede expresar simbólicamente de varias maneras: a saber:

$$p | (a^p - a) \;\;\;\;\;\;\;\;\;\; \frac{a^p - a}{p} = k \in \mathbb{Z} \;\;\;\;\;\;\;\;\;\; a^p \equiv a \pmod p$$

Corolario/Implicación: Si $p \not | a$ , entonces esto implica $a^{p-1} - 1$ es un múltiplo de $p$ . De nuevo, formulaciones equivalentes:

$$p | (a^{p-1} - 1) \;\;\;\;\;\;\;\;\;\; \frac{a^{p-1} - 1}{p} = k \in \mathbb{Z} \;\;\;\;\;\;\;\;\;\; a^{p-1} \equiv 1 \pmod p$$

En este problema utilizamos esta última forma del Pequeño Teorema de Fermat, con $a = 2, p = 13$ .

Entonces, por el Pequeño Teorema de Fermat, ya que $p = 13$ es un primo que divide $a = 2$ podemos afirmar lo siguiente:

$$2^{13-1} \equiv 1 \pmod {13} \iff 2^{12} \equiv 1 \pmod {13}$$

Cuando $\mathbb{Z}_{13}$ denota los enteros mod $13$ entonces está claro que $1 \in \mathbb{Z}_{13}$ y por lo tanto $x = 1$ en este problema.

---

Tu demostración es más o menos correcta, pero el Pequeño Teorema de Fermat no se utiliza correctamente. Teniendo $gcd(2,13) = 1$ no es condición suficiente para el corolario del Pequeño Teorema de Fermat: uno de ellos debe ser también primo. (Entonces $gcd(a,p) = 1$ implicaría la condición necesaria de no divisibilidad). A modo de ejemplo, $gcd(15, 14) = 1$ pero ninguno de ellos es primo, lo que significa que el Pequeño Teorema de Fermat no podría utilizarse si $a,p$ cada uno era uno de $14,15$ .

Answer 2

El pequeño teorema de Fermat dice $a^{12}\cong1\pmod{13}$ para $a\neq0\pmod{13}$ . Así, $2^{12}\cong1\pmod{13}$ . Así que $x=1$ .