Calcular aritmética modular?

Question

Hola, estoy haciendo un trabajo de investigacion de fin de curso y me enfrento al problema del calculo aritmetico modular. Tengo ua función C=70^7(mod 187) y no consigo calcularla. Utilizo la calculadora HP 48gII pero no se como incluir dicha función, me indica un error de sintaxi. Alguien me podría ayudar, no importa que sea a mano.
Saludos!
PD. No quiero el resultado, sinó que me ayuden a saber calcularlo

Pero si escribo 70^2 el numero es bastante grande. No existe ninguna manera de calcular el resto?

Answer 1

RESPUESTA

70^7 mod 187 = 60

ANALISIS

Si denotamos con [x] la clase residual de x mod 187, podemos escribir:

[70^7] = [70 × 70^6] = [70] × [70^2]^3

pero [70^2] = [4900] = [38] porque 4900 = 26×187 + 38, entonces

[70^7] = [70] × [38]^3 = [70] × [38^3] = [70] × [54872] = [70] × [81]

porque 54872 = 293×187 + 81, entonces

[70^7] = [70×81] = [5670] = [60]

porque 5670 = 30×187 + 60, quedando así demostrado.

La gran ventaja de la aritmética modular es que tiene las siguientes propiedades:

[a+b] = [a] + [b]
[ab] = [a][b]

y de ellas se hacen todas las reducciones posibles para no trabajar con números demasiado grandes como es 70^7.

Espero esta visión te haya sido de utilidad.

NOTA: Para calcular el resto usando una calculadora, debes conocer el cociente, por ejemplo, si quieres conocer el residuo de 70^2 cuando divides entre 187 haz lo siguiente:

70^2 = 70×70 = 4900
4900 / 187 = 26.2032... esto significa que el cociente es 26, por lo tanto el resto lo obtienes haciendo

4900 - 26×187 = 38

es decir, lo que obtuviste con este procedimiento sencillo fueron el cociente y el residuo que define el algoritmo de la división:

4900 = 26×187 + 38

Otra forma de calcular el resto de 70^2 es usando las clases residuales:

[70^2] = [ (5×14)^2 ] = [5^2 × 14^2] = [25] [196]

pero [196] = [196-187] = [9], por lo tanto

[70^2] = [25] [9] = [25×9] = [225] = [225-187] = [38].

SALUDOS!

Answer 2

70^2 (mod 187) = 4900 (mod 187) = 38 (mod 187)

70^7 (mod 187) = (70^2)·(70^2)·(70^2)·70 (mod 187) = 38·38·38·70 (mod 187) = 1444·2660 (mod 187) = 135·42 (mod 187) = 5670 (mod 187) = 60 (mod 187)

Otra forma mas sencilla de hacerlo es mediante el pequeño teorema de Fermat. Un saludo

Answer 3

Lo más directo es elevar 70 a 7, 70^7= 8.235.430.000.000 y luego hallas el resto de dividir por 187, que es 60.
Hay casos en que la aritmética modular permite simplificaciones (por ejemplo si el múdulo fuera con respecto a una cantidad menor que 70 en lugar de 187, entonces bastaría con elevar a 7 el módulo de 70 por esa cantidad). Pero aquí no es posible por ser 187 mayor que 70 y estar elevado 70 a un número impar.
Un truco para hallar un resto con la calculadora. Al dividir te resulta un número decimal. Multiplicas la parte entera por el divisor (187) y restas el resultado del dividendo, también con la propia calculadora. Así te ahorras trabajo manual.
Recuerda: el resultado es 60.

Answer 4

70 a la 7 y luego le sacas el modulo a ese resultado, sino es partir el nuemerador para que no quede tan grande el resultado, digamos 70 a la 5 * 70 a la 2 y a esa segunda parte le sacas el mod 187.

Suerte