# Polynomial division: an obvious trick? [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)$$?

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?

• One observation is that in that question the step of 'multiplying both sides by $x-1$' is only presentation and doesn't really represent any advantage for solving the problem. What is really important is observing that the roots of $Q$ are the fifths roots of $1$ besides $1$, or that is a factor of $x^5-1$. There are many ways to compute this remainder that are simple to do in a short time. So, don't include that 'multiplying by $x-1$' as part of what was required for the students to solve the problem – logarithm May 14 '19 at 15:48
• My approach would be to observe that the exponents on P(x) look like they're set up to produce an elegant answer. The common elegant answers are "1" and "0". Since the "+1"s on the polynomials are clearly intended to cancel out, the answer must be "0". – Mark May 14 '19 at 23:33
• I'm probably missing something, but... The above trick seems to show that when $Q(x) = 0$, $P(x) = Q(x)$. But (a) the original question didn't specify that $Q(x) = 0$; how do we know that the answer $P(x)\equiv\mathbf0\pmod{Q(x)}$ applies to other cases? and (b) the original question asks, "what is the remainder of $𝑃(𝑥)$ divided by $𝑄(𝑥)$?" but the answer given here says let $Q(x) = 0$; doesn't that mean that the remainder is not defined? en.wikipedia.org/wiki/Remainder#Polynomial_division – LarsH May 15 '19 at 21:06
• I added some explicit examples to the end of my answer to emphasize the ubiquity of that simple idea. – Bill Dubuque May 16 '19 at 13:49
• What kind of test? Is this part of a math competition, or a classroom precalculus exam? – PersonX May 16 '19 at 16:35

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

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).

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.

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)$$.

• I think this is the approach that the examiners would expect from high school students. – Dancrumb May 14 '19 at 0:23
• From my perspective this is the best answer. (+1) – trancelocation May 14 '19 at 3:54
• The OP understands that after multiplication with $x-1$, the question became simpler, he/she asked how a student should find this trick. This answer is basically just a reformulation of the answer given in the question. I don't see the usefulness of this answer at all... (but it has 14 upvotes, so I might be missing something...) – user193810 May 14 '19 at 11:49
• @MariaMazur: A bit, but not really. It still feels like you stopped reading the question after "what is the remainder of P(x) divided by Q(x)?". You gave a correct answer to that question, but not to the real question. It is easy to prove that the 'trick' (multiplication by $x-1$) works and is correct, but you ignored the real question, and after your edit it is hidden as a small remark. But whatever, your answer is trivially better than mine, because I did not gave any, so I'll leave it here. – user193810 May 14 '19 at 13:25
• @Pakk: it hinges on spotting the standard identity: $Q(x) = 0$ gives the fifth roots of unity (other than x=1). It takes tons more work if you don't spot that; you could solve the quartic $Q(x) = 0$ then notice "Hey these are the other four fifth roots of unity, thus x^5 \equiv 1" then apply the information $x^5 \equiv 1$ to hugely simplify $P(x)$, and thus conclude $Q(x) \mid P(x)$ and remainder = 0. But that would be lots more work. (Yeah the first time I saw this trick back in HS I voiced the same objection about non-obviousness... this is why this identity is so pivotal to factorization) – smci May 16 '19 at 1:53

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

• I would go even further. As a BSE graduate in engineering, this is not at all obvious to me. – MooseBoys May 14 '19 at 6:58
• @MooseBoys: I would go even further. As a PhD in Physics (admittedly many years ago), this is not at all obvious to me. – WoJ May 14 '19 at 9:04
• It may not be obvious in other contexts since you never had to use it, but I assure you that in Math Olympiad training it's a standard trick. All serious contestants will probably already have seen something similar. There's nothing outrageous or shameful in that; Olympiad-style math is simply different from what people use and need in other professional contexts (physicist/engineer) --- the focus on Euclidean geometry being a perfect example. – Federico Poloni May 14 '19 at 9:12
• @Federico Where in the question does it say that this is an Olympiad test? OP phrased their question as if it were applicable to all high school students. I'd guess that fewer than 5% of all students would get the correct answer. – MooseBoys May 14 '19 at 17:01
• @MooseBoys I agree with your estimate. The question is "is this obvious?", and my comment is "it is a standard problem for people who train for math Olympiads". I realize that it's a strong additional assumption. I'm not arguing that it's a good or bad problem: as you point out, to do that, we would at least have to know to which students it was given. – Federico Poloni May 14 '19 at 17:09

