4 votos

Resto del producto polinómico, solución CRT vía Bezout

Dada: $$f(x) \pmod{x^2 + 4} = 2x + 1$$ $$f(x) \pmod{x^2 + 6} = 6x - 1$$

Defina r(x) como $$f(x) \pmod{(x^2 + 4)(x^2+6)} = r(x)$$

¿Qué es? $r(4)$ ?


Las 3 ecuaciones se pueden replantear como cociente - divisor + resto:

$$f(x) = a(x)(x^2 + 4) + 2x + 1 $$ $$f(x) = b(x)(x^2 + 6) + 6x - 1 $$ $$f(x) = c(x)(x^2 + 4)(x^2 + 6) + r(x) = c(x)(x^4 + 10x^2 + 24) + r(x) $$


Tenga en cuenta que esto no es una tarea, y hay varios métodos diferentes que se pueden utilizar para resolver esto, uno de los cuales produce una f(x) basado en los 2 restos dados, dos de los cuales producen r(x) sin tener que determinar f(x), y una ligera variación que produce r(4). He mirado a otras preguntas resto polinomio aquí en SE, pero los que no implican todos los métodos que conozco que se pueden utilizar para resolver este problema en particular, así que pensé que podría ser interesante para otros aquí en SE. Algunos, pero no todos los métodos están relacionados con el teorema del resto chino, así que no estaba seguro de si también debe etiquetar esta pregunta con el teorema del resto chino. Encontré este problema en otro sitio del foro, así que no estoy seguro de los orígenes de este problema en particular.

3voto

David HAust Puntos 2696

