Compute polynomial p(x)p(x) if x5=1,x≠1x^5=1,\, x\neq 1 [reducing mod simpler\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)=x104+x93+x82+x71+1
and,
Q(x)=x4+x3+x2+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 x1:
(x1)(x4+x3+x2+x+1)=0x51=0x5=1
Substituting x5=1 in P(x) gives x4+x3+x2+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?

Answer

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,\, thereforeP\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.

Attribution
Source : Link , Question Author : joeblack , Answer Author : Bill Dubuque

Leave a Comment