# Remainder in polynomial division

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.

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}$$

• How did you get the last step from the one before? – tatan Oct 31 '16 at 16:57
• @robjohn very neat approach. – Siong Thye Goh Oct 31 '16 at 16:58
• @tatan $5a=50k+25$. divides by $5$. – Siong Thye Goh Oct 31 '16 at 16:59
• @SiongThyeGoh Yeah got it. Very compact and nice solution. – tatan Oct 31 '16 at 16:59
• @Rob In fact we can eliminate repeated squaring and solve it with simple mental arithmetic - see my answer. – Bill Dubuque Nov 23 '16 at 1:59

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

• Why the $mod 10$ – nootnoot Oct 31 '16 at 16:25
• We are interested in the unit digit right? $a \mod 10$ gives us that – Siong Thye Goh Oct 31 '16 at 16:26
• this gives $5a\equiv5\pmod{10}$. This only gives us that $a$ is odd. – robjohn Oct 31 '16 at 16:30
• you are right. should take $\mod 10$ later. – Siong Thye Goh Oct 31 '16 at 16:38
• So, how will we find the last digit? – tatan Oct 31 '16 at 16:48

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.

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\\ 3^{50}\!-(-2)^{50} &= 5a \end{align}

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

Thus $\,5a = \color{#0a0}{3^{50}-(-2)^{50}}\equiv 0\pmod{25},\,$ so ${\rm mod}\ 50\,$ either $5a\equiv 0$ or $\,5a\equiv 25.\,$ But since $\,5a\,$ is obviously $\rm\color{#0a0}{odd}$, 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.