Sugerencia $ $ Podemos leer en una solución CRT de la ecuación de Bezout para el gcd de los módulos, a saber $$\bbox[5px,border:1px solid #c00]{\text{$ \color{#90f}{\text{scale}} $ the Bezout equation by the residue difference - then $ {\rm \color{#c00}{re}\color{#0a0}{arrange}} $}}$$ $$\begin{align} {\rm if}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ &\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\begin{array}{rr} &f\equiv\, f_g\pmod{\!g}\\ &f\equiv\, f_h\pmod{\! h} \end{array}\ \ {\rm and}\ \ \gcd(g,h) = 1\\[.4em] {\rm then}\ \ \ f_g - f_h\, &=:\ \delta\qquad\qquad\ \ \rm residue\ difference \\[.2em] \times\qquad\quad\ \ \ 1\ &=\ \ a g\, +\, b h\quad\ \rm Bezout\ equation\ for \ \gcd(g,h) \\[.5em]\hline \Longrightarrow\ \,f_g\, \color{#c00}{-\, f_h}\, &= \color{#0a0}{\delta ag} + \delta bh\quad\ \rm product\ of \ above\ (= {\color{#90f}{scaled}}\ Bezout)\\[.2em] \Longrightarrow \underbrace{f_g \color{#0a0}{- \delta ag}}_{\!\!\!\large \equiv\ f_{\large g}\! \pmod{\!g}}\! &= \underbrace{\color{#c00}{f_h} + \delta bh}_{\large\!\! \equiv\ f_{\large h}\! \pmod{\!h}}\ \ \ \underset{\large {\rm has\ sought\ residues}\phantom{1^{1^{1^{1^1}}}}\!\!\!}{\rm \color{#c00}{re}\color{#0a0}{arranged}\ product}\rm\! = {\small CRT}\ solution\end{align} $$

De manera más general: $ $ si el gcd $\,d\neq 1\,$ entonces es solucionable $\iff d\mid f_g-f_h\,$ y podemos utilizar el mismo método que utilizamos a continuación para $\,d=\color{#c00}2\!:\,$ escalar la ecuación de Bezout por $\,(f_g-f_h)/d = \delta/d.\,$ Desde $\,\color{#c00}2\,$ es invertible en la OP, podríamos haber escalado la ecuación de Bezout por $\,1/2\,$ para cambiar $\,\color{#c00}2\,$ a $\,1,\,$ pero al no hacerlo se evitan fracciones (innecesarias) y se simplifica la aritmética.

En nuestro problema concreto tenemos la gran simplificación de que la ecuación de Bezout es evidente siendo simplemente los módulos diferencia $ =\color{#c00}2$
por lo que $\ \ \smash[t]{\overbrace{\color{0a0}{6x\!-\!1}-\color{#90f}{(2x\!+\!1)}}^{\rm residue\ difference}} = \overbrace{(2x\!-\!1)}^{\!\text{scale LHS}}\,\overbrace{\color{#c00}2 = (\color{0a0}{x^2\!+\!6}-\color{#0a0}{(x^2\!+\!4)}}^{{\overbrace{\textstyle\color{#c00}2\, =\, x^2\!+\!6-(x^2\!+\!4)_{\phantom{|_{|_i}}}\!\!\!\!}^{\Large \text{Bezout equation}}}})\overbrace{(\color{#0a0}{2x\!-\!1})}^{\text{scale RHS}},\ $ que reordenó

produce $\ \ \underbrace{\color{}{6x\!-\!1 - (\color{#0a0}{2x\!-\!1})(x^2\!+\!6)}}_{\large \equiv\ \ 6x\ -\ 1\ \pmod{x^2\ +\ 6}\!\!\!}\, =\, \underbrace{\color{#90f}{2x\!+\!1} -\color{#0a0}{(2x\!-\!1)(x^2\!+\!4)}}_{\large \equiv\ \ 2x\ +\ 1\ \pmod{x^2\ +\ 4}\!\!\!} =\,r(x) =\, $ Solución CRT.


Nota: $ $ Si se conocen los ideales y los cosets, lo anterior puede expresarse más sucintamente como

$$ \bbox[12px,border:1px solid #c00]{f_g\! +\! (g)\,\cap\, f_h\! +\! (h) \neq \phi \iff f_g-f_h \in (g)+(h)}\qquad$$

2voto

Anurag A Puntos 11751

Sugerencia

Observe que $\gcd(x^2+4, x^2+6)=1$ y $$\frac{1}{2}(x^2+6)-\frac{1}{2}(x^2+4)=1.$$ Ahora aplique el teorema chino del resto al sistema \begin{align*} f(x) & \equiv 2x+1 \pmod{x^2+4}\\ f(x) & \equiv 6x-1 \pmod{x^2+6} \end{align*} Para conseguir algo como: $$f(x) \equiv \underbrace{(2x+1)(\ldots) + (6x-1)(\ldots)}_{r(x)} \pmod{(x^2+4)(x^2+6)}.$$

1voto

Wes Brown Puntos 76

Estoy publicando una "respuesta" para los métodos alternativos. El tercer método a continuación es el más directo, aprovechando el hecho de que $(x^2+6)-(x^2+4) = 2$ . La respuesta a la pregunta, r(4) = -131.

Utilizar un proceso de división larga "inversa" para producir una f(x) común basada en las dos primeras ecuaciones dadas funcionará, pero, aunque esto resuelve el problema, dudo que sea la solución prevista, ya que implica una búsqueda razonada por ensayo y error de f(x) (una especie de búsqueda de fuerza bruta optimizada), y tengo la impresión de que una respuesta adecuada debería poder resolver para r(x) o específicamente para r(4) sin tener que determinar f(x).

A continuación se muestra cómo es el proceso. f(x) (el dividendo) y los cocientes a(x), b(x) son desconocidos. Los divisores y los residuos se dan en las dos primeras ecuaciones de la pregunta. Se empieza por la parte inferior de estas dos divisiones largas en paralelo, trabajando hacia arriba para producir una f(x) común.

Como se ha dicho, se trata de un proceso razonado de prueba y error. Por ejemplo, mi primer intento para el término x^2 de f(x) fue 13x^2, que falló después, el segundo intento fue 25x^2, que funcionó (al menos produce una f(x) común que satisface las dos primeras ecuaciones). Para el resto de los términos, los primeros intentos de términos para una f(x) común (y los correspondientes términos cocientes de a(x) y b(x)) funcionaron.

Considere el primer paso, f(x) / (x^2+4) tiene resto ...+1, f(x) / (x^2+6) tiene resto ...-1. Esto sugiere que el último término de f(x) es 5 y los últimos términos de ambos cocientes son 1, ya que 5-4 = +1 y 5-6 = -1. Los términos de x en el resto muestran que después de la sustracción del tercer paso desde abajo, los términos de x son 2x para la división por (x^2+4) y 6x para la división por (x^2+6), y el ajuste del término de x de f(x) a 18 funciona como 18 - (4-4) = 2 y 18 - (2-6) = 6. Se continúa el proceso hacia arriba, buscando términos comunes de f(x) que satisfagan ambas divisiones largas. Este es el resultado final. Una vez más, observe que este proceso se inicia en la parte inferior y se trabaja hacia arriba para producir un f(x) común (dividendo) para ambos divisores:

              1  1  6  4  1                   1  1  4  2  1
      ---------------------           ---------------------
1 0 4 | 1  1 10  8 25 18  5     1 0 6 | 1  1 10  8 25 18  5
        1  0  4                         1  0  6
           1  6  8                         1  4  8
           1  0  4                         1  0  6       
              6  4 25                         4  2 25
              6  0 24                         4  0 24
                 4  1 18                         2  1 18                  
                 4  0 16                         2  0 12   
                    1  2  5                         1  6  5
                    1  0  4                         1  0  6
                       2  1                            6 -1

Una vez que se determina cualquier f(x) que satisface las dos primeras ecuaciones dadas, el resto sólo requiere una división normal.

$$f(x) = x^6 + x^5 + 10 x^4 + 8 x^3 + 25 x^2 + 18 x + 5$$

Expresar f(x) como cociente - divisor + resto para los diferentes divisores:

$$f(x) = (x^4 + x^3 + 6x^2 + 4x + 1)(x^2 + 4) + 2x + 1 $$ $$f(x)= (x^4 + x^3 + 4x^2 + 2x + 1)(x^2 + 6) + 6x - 1 $$ $$f(x) = (x^2 + x)(x^4 + 10x^2 + 24) -2 x^3 + x^2 - 6 x + 5 $$


Utilizando la aproximación típica del teorema del resto f(x) evaluada en las 4 raíces de (x^2+4)(x^2+6): $$f(x) = c(x))(x^2+4)(x^2+6)) = r(x)$$ $$f(x) = (c(x) · 0) + r(x) = r(x)$$ f(x) evaluada en las 2 raíces de (x^2+4): $$f(x) = (a(x) · 0) + 2x + 1) = 2x + 1$$ f(x) evaluada en las 2 raíces de (x^2+6): $$f(x) = (b(x) · 0) + 6x - 1) = 6x - 1$$ Esto conduce a 4 puntos de datos para r(x): $${-(2)i,-(4)i+1}$$ $${+(2)i,+(4)i+1}$$ $${-\sqrt{6}i,-(6)\sqrt{6}i-1}$$ $${-\sqrt{6}i,-(6)\sqrt{6}i-1}$$

Utilizar la interpolación de Lagrange para resolver r(x) es complicado debido a los números complejos:

r(x) = ((x-x1)(x-x2)(x-x3)(y0))/((x0-x1)(x0-x2)(x0-x3)) +
       ((x-x0)(x-x2)(x-x3)(y1))/((x1-x0)(x1-x2)(x1-x3)) +
       ((x-x0)(x-x1)(x-x3)(y2))/((x2-x0)(x2-x1)(x2-x3)) +
       ((x-x0)(x-x1)(x-x2)(y3))/((x3-x0)(x3-x1)(x3-x2)) +

moler los 4 términos lleva a:

r(x) = (1/2 + i/8) (x^3 - 2 i x^2 + 6 x - 12 i) +
       (1/2 - i/8) (x^3 + 2 i x^2 + 6 x + 12 i) +
       1/24 (( i sqrt(6) - 36) x + 36 i sqrt(6) + 6) (x^2 + 4) +
       1/24 ((-i sqrt(6) - 36) x - 36 i sqrt(6) + 6) (x^2 + 4)
r(x) =    x^3 + 1/2 x^2 +  6 x + 3 +
       -3 x^3 + 1/2 x^2 - 12 x + 2
r(x) = -2 x^3 +     x^2 -  6 x + 5

Aprovechando el hecho de que $(x^2+6) - (x^2+4) = 2$ :

$$f(x) = a(x)(x^2+4)+(2x+1)$$ $$f(x) = b(x)(x^2+6)+(6x-1)$$ multiplicar la primera ecuación por $(x^2+6)$ y la segunda ecuación por $(x^2+4)$ $$f(x)(x^2+6) = a(x)(x^2+4)(x^2+6)+(2x+1)(x^2+6)$$ $$f(x)(x^2+4) = b(x)(x^2+4)(x^2+6)+(6x-1)(x^2+4)$$ restando la cuarta ecuación de la tercera: $$2f(x) = a(x)(x^2+4)(x^2+6)+(2x+1)(x^2+6)-b(x)(x^2+4)(x^2+6)-(6x-1)(x^2+4)$$ $$f(x) = (1/2)(a(x)(x^2+4)(x^2+6)+(2x+1)(x^2+6)-b(x)(x^2+4)(x^2+6)-(6x-1)(x^2+4))$$ $$f(x) mod((x^2+4)(x^2+6)) = r(x) = (1/2)((2x+1)(x^2+6) - (6x-1)(x^2+4))$$ $$r(x) = -2x^3 + x^2 - 6x + 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