Cómo encontrar el resto cuando [matemática] 3 ^ {12} + 5 ^ {12} [/ matemática] se divide por [matemática] 13 [/ matemática]

Answer 1

La solución de Nikhil Tilak está perfectamente bien para este problema; sin embargo, para números más grandes, la aritmética modular y el pequeño teorema de Fermat se vuelven útiles.

La aritmética modular se ocupa de los restos. Escribir [matemáticas] 7 \ equiv 2 \ pmod 5 [/ matemáticas] (léase “7 es congruente con 2 módulo 5”) significa que 7 tiene el mismo resto que 2 cuando se divide entre 5. Entonces, en general, [matemáticas] a \ equiv b \ pmod {n} [/ math] para enteros [math] a [/ math] y [math] b [/ math] y un entero positivo [math] n [/ math] significa que [math] ab [/ math] es divisible por [matemáticas] n [/ matemáticas]. El residuo de [math] a [/ math] modulo [math] n [/ math] es el más pequeño positivo [math] b [/ math] que aún satisface la congruencia.

(Nota al margen: la función restante en ciencias de la computación se denota por “%”, y a% b devuelve el residuo de un mod b.)

Hay algunas cosas convenientes sobre aritmética modular:
Suma, resta, multiplicación:
Si [matemática] a_1 \ equiv b_1 \ pmod {n} [/ matemática] y [matemática] a_2 \ equiv b_2 \ pmod {n} [/ matemática] entonces

• [matemáticas] a_1 + a_2 \ equiv b_1 + b_2 \ pmod {n} [/ matemáticas]
• [matemáticas] a_1-a_2 \ equiv b_1-b_2 \ pmod {n} [/ matemáticas] [matemáticas] [/ matemáticas]
• [matemáticas] a_ {1} a_ {2} \ equiv b_ {1} b_ {2} \ pmod {n} [/ matemáticas]

(Pruebe algunos ejemplos por sí mismo si no lo cree)

El pequeño teorema de Fermat establece que si [matemática] p [/ matemática] es un número primo y para cualquier número entero [matemática] a [/ matemática] no divisible por [matemática] p [/ matemática], [matemática] a ^ {p- 1} \ equiv 1 \ pmod {p} [/ math]. (Este teorema, que no debe confundirse con el último teorema de Fermat, es bastante fácil de probar. Búscalo, tiene bastantes argumentos claros).

Entonces, notamos que hey, [matemáticas] 13 [/ matemáticas] es primo, [matemáticas] 12 = 13-1 [/ matemáticas], y ni [matemáticas] 3 [/ matemáticas] ni [matemáticas] 5 [/ matemáticas] son divisible por [matemáticas] p [/ matemáticas]. Y usando el pequeño teorema de Fermat, obtenemos [matemáticas] 3 ^ {12} \ equiv 1 \ pmod {13} [/ matemáticas] y [matemáticas] 5 ^ {12} \ equiv 1 \ pmod {13} [/ matemáticas]. Usando nuestras viejas reglas de aritmética modular obtenemos [matemáticas] 2 ^ {12} + 5 ^ {12} \ equiv 1 + 1 \ equiv 2 \ pmod {13} [/ matemáticas]. ¡Hurra!

Answer 2

2

Rem [3 ^ 12/13] = Rem [27 ^ 4/13] = Rem [1 ^ 4/13] = 1
Rem [5 ^ 12/13] = Rem [25 ^ 6/13] = Rem [(-1) ^ 6/13] = 1

Rem [(3 ^ 12 + 5 ^ 12) / 13] = 1 + 1 = 2

Answer 3

El pequeño teorema de Fermat: Para cualquier primo [matemático] p [/ matemático], y un entero dado [matemático] a [/ matemático], tenemos

[matemáticas] a ^ {p-1} \ equiv 1 \ mod p \ tag {*} [/ matemáticas]

---

[matemáticas] (3 ^ {12} + 5 ^ {12}) \ mod 13 [/ matemáticas]

[matemáticas] = 3 ^ {13–1} (\ mod 13) + 5 ^ {13–1} (\ mod 13) [/ matemáticas]

[matemáticas] = 1 + 1 [/ matemáticas]

[matemáticas] = 2 [/ matemáticas]

Fácil lo hace.

Answer 4

Usa el pequeño teorema de Fermat, [1]

[matemática] \ Grande a ^ p \ equiv a \ mod p, \ text {para todos los principales p y enteros a} [/ matemática]

---

De eso podríamos obtener,

[math] \ Large a ^ {p-1} \ equiv 1 \ mod p, \ text {si p no divide a} [/ math]

---

[matemáticas] (3 ^ {12} + 5 ^ {12}) \ mod 13 [/ matemáticas]

[matemáticas] = 3 ^ {13-1} \ mod 13 + 5 ^ {13-1} \ mod 13 [/ matemáticas]

[matemáticas] = 1 + 1 = 2 [/ matemáticas]

Notas al pie

[1] El pequeño teorema de Fermat – Wikipedia

Answer 5

3 ^ 12 = 27 ^ 4 = (13 * 2 + 1) ^ 4 por lo tanto, el resto al dividir entre 13 es 1.
5 ^ 12 = 25 ^ 6 = (13 * 2-1) ^ 6. por lo tanto, el resto cuando se divide por 13 es 1.
Por lo tanto, el resto total es 2.