5 votos

¿Cómo reducir el sistema de congruencia?

Estoy dado de un sistema de congruencias y quiere aplicar el teorema del resto Chino (CRT), pero el máximo común divisor (MCD) de los módulos no es $1$.

Bien, tengo la necesidad de reducir el sistema, de tal manera que el MCD es $1$, pero no sé cómo la "reducción" de las obras. Me refiero a que necesita una explicación.

He encontrado un ejemplo, pero no se cómo por arte de magia se transforman a partir de

$$x \equiv 1 \mod 108$$ $$x \equiv 13 \mod 40$$ $$x \equiv 28 \mod 225$$

a $$x \equiv 1 \mod 27$$ $$x \equiv 5 \mod 8$$ $$x \equiv 3 \mod 25$$

Veo que $$108 = 2^2 \times 3^3$$ $$ 40 =5 \times 2^3$$ $$225=3^2 \times 5^2$$

pero no estoy seguro de cuándo y cómo se usa... gracias por la ayuda!

2voto

Mr. Brooks Puntos 639

Esencialmente, usted tiene que averiguar congruencias que significa que el tipo de la misma cosa.

Por ejemplo, si $x \equiv 1 \bmod 108$,$x \equiv 1 \bmod 3$. Sin embargo, usted no tiene que dividir $108$ que mucho, ya que dividir el $4$ conseguir $x \equiv 1 \bmod 27$ es suficiente para hacer que el primer módulo de coprime a los otros dos módulos.

Ahora sólo tienes que hacer los módulos de $40$ $225$ coprime. Se podría dividir el $25$ $225$ y, a continuación, el tercer módulo es coprime a la segunda, pero no la primera.

Por lo tanto el más fácil la elección en este punto es dividir el$5$$40$, y dividir el$9$$225$, dándole $8$ $25$ para el segundo y tercer módulos.

Pero cuidado: desde $13 > 8$$28 > 25$, usted necesita para cambiar estas dos restos. Bueno, técnicamente no tiene, pero algunas implementaciones del algoritmo puede ser expulsado y no entregar el resultado correcto, o cualquier resultado en absoluto.

Por lo tanto $x \equiv 13 \bmod 40$ hace $x \equiv 5 \bmod 8$ (desde $13 - 8 = 5$) y $x \equiv 28 \bmod 225$ hace $x \equiv 3 \bmod 25$ (desde $28 - 25 = 3$).

Para comprobar sus respuestas en Wolfram Mathematica o Wolfram Alpha: ¿ ChineseRemainder[{1, 13, 28}, {108, 40, 225}] y comparar los resultados con ChineseRemainder[{1, 5, 3}, {27, 8, 25}] (dependiendo de las circunstancias fuera de su control, Wolfram Alpha puede no dar resultado cuando los módulos no son coprime).

$x = 2053$, ya que el $2053 = 19 \times 108 + 1 = 51 \times 40 + 13 = 9 \times 225 + 28$. También se $2053 = 76 \times 27 + 1 = 256 \times 8 + 5 = 82 \times 25 + 3$.

(Yo sólo quería probar que "invisibles hasta que pase" de texto que veo en muchas respuestas en este sitio).

2voto

fleablood Puntos 5913

La reducción es trivial:

Si $a \equiv b \mod n$ $a \equiv b \mod k$ todos los $k|n$.

Sólo pensar en ello......

=======

$x \equiv 1 \mod 108 \implies x= 108k + 1 = 27(4k) + 1 \implies x \equiv 1 \mod 27$.

$x \equiv 13 \mod 40 \implies x = 40k + 13 = 8(5k) + 13 \implies x \equiv 13 \equiv 5 \mod 8$. etc.

=======

Va el otro camino que requiere (menor de edad) de la estipulación.

Si $a \equiv b \mod k$ $a \equiv b + ck \mod n$ cualquier $n$ un múltiplo de $k$ $c$ es un número entero; (exactamente que entero no es necesariamente conocida).

====

Por lo $x \equiv 1 \mod 3^3*2^2$

$x \equiv 13 \mod 2^3*5$

$x \equiv 28 \mod 5^2*3^2$

Elija la más grande de las condiciones mutuamente factores primos: $3^3;2^3;5^2$

Así

$x \equiv 1 \mod 3^3$

$x \equiv 13\mod 2^3$

$x \equiv 28 \mod 2^5$.

2voto

David HAust Puntos 2696

La idea es utilizar CRT para dividir las congruencias en congruencias equivalente a cebar poderes, luego eliminar redundantes congruencias (se muestra arriba y abajo de las implicaciones de flecha abajo)

$\begin{array}{lll} x\equiv1 \pmod{\!2^2\cdot 3^3}\iff &\!\!\!\!\!\!\color{#0a0}{x\equiv1} \pmod{\!2^2}, &\!\!\!\!\!\! x\equiv 1\pmod{\!3^3}\\[-.5em] & \Uparrow & \\[-.3em] x\equiv 13 \pmod{\!2^3\cdot 5}\iff &\!\!\!\!\!\!\color{#c00}{x\equiv 13\equiv5} \pmod{\!2^3}, & \Downarrow&x\equiv 13\equiv3\pmod{\!5}\\[-.5em] & & & \quad \Uparrow\\[-.2em] x\equiv28\pmod{\!3^3\cdot 5^2}\!\iff &&\!\!\!\!\!\!x\equiv28\equiv1\pmod{\!3^2}, &x\equiv 28\equiv 3\pmod{\!5^2} \end{matriz} $

Por ejemplo, nota $\,\color{#c00}{x\equiv 5}\pmod{\!2^3}\,\Rightarrow\, \color{#0a0}{x\equiv 5\equiv 1}\pmod{\!2^2},\,$ por lo que el último es redundante y puede eliminarse.

Del mismo modo podemos eliminar la implícita congruencias mod $3^2$y mod $5,\,$ dejando el sistema dicho equivalente de tres congruencias a poderes.

1voto

Matthew Scouten Puntos 2518

Los números primos que dividen al menos uno de los tres módulos son $2$, $3$ y $5$.

El mayor poder de $2$ en cualquiera de ellos es $2^3 = 8$, el cual se divide $40$. Dado que $x \equiv 13 \mod 40$, $x \equiv 13 \equiv 5 \mod 8$. Usted también tiene $x \equiv 1 \mod 108$ , lo que implica $x \equiv 1 \mod 4 (=2^2)$, y esto no es un problema, ya que $5 \equiv 1 \mod 4$.

Del mismo modo, la máxima potencia de $3$ es $3^3 = 27$; $x \equiv 1 \mod 108$ por lo $x \equiv 1 \mod 27$, y esto es compatible con $x \equiv 28 \mod 225$ desde $28 \equiv 1 \mod 3^2$.

Finalmente, la máxima potencia de $5$ es $5^2 = 25$; $x \equiv 28 \mod 225$ implica $x \equiv 28 \equiv 3 \mod 25$, y esto es compatible con $x \equiv 13 \mod 40$ because $13 \equiv 3 \mod 5$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X