¿Cuál será el resto cuando [matemáticas] 6457 ^ {({76} ^ {57})} [/ matemáticas] se divide por [matemáticas] 23 [/ matemáticas]?

Answer 1

La respuesta de Amitabha Tripathi a ¿Cuál será el resto cuando [matemática] 6457 ^ {({76} ^ {57})} [/ matemática] se divide por [matemática] 23 [/ matemática]?
El enfoque de Amitabha Sir es mucho mejor que la respuesta mía.

---

El resto es [matemáticas] 4 [/ matemáticas]. Veamos cómo llegamos a la solución. [Matemáticas] [/ matemáticas]

[matemáticas] 23 [/ matemáticas] es un número primo.
Utilice ciegamente el pequeño teorema de Fermat que establece cualquier número primo [matemático] p [/ matemático] y cualquier número [matemático] a [/ matemático] no un múltiplo de [matemático] p, [/ matemático] que tenemos

[matemática] a ^ {(p-1)} [/ matemática] [matemática] mod [/ matemática] [matemática] p [/ matemática] [matemática] = [/ matemática] [matemática] 1 [/ matemática]

Ahora, [matemática] 6457 [/ matemática] [matemática] mod [/ matemática] [matemática] 23 [/ matemática] [matemática] = [/ matemática] [matemática] 17. [/ matemática] La pregunta se reduce a [matemática ] 17 ^ {({76} ^ {57})} [/ math] mod [math] 23. [/ Math]

Ahora, [matemáticas] 17 ^ {22} [/ matemáticas] = [matemáticas] 1 [/ matemáticas] [matemáticas] mod [/ matemáticas] [matemáticas] 23 [/ matemáticas]

Tenemos que escribir [matemáticas] 76 ^ {57} [/ matemáticas] en forma de [matemáticas] 22n + k [/ matemáticas] donde [matemáticas] 0 <= k <= 22. [/ Matemáticas] Entonces, lo requerido la respuesta será [matemática] 17 ^ {22 * n + k} [/ matemática] mod [matemática] 17 [/ matemática] que se reduce a [matemática] 17 ^ k [/ matemática] mod [matemática] 23. [/ matemática ]

Ahora, encontramos [matemáticas] k [/ matemáticas] donde [matemáticas] k [/ matemáticas] [matemáticas] = [/ matemáticas] [matemáticas] 76 ^ {57} [/ matemáticas] [matemáticas] mod [/ matemáticas] [ matemáticas] 22 [/ matemáticas]

[matemáticas] 76 ^ {57} [/ matemáticas] [matemáticas] mod [/ matemáticas] [matemáticas] 22 = 2 [/ matemáticas] [matemáticas] * [/ matemáticas] [matemáticas] 2 ^ {56} [/ matemáticas] [matemática] * [/ matemática] [matemática] 38 [/ matemática] [matemática] ^ {57} [/ matemática] [matemática] mod [/ matemática] [matemática] 22. [/ matemática]

Ir a través de algunas propiedades del módulo aquí.

Desde [math] MCD (76,22) [/ math] [math] = [/ math] [math] 2 [/ math]. Entonces, usaremos la siguiente propiedad.

[matemática] (a * k) [/ matemática] [matemática] mod [/ matemática] [matemática] (k * m) [/ matemática] [matemática] = [/ matemática] [matemática] k [/ matemática] [matemática ] * [/ matemática] [matemática] (a [/ matemática] [matemática] mod [/ matemática] [matemática] m) [/ matemática] donde [matemática] mcd (a, m) [/ matemática] [matemática] = [/ matemáticas] [matemáticas] 1 [/ matemáticas]

[matemática] => k [/ matemática] [matemática] = [/ matemática] [matemática] 2 [/ matemática] [matemática] * [/ matemática] [matemática] (2 ^ {56} [/ matemática] [matemática] * [/ matemática] [matemática] 38 [/ matemática] [matemática] ^ {57} [/ matemática] [matemática] mod [/ matemática] [matemática] 11) [/ matemática]

