Compute polynomial $p(x)$ if $x^5=1,\, x\neq 1$ [reducing mod $\textit{simpler}$ multiples]

The following question was asked on a high school test, where the students were given a few minutes per question, at most:

Given that, $$P(x)=x^{104}+x^{93}+x^{82}+x^{71}+1$$ and, $$Q(x)=x^4+x^3+x^2+x+1$$ what is the remainder of $P(x)$ divided by $Q(x)$?

The given answer was:

Let $Q(x)=0$. Multiplying both sides by $x-1$: $$(x-1)(x^4+x^3+x^2+x+1)=0 \implies x^5 - 1=0 \implies x^5 = 1$$ Substituting $x^5=1$ in $P(x)$ gives $x^4+x^3+x^2+x+1$. Thus, $$P(x)\equiv\mathbf0\pmod{Q(x)}$$

Obviously, a student is required to come up with a “trick” rather than doing brute force polynomial division. How is the student supposed to think of the suggested method? Is it obvious? How else could one approach the problem?

Solution 1:

The key idea employed here is the method of simpler multiples - a very widely used technique. Note that $\,Q\,$ has a "simpler" multiple $\,QR = x^5\!-\!1,\,$ so we can first reduce $P$ modulo $\,x^{\large 5}\! -\! 1\,$ via $\!\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},\,$ then finally reduce that $\!\bmod Q,\,$ i.e.

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

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

Therefore, if $\,P = x^{\color{#0a0}A}+x^{\color{#90f}B} +x^C + x^D + x^E\,$ & $\bmod 5\!:\ \color{#0a0}A,\color{#90f}B,C,D,E\equiv \color{#0a0}4,\color{#90f}3,2,1,0\,$ then $\,P\bmod x^5-1 = x^{\large \color{#0a0}4}+x^{\large \color{#90f}3}+x^{\large 2}\,+x^{\large 1}\,+x^{\large 0} = Q,\,$ therefore$P\bmod Q \,=\, (P\bmod X^5\!-\!1)\bmod Q \,=\, Q\bmod Q = 0,\,$ generalizing the OP.

This idea is ubiquitous, e.g. we already use it implicitly in grade school in radix $10$ to determine integer parity: first reduce mod $10$ to get the units digit, then reduce the units digits mod $2,\,$ i.e.

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

i.e. an integer has the same parity (even / oddness) as that of its units digit. Similarly since $7\cdot 11\cdot 13 = 10^{\large 3}\!+1$ we can compute remainders mod $7,11,13$ by using $\,\color{#c00}{10^{\large 3}\equiv -1},\,$ e.g. $\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,\,$ and, similar to the OP, by $\,9\cdot 41\cdot 271 = 10^{\large 5}\!-1\,$ we can compute remainders mod $41$ and $271$ by using $\,\color{#c00}{10^5\!\equiv 1}$

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

for example $\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$

Such "divisibility tests" are frequently encountered in elementary and high-school and provide excellent motivation for this method of "divide first by a simpler multiple of the divisor" or, more simply, "mod first by a simpler multiple of the modulus".

This idea of scaling to simpler multiples of the divisor is ubiquitous, e.g. it is employed analogously when rationalizing denominators and in Gauss's algorithm for computing modular inverses.

For example, to divide by an algebraic number we can use as a simpler multiple its rational norm = product of conjugates. Let's examine this for a quadratic algebraic number $\,w = a+b\sqrt{n},\,$ with norm $\,w\bar w = (a+b\sqrt n)(a-b\sqrt n) = \color{#0a0}{a^2-nb^2 = c}\in\Bbb Q\ (\neq 0\,$ by $\,\sqrt{n}\not\in\Bbb Q),\,$ which reduces division by an algebraic to simpler division by a rational, i.e. $\, v/w = v\bar w/(w\bar w),$ i.e.

$$\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 $$

so-called $\rm\color{#90f}{rationalizing}\ the\ \color{#0a0}{denominator}$. The same idea works even with $\,{\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$$

which simplifies by eliminating $\,t\,$ from the denominator, i.e. $\,a-t\to a^n,\,$ reducing the division to division by a simpler constant $\,a^n\,$ (vs. a simpler rational when rationalizing the denominator).

More generally, often we can use norms to reduce divisibility and factorization problems on algebraic integers to "simpler" problems involving their norm multiples in $\Bbb Z$ - analogous to above, where we reduced division by the algebraic integer $\,w = a + b\sqrt{n}\,$ to division by its norm. The same can be done using norms in any (integral) ring extension (i.e. the base ring need not be $\Bbb Z$).

Another example is Gauss' algorithm, where we compute fractions $\!\bmod m\,$ by iteratively applying this idea of simplifying the denominator by scaling it to a smaller multiple. Here we scale $\rm\color{#C00}{\frac{A}B} \to \frac{AN}{BN}\: $ by the least $\rm\,N\,$ so that $\rm\, BN \ge m,\, $ reduce mod $m,\,$ then iterate this reduction, e.g.

$$\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$$

Denominators of the $\color{#c00}{\rm reduced}$ fractions decrease $\,\color{#C00}{ 9 > 5 > 2> \ldots}\,$ so reach $\color{#C00}{1}\,$ (not $\,0\,$ else the denominator would be a proper factor of the prime modulus; it may fail for composite modulus)

See here and its $25$ linked questions for more examples similar to the OP (some far less trivial).

Worth mention: there are simple algorithms for recognizing cyclotomics (and products of such), e.g. it's shown there that $\, x^{16}+x^{14}-x^{10}-x^8-x^6+x^2+1$ is cyclotomic (a factor of $x^{60}-1),\,$ so we can detect when the above methods apply for arbitrarily large degree divisors.

Solution 2:

Let $a$ be zero of $x^4+x^3+x^2+x+1=0$. Obviously $a\ne 1$. Then $$a^4+a^3+a^2+a+1=0$$ so multiply this with $a-1$ we get $$a^5=1$$ (You can get this also from geometric series $$a^n+a^{n-1}+...+a^2+a+1 = {a^{n+1}-1\over a-1}$$ by putting $n=4$).

But then \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}

So each zero of $Q(x)$ is also a zero of $P(x)$ and since all 4 zeroes of $Q(x)$ are different we have $Q(x)\mid P(x)$.

Solution 3:

While it may be a standard technique, as Bill's response details, I wouldn't say it's at all obvious at High School level. As a pre-Olympiad challenge problem, however, it's a good one.

My intuition is via cyclotomic polynomials -- $Q(x) = \Phi_5(x)$, giving the idea to multiply through by $x-1$ -- but I doubt I would have recognised them before university: https://en.wikipedia.org/wiki/Cyclotomic_polynomial