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?
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$$
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 in the method of rationalizing denominators and in Gauss's algorithm for computing modular inverses.
For example, to divide by an algebraic number we can employ its norm as a simpler multiple, e.g. for $\,w = a+b\sqrt{n}\,$ we use $\,ww' = (a+b\sqrt n)(a-b\sqrt n) = 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 = vw'/(ww'),$ e.g.
$$\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}{a^2-nb^2}\,=\, {\frac{\small 1}{\small c}}(a-b\sqrt n)\qquad $$
so-called rationalizing the 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$$ 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.
No comments:
Post a Comment