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?
 A: 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)$. 
A: 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$. 
A: 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
A: 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
A: 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.
A: 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$ 