[matemáticas] 11 [/ matemáticas] es de nuevo un número primo, use el pequeño teorema de Fermat nuevamente. También [matemática] 76 [/ matemática] [matemática] = [/ matemática] [matemática] -1 [/ matemática] [matemática] mod [/ matemática] [matemática] 11 [/ matemática]

=> [matemáticas] k [/ matemáticas] [matemáticas] = [/ matemáticas] [matemáticas] 2 * (2 ^ 6 * (5) ^ 7 mod 11) [/ matemáticas]

=> [matemática] k [/ matemática] [matemática] = [/ matemática] [matemática] 2 [/ matemática] [matemática] * [/ matemática] [matemática] (64 [/ matemática] [matemática] mod [/ matemática ] [matemáticas] 11 [/ matemáticas] [matemáticas] * [/ matemáticas] [matemáticas] 3 [/ matemáticas] [matemáticas] mod [/ matemáticas] [matemáticas] 11) [/ matemáticas]

=> [matemáticas] k = 2 * (-2 * 3 mod 11) [/ matemáticas]

=> [matemática] k = 2 [/ matemática] [matemática] * [/ matemática] [matemática] (([/ matemática] [matemática] -6) [/ matemática] [matemática] mod [/ matemática] [matemática] 11) [/ matemáticas]

=> [matemática] k [/ matemática] [matemática] = [/ matemática] [matemática] 2 * 5 [/ matemática] [matemática] = [/ matemática] [matemática] 10 [/ matemática] [desde [matemática] – 6 [/ matemática] [matemática] = [/ matemática] [matemática] 5 [/ matemática] [matemática] mod [/ matemática] [matemática] 11] [/ matemática]

Entonces, la respuesta requerida será

[matemáticas] 17 ^ {(22n + 4)} [/ matemáticas] [matemáticas] mod [/ matemáticas] [matemáticas] 23 [/ matemáticas]

= [matemáticas] (- 6) ^ {10} [/ matemáticas] [matemáticas] mod [/ matemáticas] [matemáticas] 23 [/ matemáticas]

= [matemáticas] 6 ^ {10} [/ matemáticas] [matemáticas] mod [/ matemáticas] [matemáticas] 23 [/ matemáticas]

= [matemática] (6 [/ matemática] [matemática] ^ 2) ^ 5 [/ matemática] [matemática] mod [/ matemática] [matemática] 23 [/ matemática]

= [matemática] 13 [/ matemática] [matemática] * [/ matemática] [matemática] 13 [/ matemática] [matemática] * [/ matemática] [matemática] 13 [/ matemática] [matemática] * [/ matemática] [ matemática] 13 [/ matemática] [matemática] * [/ matemática] [matemática] 13 [/ matemática] [matemática] mod [/ matemática] [matemática] 23 [/ matemática]

= [matemática] 169 [/ matemática] [matemática] * [/ matemática] [matemática] 169 [/ matemática] [matemática] * [/ matemática] [matemática] 13 [/ matemática] [matemática] mod [/ matemática] [ matemáticas] 23 [/ matemáticas]

= [matemática] 8 [/ matemática] [matemática] * [/ matemática] [matemática] 8 [/ matemática] [matemática] * [/ matemática] [matemática] 13 [/ matemática] [matemática] mod [/ matemática] [ matemáticas] 23 [/ matemáticas]

= [matemática] 64 [/ matemática] [matemática] * [/ matemática] [matemática] 13 [/ matemática] [matemática] mod [/ matemática] [matemática] 23 [/ matemática]

= [matemática] (- 5) [/ matemática] [matemática] * [/ matemática] [matemática] 13 [/ matemática] [matemática] mod [/ matemática] [matemática] 23 [/ matemática]

= [matemática] (- 65) [/ matemática] [matemática] mod [/ matemática] [matemática] 23 [/ matemática]

= [matemáticas] 4 [/ matemáticas]

Espero que ayude. 🙂

Para resolver este tipo de preguntas, utilice el pequeño teorema de Fermat, el teorema de Euler, la función totient de Euler y las propiedades del módulo.

Answer 2

