Evaluar $12^{3434322319}\mod7$

Question

Una forma instantánea de resolver esto $12^{3434322319}\mod7$ ?

He intentado $$12\mod7:5\mod7 \\ 12^2\mod7: 4\mod7\\ 12^3\mod7: 6\mod7\\ 12^4\mod7: 2\mod7\\ 12^5\mod7: 3\mod7\\ 12^6\mod7: 1\mod7 \\then \ the \ cycle \ repeats\\\\ 12^7\mod7: 5\mod7\\ 12^8\mod7: 4\mod7\\ ...$$ es un ciclo de 6, así que voy a calcular $$3434322319\mod6=1\mod6$$ así que $12^1\mod7 = 5\mod7$

Pero sé que hay la manera más rápida de resolver esto, tal vez usando el pequeño teorema de Fermat $$a^p\equiv a \ \mod p$$ de hecho $12\mod7 = 5\mod7$ pero ¿cómo sé si puedo aplicar esto? Quiero decir que cómo puedo saber que $3434322319=p$ para aplicar el teorema?

Answer 1

No necesitas saber que " $3434322319=p$ " o incluso que $3434322319$ es un número primo, que de hecho no lo es. ( $41$ es un factor).

Todo lo que necesitas saber es que $p=7$ es primo para que $a^7 \equiv a \pmod 7$ para todos los enteros $a$ por el pequeño teorema de Fermat. Por lo tanto, al hacer aritmética modular con módulo $7$ siempre se puede restar $6$ de los exponentes. (Esta es exactamente la observación que hizo por la inspección de la longitud del ciclo).

Como has dicho, $12\equiv 5\pmod 7$ y $3434322319\equiv 1\pmod 6$ para que el módulo $7$ tenemos $$ 12^{3434322319} \equiv 5^{3434322319} \equiv 5^{6k+1} \equiv 5^1 \equiv 5 \pmod 7. $$

Answer 2

Considere la posibilidad de aplicar Teorema de Euler-Fermat :

Primera comprobación $(12, 7) = 1$ para que podamos aplicarlo.

$$\varphi(7) = 6$$ $$12^6 \equiv 1 (7)$$

Ahora, queremos expresar 3434322319 de la siguiente forma: $$3434322319 = 6*k + r$$ donde r es el resto de la división entera por 6. Si se mira con más atención, se ve que $3434322319 = 3434322300 + 19$ .

$3434322300$ es par, por lo que es divisible por $2$ y la suma de sus dígitos es $24$ por lo que es divisible por $3$ también, por lo que el número entero es divisible por $6$ . Esto significa: $$3434322319 = 3434322300 + 19 \equiv 19 \equiv 1 (6)$$ Así que tenemos: $$3434322319 = 6*k + 1$$ Y luego $$12^{3434322319} = 12^{6k + 1} = (12^6)^{k}*12$$ Pero también sabemos que $$(12^6)^{k} \equiv 12^6 \equiv 1^k = 1(7)$$ Así que $$(12^6)^{k}*12 \equiv 1*12 = 12 \equiv 5(7)$$

Answer 3

No estoy seguro de cuánto más rápido necesitas que sea esto, para llamarlo una forma rápida... :-)

Todo lo que necesitas saber para acortar el cálculo es que $12^6\equiv 1 \bmod 7$ .

Entonces $12^{6k} \equiv (12^6)^k \equiv 1^k \equiv 1 \bmod 7$ para $k\in \mathbb N$ .

En particular, como usted observa, $3434322319 = 6k+1$ así que $12^{3434322319} \equiv 12^{6k+1} \equiv 12^{6k}\cdot 12^1 \equiv 12\bmod 7$ .

La aplicación de El pequeño teorema de Fermat depende de lo que el módulo es, el exponente aquí es solo algo que puedes ajustar usando ese hecho. Así que FLT le permite conocer una variación de la primera declaración - $12^7\equiv 12 \bmod 7$ - que también nos permite expulsar $6$ s en el exponente. Se puede utilizar el corolario de que $12^6\equiv 1 \bmod 7$ desde $12$ no es divisible por el módulo primo, $7$ .

[Nótese, por cierto, que $12\equiv 5 \bmod 7$ y $5\equiv 12 \bmod 7$ son ambos correctos y dicen lo mismo. Ciertamente, también sería legítimo decir de entrada que $12^{3434322319} \equiv 5^{3434322319} \bmod 7$ y proceder a partir de ahí].