Polynomial division by polynomial without remainder

Question

I have two polynomials: $$ Q(x)=x^{624} + x^{524} + x^{424} + x^{324} + x^{224} + x^{124} + x^{n} $$ $$ P(x) = x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1 $$

And the question: what is the largest natural value of the number $n \leq 100 $ at which the polynomial $Q(x)$ is divisible without reminder by $P(x)$?

I have no idea about solution, I even don't know what area of math it is.

It might help to know that $\sum_{i=0}^n x^i = (x^{n+1}-1)/(x-1)$, and that $x^p -1$ divides $x^q-1$ whenever $p$ divides $q$. — eyeballfrog, Jul 12 '22 at 13:33
$P(x)(x-1)=x^7+x^6+\ldots+x-x^6-x^5-\ldots-1=x^7-1$, then $R(x)=\frac{Q(x)}{P(x)}=\frac{Q(x)(x-1)}{x^7-1}$. For $R(x)$ to be polynomial, $Q(x)(x-1)$ must be divisible by $x^7-1$. — Ivan Kaznacheyeu, Jul 12 '22 at 13:59
One can show that $Q(x)$ divides $P(x)$ at $n=24$, then one can consider conditions for $Q(x)=Q_{24}(x)+x^{n}-x^{24}$ to be divisible by $P(x)$. — Ivan Kaznacheyeu, Jul 12 '22 at 14:05
Another path forward: for which $k$ is it true that $P(x) | P(x^k)$? — eyeballfrog, Jul 12 '22 at 14:10

Sam Antonyan · Accepted Answer · 2022-07-12T15:48:37.600

First, using the geometric series formula, it is easy to see that

$$ P(x) = \sum_{i=0}^6 x^i = \frac{x^7-1}{x-1} $$

If we let $H(x) = Q(x)/P(x)$ for some polynomial $H(x)$, then rearranging the equation gives the following:

$$ (x-1)Q(x) = (x^7-1)H(x)\\ x^{625}-x^{624} + x^{525}-x^{524} + \dots+ x^{125}-x^{124} + x^{n+1}-x^n = (x^7-1)H(x) $$

Notice that we can reduce the powers in the left side. Pick any of the terms, for example, $x^{625}$. Then, by letting $H(x) = x^{617} + J(x)$, we get

$$ x^{625}-x^{624} + x^{525}-x^{524} + \dots+ x^{125}-x^{124} + x^{n+1}-x^n = x^{625}-x^{618} + (x^7-1)J(x)\\ x^{618}-x^{624} + x^{525}-x^{524} + \dots+ x^{125}-x^{124} + x^{n+1}-x^n = (x^7-1)J(x) $$

The right side of the equation hasn't changed since $J(x)$ is a polynomial just like $H(x)$. So, we managed to reduce the term $x^{625}$ to $x^{618}$. Since nothing is special about $x^{625}$, we could have reduced the power of each term in the left side similarly. And every time we do so, the power of the term decreases by 7.

Once we realize this, we can keep decreasing the powers of the terms until they cancel out. For example, notice that $625\equiv 324\pmod 7$, so if we decrease decrease the power of $x^{625}$ $ 43$ times, we would get $x^{324}$, which will cancel out with $-x^{324}$. Similarly, $x^{525}$ will cancel out with $-x^{224}$, $x^{425}$ will cancel out with $-x^{124}$, $-x^{624}$ will cancel out with $x^{225}$, $-x^{524}$ will cancel out with $x^{125}$. We are left with $-x^{424} + x^{325} + x^{n+1}-x^{n}$. We need to find the largest $n<100$ to make everything cancel out. Since $424\equiv 4\pmod 7$ and $325\equiv 3\pmod 7$, we need $n+1\equiv 4\pmod 7$, $n\equiv 3\pmod 7$. And the largest $n<100$ with a remainder of $3$ when divided by $7$ is $94$.

Thank you for your answer, but it seems that $(x-1)P(x) = (x^{7}-1)H(x)$ should be $(x-1)Q(x) = (x^{7}-1)H(x)$... — Noerigarnhy, Jul 12 '22 at 15:34

Polynomial division by polynomial without remainder

1 Answers1