2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

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

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

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.