Otro problema del Teorema del Resto Chino

Question

Esto es muy similar a: Problema del Teorema del Resto Chino en que al aplicar un algoritmo, obtengo una respuesta incorrecta y no veo dónde está mi error.

Una de las respuestas a la pregunta enlazada anteriormente señalaba que hay muchos algoritmos diferentes circulando para resolver la CRT. El que yo utilizo es similar al utilizado anteriormente, pero no es exactamente el mismo. El mío lo saqué del capítulo 33 de Algorithms, de Cormen, Leiserson y Rivest.

El problema es encontrar z que satisfaga $$3\ mod\ 8$$ $$7\ mod\ 21$$ $$22\ mod\ 25$$ $$2\ mod\ 11$$

Como 8, 21, 25 y 11 son relativamente primos, hay una solución.

El método se basa en encontrar constantes $c_1, .., c_4$ de la siguiente manera. Sea $(a_1, .., a_4) = (3, 7, 22, 2)$ y $(n_1,..,n_4) = (8, 21, 25, 11)$ . $n$ es el producto del $n_i$ : Aquí 46200. Definir $(m_1,..,m_4)$ dividiendo $n_i$ de $n$ Por ejemplo, ( $\frac{46200}{8}, \frac{46200}{21}, \frac{46200}{25}, \frac{46200}{11}$ ), o $(5775, 2200, 1848, 4200)$ .

Encuentre $(m_i^{-1}\ mod\ n_i)$ . Para el $m_i$ dado estos cálculos se encuentran a continuación. A modo de explicación, en el cálculo de abajo para $m_1^{-1}$ , $m_1 + 1 = 5775 + 1 = 5776$ es divisible por $8$ lo cual es cierto (en otras palabras, que 1 es el inverso de 5775 en la clase de equivalencia mod 8). $$m_1^{-1}\ mod\ 8 = 1$$ $$m_2^{-1}\ mod\ 21 = 5$$ $$m_3^{-1}\ mod\ 25 = 2$$ $$m_4^{-1}\ mod\ 11 = 2$$ .

Las constantes $c_i$ se forman ahora a partir del $m_i$ y las inversas que se acaban de encontrar $(1, 5, 2, 2)$ multiplicando los pares correspondientes: $(1 \cdot 5775, 5 \cdot 2200, 2 \cdot 1848, 2 \cdot 4200)$ o ( $5775, 11000, 3696, 8400$ ).

Finalmente, se resuelve $$a = (a_1 \cdot c_1 + .. + a_4 \cdot c_4)\ mod\ n$$ para conseguir $$(3 \cdot 5775 + 7 \cdot 11000 + 22 \cdot 3696 + 2 \cdot 8400)\ mod\ 46200$$

Obtengo como una de las soluciones para esto el número $a = 7637$ .

Sin embargo, el 7637 no funciona. Por ejemplo, $7637\ mod\ 8 = 5$ mientras que para ser una solución debe ser cierto que $7637\ mod\ 8 = 3$ .

Si alguien puede indicarme lo que estoy haciendo mal, se lo agradecería mucho.

Answer 1

El inverso multiplicativo , $a^{-1} \pmod n$ se define como : $a^{-1}a\equiv 1\pmod{n}$

Para encontrar $m_1^{-1}\pmod{8}$ , tienes que resolver la congruencia de abajo : $$\color{blue}{m_1x\equiv 1\pmod{8}}$$

y no $$\color{red}{m_1 + x \equiv 0 \pmod{8}}$$

Por lo tanto, obtendrá $$\color{blue}{x\equiv 7 \pmod{8}} $$

y no

$$\color{red}{ x \equiv 1 \pmod{8}}$$

Answer 2

La aritmética suele ser más fácil si se resuelven las congruencias sucesivamente en parejas en lugar de en paralelo. Comience con $\,x = 22+25i\,$ por $\,x\equiv 22\pmod{\!25}.$ Sustitúyalo en $\,x\equiv 7\pmod{\!21},$ resolver para $\,i$ para obtener un nuevo valor para $\,x,\,$ sustituirlo por la siguiente congruencia, etc., es decir

${\rm mod}\ 21\!:\ 7 \equiv 22+25\,\color{#c00}i\equiv 1+4i\!\iff\! 4i\equiv 6\!\iff\! 2i\equiv 3\iff\! \smash[t]{\overbrace{\color{}i\equiv 3/2\equiv 24/2\equiv \color{}{12}}^{\Large \color{#c00}{i\, =\, 12}\, +\, 21j}}\phantom{1^{1^{1^{1^{1^(1^1}}}}}$

${\rm mod}\ 11\!:\ 2\equiv 22+25(\color{#c00}{12}+21\color{#0a0}j)\,\equiv\, 3(1-j)\iff 3j\equiv 1\iff\! \smash[b]{\underbrace{\color{}j\equiv 1/3\equiv 12/3\equiv \color{}4}_{\Large\color{#0a0}{j\,=\, 4}\,+\,11k}}$

${\rm mod}\,\ \ 8\!:\ 3\equiv 22+25(12+21(\color{#0a0}4+11k))$ $\qquad\qquad 3 \equiv -2\ \ +\ (\ \ 4\ -\ 3(4\,+\ \,3\color{#c0f}k)) \equiv\, {-}2-k \iff \smash[b]{\underbrace{\color{}k\equiv-5\equiv \color{}3}_{\Large \color{#c0f}{k\,=\,3}\,+\,8n}}$

$\!\begin{align}{\rm Hence}\ \ x\equiv &\ \ 22+25(12+21(4+11(\color{#c0f}3+8n)))\\ =&\ \ 19747+46200 n\end{align}$

Fíjate que así todos los números son tan pequeños que se puede hacer toda la aritmética mentalmente, salvo, posiblemente, las sumas y multiplicaciones finales de la última línea.