1 respuesta
7) Busca el resto de 15! Entre 323.
El problema es idéntico al número 5. Primero factorizamos 323
323 = 17·19
El resto entre 323 cumplirá
15! = 323n + r = 17·19n + r
Y los restos entre 17 y 19 cumplen
15! = 17m + r1
15! = 19k + r2
igualando
17·19n + r = 17m + r1 ==> r =17(m-19n) + r1
17·19n + r = 19k + r2 ==> r = 19(k-17n) + r2
Luego el resto r entre 323 es congruente módulo 17 con r1 y es congruente módulo 19 con r2.
Si conocemos r1 y r2 podremos aplicar el teorema chino de los restos para calcular r. Y r1 y r2 los podemos conocer por el teorema de Wilson
Como 19 es primo por el teorema de Wilson
18! ~: -1 (mod 19)
18·17·16·15! ~: -1 (mod 19)
(-1)(-2)(-3)15! ~: -1 (mod 19)
-6·15! ~: -1 (mod 19)
Va a ser difícil calcular la congruencia de 15! Pero por nada del mundo quiero usar el algoritmos de Euclides que ya ni me acuerdo casi
6·15! ~: 1 (mod 19)
Multiplicamos por 4
24·15! ~: 4 (mod 19)
Restamos 19·15!
5·15! ~: 4 (mod 19)
Multiplicamos por 4
20·15| ~: 16 (mod19)
restamos 19·15!
15! ~: 16 (mod 19)
Y como 17 es primo
16! ~: -1 (mod 17)
16·15! ~: -1 (mod 17)
(-1)15! ~: -1 (mod 17)
15! ~: 1 (mod 17)
Y ya tenemos el sistema de ecuaciones en congruencias del teorema chino de los restos si donde está 15! Ponemos x
x ~: 1 (mod 17)
x ~: 16 (mod 19)
El libro dice que la respuesta es
x* = (323/17)b1·1 + (323/19)b2·16 = 19·b1 + 272·b2
Donde
19·b1 ~: 1 (mod 17)
17·b2 ~: 1 (mod 19)
Vamos a resolver para encontrar b1 y b2.
En la primera restamos 17b1
2b1 ~: 1 (mod 17)
Multiplicamos por 9
18b1 ~: 9 (mod 17)
Restamos 17b1
b1 ~: 9 (mod 17)
Y en la segunda restamos 19b2
-2b2 ~: 1 (mod 19)
multiplicamos por 9
-18b2 ~: 9 (mod 19)
y sumamos 19b2
b2 ~: 9 (mod 19)
Con esto x* = 19·9 + 272·9 = 2619
El teorema dice que las soluciones son las congruencias módulo 323 de este número, luego vamos a calcular la solución menos que sera el resto
2619 / 323 = 8.10..
2619 - 8·323 = 35
Luego 35 es el resto de dividir 15! entre 323
-------------------------------
La verdad es que se hacen tantas cosas que uno duda, pero esta vez no han puesto números muy grandes y la calculadora de Windows 7 es una joya para comprobar operaciones que desbordan a las normales, aunque tampoco todas.
15! = 1307674368000
1307674368000 / 323 =4048527455,1083591331269349845201
1307674368000 - 4048527455 · 323 = 35
Luego está bien.
Y eso es todo.
