¿Cuál es el teorema del resto chino y cómo se usa en la programación competitiva? Educación te da un futuro mejor

Teorema:

Deje que [math] m_ {1}, m_ {2}, …, m_ {r} [/ math] denote [math] r [/ math] enteros positivos que son relativamente primos en pares, y que [math] a_ {1 }, a_ {2}, … a_ {r} [/ math] denota cualquier entero [math] r [/ math]. Entonces, las congruencias [matemáticas] x \ equiv a_ {i} (mod \ m_ {i}) i = 1,2 … r [/ matemáticas] tienen soluciones comunes. Dos soluciones son módulo congruente [matemáticas] m_ {1}, m_ {2}, …, m_ {r} [/ matemáticas].

Aquí hay un ejemplo.
Encuentre todas las soluciones del sistema [matemática] x \ equiv 2 (mod \ 4), x \ equiv 3 (mod \ 5), x \ equiv 1 (mod \ 7) [/ math]

Aquí, [matemáticas] m_ {1} = 4, m_ {2} = 5, m_ {3} = 7, M = m_ {1} m_ {2} m_ {3} = 140, [/ matemáticas] [matemáticas] M_ {1} = \ frac {M} {m_ {1}} = 35, M_ {2} = \ frac {M} {m_ {2}} = 28, M_ {3} = \ frac {M} {m_ {3}} = 20 [/ matemáticas]

[matemáticas] M_ {1} \ equiv 3 (mod \ 4) [/ matemáticas]
por lo tanto, [matemáticas] M_ {1} ^ {‘} \ equiv 3 (mod \ 4). [/matemáticas]
[matemáticas] M_ {2} \ equiv 3 (mod \ 5) [/ matemáticas]
por lo tanto, [matemáticas] M_ {2} ^ {‘} \ equiv 2 (mod \ 5) [/ matemáticas]
[matemáticas] M_ {3} \ equiv 6 (mod \ 7) [/ matemáticas]
por lo tanto, [math] \ M_ {3} ^ {‘} \ equiv 6 (mod \ 7) [/ math]

Considerar,
[matemáticas] x_ {0} = 2M_ {1} M_ {1} ^ {‘} + 3M_ {2} M_ {2} ^ {‘} + 1M_ {3} M_ {3} ^ {‘} [/ matemáticas]
[matemáticas] x_ {0} = 2 \ veces 35 \ veces 3 + 3 \ veces 28 \ veces 2 + 20 \ veces 6 [/ matemáticas]
[matemáticas] = 498 \ equiv 78 (mod \ 140) [/ matemáticas]
Por lo tanto, todas las soluciones son de la forma
[matemáticas] 78 + 140k, k \ epsilon \ mathbb {Z} [/ matemáticas].
Hay muchas posibilidades para elegir [matemáticas] M_ {i} ^ {‘} [/ matemáticas].
Por ej. si elegimos [matemática] M_ {1} ^ {‘} = – 1, M_ {2} ^ {‘} = 2, M_ {3} ^ {‘} = -1 [/ matemática] entonces, [matemática] x_ {0} \ equiv 78 (mod \ 140) [/ math].

Aquí hay otro ejemplo en el que podría ser útil en la codificación competitiva.
Encuentra los últimos tres dígitos de las potencias número 100 de los primeros 100 números naturales.

Sea [math] m [/ math] un número natural y [math] r [/ math] sea el último dígito de [math] m [/ math]. Entonces, [math] m = r + 10k \ for \ some \ integer \ k [/ math]
Por lo tanto,
[matemáticas] m ^ {100} = (r + 10k) ^ {100} = r ^ {100} + 100r ^ {99} (10k) + [/ matemáticas]
[matemáticas] \ frac {100 \ veces 99} {2} r ^ {98} (10k ^ {2}) +… [/ matemáticas]
[matemáticas] m ^ {100} \ equiv r ^ {100} (mod \ 1000) [/ matemáticas]
porque,
[math] m \ equiv r (mod \ 10) \ Rightarrow m ^ {10} \ equiv r ^ {10} (mod \ 10 ^ {2}) [/ math]
[math] \ Rightarrow (m ^ {10}) ^ {10} \ equiv (r ^ {10}) ^ {10} (mod \ 10 ^ {3}) [/ math]
[matemáticas] es decir, m ^ {100} \ equiv r ^ {100} (mod \ 1000) [/ matemáticas]
(a) Si [matemáticas] r = 0 [/ matemáticas], entonces [matemáticas] r ^ {100} = 0. [/ matemáticas]
(b) Si [matemática] r = 1, 3, 7, 9, [/ matemática] entonces [matemática] r ^ {2} \ equiv 1 (mod \ 8) [/ matemática], entonces, [matemática] r ^ {100} \ equiv 1 (mod \ 8) [/ math].
Además, [matemáticas] \ phi (125) = 100 [/ matemáticas].
Según el teorema de Euler, como [math] (r, 5) = 1, r ^ {100} \ equiv 1 (mod \ 125) [/ math].
Por lo tanto, [matemática] r ^ {100} \ equiv 1 (mod \ 1000) [/ matemática]
(c) Si [matemática] r = 5 [/ matemática], entonces, [matemática] r ^ {2} \ equiv 1 (mod \ 8) [/ matemática].
Por lo tanto, [math] r ^ {100} \ equiv 1 (mod \ 8) y r ^ {100} \ equiv 0 (mod \ 125) [/ math].
Usando el teorema del resto chino, [math] r ^ {100} \ equiv 625 (mod \ 1000) [/ math]
(d) Si [matemáticas] r = 2, 4, 6, 8, r ^ {100} \ equiv 0 (mod \ 8) [/ matemáticas].
Como, [math] (r, 5) = 1 [/ math], obtenemos [math] r ^ {100} \ equiv 1 (mod \ 125) [/ math].
Según el teorema del resto chino, [math] r ^ {100} \ equiv 376 (mod \ 1000) [/ math].

Por lo tanto, en los casos anteriores, los últimos tres dígitos de [math] m ^ {100} [/ math] son [math] 000, 001, 625 \ y \ 376 [/ math]