# divisible by

prove that

divisible by

#### Soroban

MHF Hall of Honor
Hello, dapore!

I haven't solved it yet, but I know a few tricks . . .

Prove that:

. . $$\displaystyle \underbrace{x^{9999} + x^{8888} + x^{7777} + \hdots + x^{1111} + 1}_A\:\text{ is divisible by }\;\underbrace{x^9 + x^8 + x^7 + \hdots + x + 1}_B$$

Multiply $$\displaystyle A$$ by $$\displaystyle \frac{x^{1111}-1}{x^{1111}-1}\!:$$

. . $$\displaystyle A \;=\;\frac{x^{1111}-1}{x^{1111}-1}\cdot\frac{x^{9999} + x^{8888} + x^{7777} + \hdots + x^{1111} + 1}{1}$$ . $$\displaystyle =\;\frac{x^{11,110}-1}{x^{1111}-1}$$

Multiply $$\displaystyle B$$ by $$\displaystyle \frac{x-1}{x-1}\!:$$

. . $$\displaystyle B \;=\; \frac{x-1}{x-1}\cdot\frac{x^9 + x^8 + x^7 + \hdots x + 1}{1} \;=\; \frac{x^{10}-1}{x-1}$$

Hence, we have:

. . $$\displaystyle \frac{A}{B} \;=\;\frac{x^{11,110} - 1}{x^{1111}-1}\cdot\frac{x-1}{x^{10}-1}$$

Does this inspire anyone? . . . Anyone? Anyone?

• #### TKHunny

Only 10 terms? Try long division.

This will not only prove it but produce the result.

No, really. It will be fun. You've been saving that stack of scratch paper too long, anyway.

• dapore

#### TheCoffeeMachine

$$\displaystyle \underbrace{x^{9999}+x^{8888}+x^{7777}+\hdots+x^{1111}+1}_{P(x)}\:\text{ is divisible by}\;\underbrace{x^9 + x^8 + x^7 + \hdots + x + 1}_{Q(x)}$$
We have $$\displaystyle P(x)= Q(x^{1111})$$. Since $$\displaystyle Q(x) = 0$$ for $$\displaystyle x_{k}=\cos\frac{2k\pi}{10}+i\sin\frac{2k\pi}{10}$$, $$\displaystyle \qquad (k = 1, 2, 3, \dots, 9)$$ and $$\displaystyle x_{k}^{1111}=\cos\frac{2222k\pi}{10}+i\sin\frac{2222k\pi}{10}=\cos(222k\pi+\frac{2k\pi}{10})+i\sin(222k\pi+\frac{2k\pi}{10})=x_{k}$$, it follows that $$\displaystyle P(x^{k})=Q(x_{k}^{1111})=Q(x_{k})=0.$$ Therefore, $$\displaystyle Q(x)|P(x)$$. (Clapping)

• dapore and AllanCuz

#### AllanCuz

We have $$\displaystyle P(x)= Q(x^{1111})$$. Since $$\displaystyle Q(x) = 0$$ for $$\displaystyle x_{k}=\cos\frac{2k\pi}{10}+i\sin\frac{2k\pi}{10}$$, $$\displaystyle \qquad (k = 1, 2, 3, \dots, 9)$$ and $$\displaystyle x_{k}^{1111}=\cos\frac{2222k\pi}{10}+i\sin\frac{2222k\pi}{10}=\cos(222k\pi+\frac{2k\pi}{10})+i\sin(222k\pi+\frac{2k\pi}{10})=x_{k}$$, it follows that $$\displaystyle P(x^{k})=Q(x_{k}^{1111})=Q(x_{k})=0.$$ Therefore, $$\displaystyle Q(x)|P(x)$$. (Clapping)
Okay I'm a little slow...but what?! We came up with $$\displaystyle x_k = e^{ i \frac{2k \pi }{10} }$$ how?

• dapore

#### TheCoffeeMachine

Okay I'm a little slow...but what?! We came up with $$\displaystyle x_k = e^{ i \frac{2k \pi }{10} }$$ how?
We see that $$\displaystyle G(x) = \dfrac{x^{10}-1}{x-1}$$ (by either using Soroban's trick or just recalling that $$\displaystyle a+ar+ar^2+ar^3+ \cdots+ar^{n}=\sum_{k=0}^{n}ar^k= a\left(\frac{1-r^{n+1}}{1-r}\right)$$ and realising that $$\displaystyle G(x)$$ is a case of that where $$\displaystyle a = 1$$ and $$\displaystyle r = x$$, and $$\displaystyle n = 9$$). We have $$\displaystyle G(x) = 0 \Rightarrow\dfrac{x^{10}-1}{x-1} = 0 \Rightarrow x^{10}-1 = 0 \Rightarrow x_{k} = e^{ i\frac{2k \pi }{10}}$$, which are all roots of $$\displaystyle g(x)$$, except of course $$\displaystyle x = 1$$. Thus $$\displaystyle G(x) = 0[/Math] for \(\displaystyle x_k = e^{ i \frac{2k \pi }{10}}$$\)$$\displaystyle , \(\displaystyle (1\le{k}\le{9}).$$\)

Last edited:
• dapore and AllanCuz