Remainder in polynomial division

Question

The remainder when $x^{50}$ is divided by $(x-3)(x+2)$ is of the form $ax + b$. Find the units digit of $a$.

I tried to tackle the problem using the polynomial remainder theorem but got stuck as the divisor is a quadratic expression.

Answer 1

Siong Thye Goh has a good idea but we need to work $\bmod 50$.

We can compute the following modular exponentiation using the Square and Multiply Algorithm: $$ \begin{align} x^{50}&=(x-3)(x+2)Q(x)+ax+b\\ (-2)^{50}&\equiv24\equiv-2a+b\pmod{50}\\ 3^{50}&\equiv49\equiv\phantom{-}3a+b\pmod{50} \end{align} $$ Therefore, $$ 25\equiv5a\pmod{50} $$ which means that $$ \bbox[5px,border:2px solid #C0A000]{a\equiv5\pmod{10}} $$

---

Exponentiation Using The Square and Multiply Algorithm $$ \begin{array}{} &\bmod{50}\\ (-2)^1&\equiv-2\\ (-2)^2&\equiv4&\text{square}\\ (-2)^3&\equiv-8&\text{multiply}\\ (-2)^6&\equiv14&\text{square}\\ (-2)^{12}&\equiv-4&\text{square}\\ (-2)^{24}&\equiv16&\text{square}\\ (-2)^{25}&\equiv-32&\text{multiply}\\ (-2)^{50}&\equiv24&\text{square} \end{array} $$ $$ \begin{array}{} &\bmod{50}\\ 3^1&\equiv3\\ 3^2&\equiv9&\text{square}\\ 3^3&\equiv27&\text{multiply}\\ 3^6&\equiv29&\text{square}\\ 3^{12}&\equiv41&\text{square}\\ 3^{24}&\equiv31&\text{square}\\ 3^{25}&\equiv-7&\text{multiply}\\ 3^{50}&\equiv49&\text{square} \end{array} $$

Answer 2

Edit: robjohn's solution is super awesome.

$$x^{50}=A(x-3)(x+2)+ax+b$$

Substitute $x=-2$ and $3$ and take $\mod 10$.

$$ (-2)^{50}= -2a+b $$

$$(3)^{50}= 3a+b $$

$$3^{50}-(-2)^{50}=5a$$

$$(3-(-2))\left( \sum_{i=0}^{49} 3^i(-2)^{49-i} \right)=5a$$

Answer 3

Hint

$x^{50}=(x-3)(x+2)q(x)+ax+b$ (Division algorithm)

Now, take $x=3$ and $x=-2$ to get two equations. Two variables and two equations. Hope you get it.

This is the complete problem. (Use the hint and try yourself first)

Taking $x=3$,

$3^{50}=3a+b,$

Taking $x=-2$

$(-2)^{50}=2^{50}=-2a+b$

Subtracting, we get

$3^{50}-2^{50}=5a\implies 9^{25}-4^{25}=5a$

Firstly, observe that the LHS is divisible by $(9-4)=5$(Why?). So, you get an integer value of $a$. (Just for a check)

$\therefore a= 9^{24}+9^{23}\cdot 4+ 9^{22}\cdot 4^2+...+4^{24}$

Now, you may use modular arithmetic.

$a\equiv 1-4+6-4+6-4+...+6 \equiv 1+12\times 2\equiv 5\pmod{10}$ (Why?)

Hope you get it.

Answer 4

Below we solve it simply - with purely mental arithmetic. By polynomial division with remainder followed by evaluation at $\,x=3,$ and $\,x=-2\,$ we obtain

$$\begin{align} x^{50} &= (x\!-\!3)(x\!+\!2)\, q(x) + ax + b\\ \Rightarrow\quad 3^{50} &= \ \ \ 3a + b\\ (-2)^{50} &= -2a + b\\ \Rightarrow\ \ 3^{50}\!-(-2)^{50} &=\ \ \ 5a \end{align}\ \ \ $$

But $\ 3\equiv -2\pmod{5}\,\Rightarrow\, 3^{50}\equiv (-2)^{50}\,\Rightarrow\, 5a\equiv 0\pmod{25},\,$ by Lemma below.

So ${\rm mod}\ 50\,$ either $5a\equiv 0$ or $\,5a\equiv 25.\,$ But $\,5a = 3^{50}-(-2)^{50}\,$ is odd, so it must be $\,5a\equiv 25\pmod{50}.\,$ Hence $\,a\equiv 5\pmod{10},\,$ by cancelling $\,5$.

---

Lemma $\ \ c \equiv d \pmod n\,\Rightarrow\, c^{nk} \equiv d^{nk} \pmod{n^2}$.

Proof $\ $ By hypothesis $\ c = d+nj\,$ for some integer $\,j\,$ so by the Binomial Theorem $$ c^{nk} = (d+nj)^{nk} = d^{nk} + (\color{#c00}nk)(\color{#c00}nj) d^{nk-1} + (\color{#c00}nj)^{\color{#c00} 2}(\cdots) \equiv d^{nk}\!\! \pmod{\!\color{#c00}{n^2}}$$

Remark $ $ This method of solving for $\,a\,$ may be viewed as Lagrange (or Newton) interpolation, which is a special case of CRT = Chinese remainder theorem.