Problema numero 11 - The theory of numbers

¿Cuál es el resto cuando 15^22 + 22^15 se divide entre 330? (Trabaje módulo 2,3,5 y 11 y use el teorema chino de los restos)

¿Y por qué será que nunca recuerdo ese teorema?

Bueno, lo que está claro es que 330 = 2·3·5·11

El teorema chino dice que dados m1, m2, ..., mr positivos primos entre sí por parejas, entonces el sistema de congruencias

x :~ a1 (mod m1)

x :~ a2 (mod m2)

......

x :~ ar (mod mr)

tiene solución común y dos soluciones son congruentes modulo m1·m2···mr

Y el método de construcción de la respuesta mejor lo dejo, en el libro está.

Pues vamos a ser obedientes y haremos lo que dice la pista

15 :~ 1 (mod 2) ==> 15^22 :~ 1 (mod 2)

22 :~ 0 (mod 2) ==> 22^15 :~ 0 (mod 2)

De lo cual se deduce

15^22 + 22^15 :~ 1 +0 :~ 1 (mod 2)

15 :~ 0 (mod 3) ==> 15^22 :~ 0 (mod 3)

22 :~ 1 (mod 3) ==> 22^15 :~ 1 (mod 3)

15^22 + 2^15 :~ 0+1 :~ 1 (mod 3)

15 :~ 0 (mod 5) ==> 15^22 :~ 0 (mod 5)

22 :~ 2 (mod 5) ==>

22^2 :~ 4 (mod 5) ==>

22^4 :~ 4·4 :~ 16 :~1 (mod 5) ==>

22^15 = (22^4)^3 · 22^2 · 22^1 :~ 1^3·4·2 :~ 8 :~ 3 (mod 5) ==>

15^22 + 22^15 :~ 0+3 :~ 3 (mod 5)

15 :~ 4 (mod 11) ==>

15^2 :~ 4·4 :~ 16 :~ 5 (mod 11) ==>

15^4 :~ 5·5 :~ 25 :~ 3 (mod 11) ==>

15^8 :~ 3·3 :~ 9 (mod 11) ==>

15^16 :~ 9·9 :~ 81 :~ 81 - 7·11 :~ 4 (mod 11) ==>

15^22 = 15^16 · 15^4 · 15^2 :~ 4·3·4 :~ 48 :~ 4 (mod 11)

22 :~ 0 (mod 11) ==> 22^15 :~ 0 (mod 11) ==>

15^22 + 22^15 :~ 4+0 :~ 4 (mod 11)

El residuo módulo un producto (m1·m2···ms) es residuo módulo cada uno de los factores, veámoslo

a = n(m1·m2···ms) + r ==> a :~ r (mod m1·m2···ms)

a = (n·m2····ms)m1 + r ==> a :~ r (mod m1)

....

a = [n·m1·m2···m sub(s-1)]ms + r ==> a :~ r (mod ms)

Luego el resto que sea al dividir por 330 será congruente con los cuatro restos que hemos calculado

x :~ 1 (mod 2)

x :~ 1 (mod 3)

x :~ 3 (mod 5)

x :~ 4 ( mod 11)

Se cumplen las condiciones del teorema chino de los restos, ya que 2,3,5,11 son primos entre sí y la respuesta x del sistema será el resto de dividir entre 330.

Ahora viene lo que nunca recuerdo como se resuelve, lo miraremos en el libro

Siendo m = m1·m2···ms, se tienen que resolver las incógnitas bi de las congruencias

(m/mi) bi :~ 1 (mod mi)

Como m=330, m1=2, m2=3, m3=5 y m4=11 las ecuaciones a solucionar son

165·b1 :~ 1 (mod 2) ==> está claro b1=1

110·b2 :~ 1 (mod 3) ==> Como 110 :~ 2 (mod 3) ==> 2·b2 :~1 (mod 3) ==> b2 = 2

66·b3 :~ 1 (mod 5) ==> Como 66 :~ 1 (mod 5) ==> 1·b3 :~ 1 (mod 5) ==> b3 = 1

30·b4 :~ 1 (mod 11) ==> Como 30 :~ 8 (mod 11) ==> 8·b4:~1 (mod 11) ==> b4 = 7

Esta última era un poco más complicada, he buscado en múltiplo de 8 que fuera una de 11 mas 1 y 8·7 = 56 = 5·11+1 luego 7 era el buscado

Y el libro dice que la solución es

x* = (m/m1)b1·a1 + (m/m2)b2·a2 + ....+ (m/ms)bs·as

luego en nuestro caso

x* = 165·1·1 + 110·2·1 + 66·1·3 + 30·7·4 = 165 + 220 + 198 + 840 = 1423

La solución que nos interesa es la congruente con esta módulo 330 que esté comprendida entre 0 y 329

1423 - 4·330 = 103

Luego si no me he equivocado el resto de la división que nos piden es 103. Eso es laborioso comprobarlo salvo que se haga con ordenador.

Este es un pequeño programa que calcula el modulo 330 de 15^22

program modulopotencias;
{$mode objfpc}{$H+}
uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Classes
  { you can add units after this };
var
  i,j: integer;
begin
  j:=1;
  for i:= 1 to 22 do
    begin
      j:=j*15 mod 330;
      writeln (i:6,j:6);
    end;
  readln;
end. 

da 225

Cambiando algunos números tenemos el que calcula el módulo 330 de 22^15 que da 88

Luego

15^22 + 22^15 :~ 225 + 88 = 313 (mod 330)

Pues no sale porque yo decía que era 107 y el ordenador que es 313

Te lo mando para que veas las penalidades que se pasa a veces. Voy a intentar encontrar el error, yo creo que no es fallo de la teoría, pero como no es algo que domine por completo no lo puedo asegurar.

Espera, espera. espera...