<s>[INST] 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?
 [/INST] 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
</s>