Etydhv

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,

$$
fracP(x)Q(x)=0
$$

This question was asked in a high school test. (The candidates had at most few minutes per question.) Obviously, the candidate is required to come up with a “trick” rather than doing brute force polynomial division. My question is: How is the candidate supposed to think of the suggested method? Is it obvious? How else could one approach the problem?

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

It's standard technique. $Q$ has a "simpler" multiple $,QR = x^5!-!1,$ so we first reduce $P$ mod $,x^large 5! -! 1$ using $bmod x^large 5-1!:, color#c00x^large 5equiv 1Rightarrow, x^large r+5qequiv x^large r(color#c00x^large 5)^large qequiv x^large r,,$ then reduce that result $bmod Q,,$ i.e.

$$Pbmod Q, =, (Pbmod QR)bmod Qqquad$$

This idea is ubiquitous, e.g. we already use it implicitly in grade school in radix $10$ to determine integer parity: first reduce mod $10$ to get the units digit, then reduce the units digits mod $2,,$ i.e.

$$N bmod 2, = (Nbmod 2cdot 5)bmod 2qquad $$

i.e. an integer has the same parity (even / oddness) as that of its units digit.

See here and its $25$ linked questions for many more examples (some far less trivial).

Remark $ $ Further, there are simple algorithms for recognizing cyclotomics (and products of such), e.g. there it shows that $, x^16+x^14-x^10-x^8-x^6+x^2+1$ is cyclotomic (a factor of $x^60-1).,$

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_ntoinftysum_k=1^nx^k=lim_ntoinftyfracx^n+1-1x-1=frac11-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$.

Let $a$ be zero of $x^4+x^3+x^2+x+1=0$. Obviously $ane 1$. Then $$a^4+a^3+a^2+a+1=0$$
so multiply this with $a-1$ we get $$a^5=1$$ But then $$ Q(a) = a^100a^4+a^90a^3+a^80 a^2+a^70a+1 = a^4+a^3+a^2+a+1=0$$

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

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.