This may be accessible to a high school student:

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

We know that $$(x^n-1)|(x^{mn}-1), m,n \in \mathbb{N}$$ so $$x^5-1$$ divides $$x^{100}-1, x^{90}-1$$ etc.

In turn $$x^5-1$$ is divisible by $$(x^4+x^3+x^2+x+1)$$ which concludes the proof

If it's not obvious, an examination of the question quickly reveals the trick. Say

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

Then begin long division by $$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}$$

While it may not be obvious just by looking at the question, anyone who attempts the naive solution has (at least) a reasonable chance of running across a way of solving it.

• This is a good point. If one is asked to perform division by a polynomial $Q(x)$, it is natural to start with dividing $x^n$ for $n> \deg(Q)$. Thus the first step is to divide $x^5$. Magically(!), one gets the remainder 1. So, one can discover the formula in the form $x^5=(x-1)(x^4+x^3+x^2+x+1) + 1$ even if one didn't remember it. The rest of the steps are not too difficult. – Kapil May 14 '19 at 4:07

I would have thought that bright students, who knew $$1+x+x^2+\cdots +x^{n-1}= \frac{x^n-1}{x-1}$$ as a geometric series formula, could say

$$\dfrac{P(x)}{Q(x)} =\dfrac{x^{104}+x^{93}+x^{82}+x^{71}+1}{x^4+x^3+x^2+x+1}$$

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

$$=\dfrac{x^{105}-x^{104}+x^{94}-x^{93}+x^{83}-x^{82}+x^{72}-x^{71}+x-1}{x^5-1}$$

$$=\dfrac{x^{105}-1}{x^5-1}-\dfrac{x^{104}-x^{94}}{x^5-1}-\dfrac{x^{93}-x^{83}}{x^5-1}-\dfrac{x^{82}-x^{72}}{x^5-1}-\dfrac{x^{71}-x}{x^5-1}$$

$$=\dfrac{x^{105}-1}{x^5-1}-x^{94}\dfrac{x^{10}-1}{x^5-1}-x^{83}\dfrac{x^{10}-1}{x^5-1}-x^{72}\dfrac{x^{10}-1}{x^5-1}-x\dfrac{x^{70}-1}{x^5-1}$$

and that each division at the end would leave zero remainder for the same reason, replacing the original $$x$$ by $$x^5$$

I think if the candidates know what a geometric series is, the question is okay. Indeed, one uses exactly this trick to find the formula for the geometric series, i.e. one writes $$(x-1)\sum_{k=1}^nx^k=x^{n+1}-1$$ to find that $$\sum_{k=1}^\infty x^k=\lim_{n\to\infty}\sum_{k=1}^nx^k=\lim_{n\to\infty}\frac{x^{n+1}-1}{x-1}=\frac{1}{1-x}$$ for $$|x|<1$$. Therefore, it is not too hard to get from $$x^4+x^3+x^2+x+1$$ to $$x^5-1$$. Now you can reduce mod $$x^5-1$$ by substitution $$x^5=1$$.

I think the way one should think about this is to note that $$x^4+x^3+x^2+x+1$$ is the minimal polynomial of any primitive 5th unit root $$\alpha$$. Now $$P(\alpha)=0$$ since $$\alpha^5=1$$ and therefore $$Q$$ devides $$P$$.