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?

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