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?

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
