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?

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$ 
