División de polinomios: ¿un truco obvio? [reducir mod $\textit{simpler}$ múltiplos]

Question

La siguiente pregunta se formuló en un examen de bachillerato, en el que los alumnos disponían de unos minutos por pregunta, como máximo:

Dado que, $$P(x)=x^{104}+x^{93}+x^{82}+x^{71}+1$$ y, $$Q(x)=x^4+x^3+x^2+x+1$$ qué es lo que queda de $P(x)$ dividido por $Q(x)$ ?

---

La respuesta dada fue:

Dejemos que $Q(x)=0$ . Multiplicando ambos lados por $x-1$ : $$(x-1)(x^4+x^3+x^2+x+1)=0 \implies x^5 - 1=0 \implies x^5 = 1$$ Sustituyendo $x^5=1$ en $P(x)$ da $x^4+x^3+x^2+x+1$ . Así, $$P(x)\equiv\mathbf0\pmod{Q(x)}$$

---

Evidentemente, se requiere que el estudiante idee un "truco" en lugar de hacer la división de polinomios por fuerza bruta. ¿Cómo se supone que el estudiante debe pensar en el método sugerido? ¿Es obvio? ¿De qué otra manera se podría abordar el problema?

Answer 1

La idea clave empleada aquí es la método de los múltiplos más simples - una técnica muy utilizada. Tenga en cuenta que $\,Q\,$ tiene un múltiplo "más simple" $\,QR = x^5\!-\!1,\,$ por lo que primero podemos reducir $P$ modulo $\,x^{\large 5}\! -\! 1\,$ a través de $\!\bmod x^{\large 5}-1\!:\,\ \color{#c00}{x^{\large 5}\equiv 1}\Rightarrow\, x^{\large r+5q^{\phantom{|}}}\!\!\equiv x^{\large r}(\color{#c00}{x^{\large 5}})^{\large q}\equiv x^{\large r},\,$ para finalmente reducirlo $\!\bmod Q,\,$ es decir

$$P\bmod Q\, =\, (P\bmod QR)\bmod Q\qquad$$

Prueba: $\: \color{#0a0}{P'}:= P\bmod QR\, =\, P-QRS\,\color{#0a0}{\equiv P}\,\pmod{\!Q},\,$ así $\:\color{#0a0}{P'}\bmod Q = \color{#0a0}{P}\bmod Q$

Esta idea es omnipresente, por ejemplo, ya la utilizamos implícitamente en la escuela primaria en el radix $10$ para determinar la paridad de los enteros: primero reducir mod $10$ para obtener el dígito de las unidades, luego reduce los dígitos de las unidades mod $2,\,$ es decir

$$N \bmod 2\, = (N\bmod 2\cdot 5)\bmod 2\qquad\ $$

es decir, un número entero tiene la misma paridad (par / impar) que la de su dígito de las unidades. Del mismo modo, puesto que $7\cdot 11\cdot 13 = 10^{\large 3}\!+1$ podemos calcular los residuos mod $7,11,13$ utilizando $\,\color{#c00}{10^{\large 3}\equiv -1},\,$ Por ejemplo $\bmod 13\!:\,\ d_0+ d_1 \color{#c00}{10^{\large 3}} + d_2 (\color{#c00}{10^{\large 3}})^{\large 2}\!+\cdots\,$ $ \equiv d_0 \color{#c00}{\bf -} d_1 + d_2+\cdots,\,$ y, al igual que el PO, por $\,9\cdot 41\cdot 271 = 10^{\large 5}\!-1\,$ podemos calcular los residuos mod $41$ y $271$ utilizando $\,\color{#c00}{10^5\!\equiv 1}$

$$N \bmod 41\, = (N\bmod 10^{\large 5}\!-1)\bmod 41\quad $$

por ejemplo $\bmod 41\!:\ 10000\color{#0a0}200038$ $ \equiv (\color{#c00}{10^{\large 5}})^{\large 2}\! + \color{#0a0}2\cdot \color{#c00}{10^{\large 5}} + 38\equiv \color{#c00}1+\color{#0a0}2+38\equiv 41\equiv 0$

Tales "pruebas de divisibilidad" se encuentran con frecuencia en la escuela primaria y secundaria y proporcionan una excelente motivación para este método de "dividir primero por un múltiplo más simple del divisor" o, más simplemente, "mod primero por un múltiplo más simple del módulo".

Esta idea de escalar a múltiplos más simples del divisor es omnipresente, por ejemplo, se emplea análogamente cuando racionalizar los denominadores y en Algoritmo de Gauss para calcular las inversiones modulares.

Por ejemplo, para dividir por un número algebraico podemos utilizar como más sencillo múltiples su racional norma = producto de conjugados. Examinemos esto para un número algebraico cuadrático $\,w = a+b\sqrt{n},\,$ con norma $\,w\bar w = (a+b\sqrt n)(a-b\sqrt n) = \color{#0a0}{a^2-nb^2 = c}\in\Bbb Q\ (\neq 0\,$ por $\,\sqrt{n}\not\in\Bbb Q),\,$ que reduce la división por un algebraico a más sencillo división por un racional es decir $\, v/w = v\bar w/(w\bar w),$ es decir

$$\dfrac{1}{a+b\sqrt n}\, =\, \dfrac{1}{a+b\sqrt n}\, \dfrac{a-b\sqrt n}{a-b\sqrt n}\, =\, \dfrac{a-b\sqrt n}{\color{#0a0}{a^2-nb^2}}\,=\, {\frac{\small 1}{\small \color{#0a0}c}}(a-b\sqrt n),\,\ \color{#0a0}{c}\in\color{#90f}{\Bbb Q}\qquad $$

el llamado $\rm\color{#90f}{rationalizing}\ the\ \color{#0a0}{denominator}$ . La misma idea funciona incluso con $\,{\rm\color{#c00}{nilpotents}}$

$$\color{#c00}{t^n = 0}\ \Rightarrow\ \dfrac{1}{a-{ t}}\, =\, \dfrac{a^{n-1}+\cdots + t^{n-1}}{a^n-\color{#c00}{t^n}}\, =\, a^{-n}(a^{n-1}+\cdots + t^{n-1})\qquad$$

que simplifica eliminando $\,t\,$ del denominador, es decir $\,a-t\to a^n,\,$ reduciendo la división a la división por una más simple constante $\,a^n\,$ (frente a una más sencilla racional cuando racionalizando el denominador).

De manera más general, a menudo podemos utilizar las normas para reducir los problemas de divisibilidad y factorización en algebraico enteros a problemas "más sencillos" que implican sus múltiplos de norma en $\Bbb Z$ - análoga a la anterior, en la que redujimos la división por el entero algebraico $\,w = a + b\sqrt{n}\,$ a la división por su norma. Lo mismo se puede hacer usando normas en cualquier extensión de anillo (integral) (es decir, el anillo base no necesita ser $\Bbb Z$ ).

Otro ejemplo es El algoritmo de Gauss, donde calculamos las fracciones $\!\bmod m\,$ aplicando iterativamente esta idea de simplificar el denominador escalándolo a un múltiplo menor. Aquí escalamos $\rm\color{#C00}{\frac{A}B} \to \frac{AN}{BN}\: $ por el menos $\rm\,N\,$ para que $\rm\, BN \ge m,\, $ reducir mod. $m,\,$ y luego iterar esta reducción, por ejemplo

$$\rm\\ mod\ 13\!:\,\ \color{#C00}{\frac{7}9} \,\equiv\, \frac{14}{18}\, \equiv\, \color{#C00}{\frac{1}5}\,\equiv\, \frac{3}{15}\,\equiv\, \color{#C00}{\frac{3}2} \,\equiv\, \frac{21}{14} \,\equiv\, \color{#C00}{\frac{8}1}\qquad\qquad$$

Denominadores del $\color{#c00}{\rm reduced}$ las fracciones disminuyen $\,\color{#C00}{ 9 > 5 > 2> \ldots}\,$ por lo que llegar a $\color{#C00}{1}\,$ (no $\,0\,$ si no, el denominador sería un adecuado factor de la prime módulo; puede fallar para compuesto módulo)

Ver aquí y su $25$ preguntas enlazadas para más ejemplos similares al OP (algunos mucho menos triviales).

Vale la pena mencionar: hay simple algoritmos para reconocer la ciclotomía (y sus productos), por ejemplo, se muestra allí que $\, x^{16}+x^{14}-x^{10}-x^8-x^6+x^2+1$ es ciclotómico (un factor de $x^{60}-1),\,$ para que podamos detectar cuándo se aplican los métodos anteriores para divisores de grado arbitrariamente grandes.

Answer 2

Dejemos que $a$ sea cero de $x^4+x^3+x^2+x+1=0$ . Obviamente $a\ne 1$ . Entonces $$a^4+a^3+a^2+a+1=0$$ así que multiplique esto por $a-1$ obtenemos $$a^5=1$$ (También se puede obtener de la serie geométrica $$a^n+a^{n-1}+...+a^2+a+1 = {a^{n+1}-1\over a-1}$$ poniendo $n=4$ ).

Pero entonces \begin{eqnarray} Q(a) &=& a^{100}\cdot a^4+a^{90}\cdot a^3+a^{80}\cdot a^2+a^{70}\cdot a+1\\ &=& a^4+a^3+a^2+a+1\\&=&0\end{eqnarray}

Así que cada cero de $Q(x)$ también es un cero de $P(x)$ y como los 4 ceros de $Q(x)$ son diferentes tenemos $Q(x)\mid P(x)$ .

Answer 3

Aunque puede ser una técnica estándar, como detalla la respuesta de Bill, yo no diría que es del todo obvia en el nivel de High School. Sin embargo, como problema de desafío preolímpico, es bueno.

Mi intuición es a través de polinomios ciclotómicos -- $Q(x) = \Phi_5(x)$ , dando la idea de multiplicar por $x-1$ -- pero dudo que los hubiera reconocido antes de la universidad: https://en.wikipedia.org/wiki/Cyclotomic_polynomial

Answer 4

Esto puede ser accesible para un estudiante de secundaria:

$x^{104}+x^{93}+x^{82}+x^{71}+1$

$ = (x^{104}-x^4)+(x^{93}-x^3)+(x^{82}-x^2)+(x^{71}-x)+(x^4+x^3+x^2+x+1)$

$=x^4(x^{100}-1)+x^3(x^{90}-1)+x^2(x^{80}-1)+ x(x^{70}-1)+(x^4+x^3+x^2+x+1)$

Sabemos que $(x^n-1)|(x^{mn}-1), m,n \in \mathbb{N}$ así que $x^5-1$ divide $x^{100}-1, x^{90}-1$ etc.

A su vez $x^5-1$ es divisible por $(x^4+x^3+x^2+x+1)$ lo que concluye la prueba

Answer 5

Si no es evidente, un examen de la pregunta revela rápidamente el truco. Diga

$$P(x)=x^n$$

A continuación, comience la división larga por $Q(x)$ :

$$x^n-x^n-x^{n-1}-x^{n-2}-x^{n-3}-x^{n-4}$$ $$x^{n-5}$$ $$\dots$$ $$x^{n-5k}$$

Aunque puede que no sea obvio con sólo mirar la pregunta, cualquiera que intente la solución ingenua tiene (al menos) una posibilidad razonable de encontrarse con una forma de resolverla.