Yo tampoco veo el punto de preguntas como esta. Además, no tengo una respuesta sustancialmente diferente de Gautam Kumar. Sin embargo, aquí está mi respuesta. También voy a usar un poco más de maquinaria, que también he usado en una respuesta anterior. Esto no solo simplifica el último bit de la respuesta, sino que es una parte útil e importante de la teoría de números.

---

Por conveniencia de notación, sea [matemática] n = 76 ^ {57} [/ matemática] y [matemática] N = 6457 ^ {76 ^ {57}} = 6457 ^ n [/ matemática].

Como [math] 76 \ equiv 10 \ pmod {22} [/ math], tenemos [math] n = 76 ^ {57} \ equiv 10 ^ {57} \ pmod {22} [/ math]. Ahora

[matemáticas] 10 ^ {57} \ equiv (-1) ^ {57} = -1 \ pmod {11} [/ matemáticas] y [matemáticas] 10 ^ {57} \ equiv 0 \ pmod {2} [/ matemáticas ]

Por lo tanto, [matemáticas] n = 76 ^ {57} \ equiv 10 ^ {57} \ equiv 10 \ pmod {22} [/ matemáticas]. … ([Matemáticas] \ estrella [/ matemáticas])

Desde [matemáticas] 6457 \ equiv -6 \ pmod {23} [/ matemáticas], tenemos

[matemáticas] N = 6457 ^ n \ equiv (-6) ^ n = 6 ^ n \ pmod {23} [/ matemáticas].

Como [math] 23 [/ math] es primo , [math] 6 ^ {22} \ equiv 1 \ pmod {23} [/ math]. De la ec. ([matemática] \ estrella [/ matemática]), [matemática] n = 22k + 10 [/ matemática] para algún número entero positivo [matemática] k [/ matemática]. Por lo tanto

[matemática] N \ equiv 6 ^ n = \ izquierda (6 ^ {22} \ derecha) ^ k \ cdot 6 ^ {10} \ equiv 6 ^ {10} \ pmod {23} [/ matemática]. … ([Matemáticas] \ estrella \ estrella [/ matemáticas])

---

Recuerde que el símbolo Legendre [matemática] \ left (\ frac {a} {p} \ right) [/ math] satisface

[matemáticas] \ left (\ frac {a} {p} \ right) \ equiv a ^ {(p-1) / 2} \ pmod {p} [/ math]

y es multiplicativo en el sentido de que

[matemáticas] \ left (\ frac {ab} {p} \ right) = \ left (\ frac {a} {p} \ right) \ left (\ frac {b} {p} \ right) [/ math] .

Ver también

La respuesta de Amitabha Tripathi a ¿Cómo muestra que si ab congurante a 1 (mod p) entonces (a \ p) = (b \ p)?

también

[matemática] \ left (\ frac {2} {p} \ right) = +1 [/ math] if [math] p \ equiv \ pm 1 \ pmod {8} [/ math] y [math] -1 [ / math] if [math] p \ equiv \ pm 3 \ pmod {8} [/ math],

y

[matemáticas] \ left (\ frac {p} {q} \ right) = \ left (\ frac {q} {p} \ right) [/ math] if [math] p [/ math] or [math] q [/ math] tiene la forma [math] 4k + 1 [/ math] y [math] – \ left (\ frac {q} {p} \ right) [/ math] si ambos [math] p [/ math ], [matemática] q [/ matemática] tienen la forma [matemática] 4k + 3 [/ matemática].

---

Por lo tanto

[matemáticas] 6 ^ {11} \ equiv \ left (\ frac {6} {23} \ right) = \ left (\ frac {2} {23} \ right) \ left (\ frac {3} {23} \ right) = \ left (\ frac {3} {23} \ right) = – \ left (\ frac {23} {3} \ right) = – \ left (\ frac {2} {3} \ right) = 1 \ pmod {23} [/ matemáticas].

Ahora de la ecuación. ([matemáticas] \ estrella \ estrella [/ matemáticas]) tenemos

[matemáticas] 6N \ equiv 6 ^ {11} \ equiv 1 \ pmod {23} [/ matemáticas],

de modo que al multiplicar ambos lados de la congruencia por [matemática] 4 [/ matemática] se obtiene [matemática] N \ equiv 4 \ pmod {23} [/ matemática].