3
$\begingroup$

How can I complete the following problem using modular arithmetic?

Find the last two digits of $9^{56}$.

I get to the point where I have $729^{18} \times 9^2 \pmod{100}$. What should I do from here?

$\endgroup$
  • 1
    $\begingroup$ I wouldn't do it quite like that. There are various better methods. Try the first few powers of $9$ - do you see a pattern? $\endgroup$ – Mark Bennet May 2 '15 at 17:57
  • $\begingroup$ @user31415 $729^{18} = (9^3)^{18} = 9^{54}$ $\endgroup$ – Joffan May 2 '15 at 18:17
1
$\begingroup$

Another way :

Let $[n]$ be the right-most two digits of $n$. Then, note that $$[9^2]=81,[9^3]=29,[9^4]=61,[9^5]=49,[9^6]=41,$$$$[9^7]=69,[9^8]=21,[9^9]=89,[9^{10}]=\color{red}{01}.$$

Hence, $[9^{56}]=[9^{6}]=41$.

$\endgroup$
10
$\begingroup$

Hint: use a binomial expansion of $$ (10 - 1)^{56} $$

$\endgroup$
  • $\begingroup$ Another hint: the last two terms. $\endgroup$ – mathreadler May 2 '15 at 18:48
  • $\begingroup$ Can you expand your hint into a proper answer? $\endgroup$ – Joffan May 4 '15 at 5:10
3
$\begingroup$

If you don't insist on using a clever method, it actually isn't too hard to just do by hand. When you write out the first few powers of $9$ modulo $100$, you will find (just remember the last two digits in each step) that: $$9^6\equiv 41\mod 100$$

And:

$$9^{10}\equiv 1\mod 100$$

Now we see that:

$$9^{56}=(9^{10})^5\cdot 9^6\equiv 41\mod 100$$

$\endgroup$
1
$\begingroup$

$\bmod 4\!:\ 9^{56}\equiv 1^{56}\equiv 1\,\Rightarrow\, 9^{56}=4m+1$.

$$\bmod 25\!:\ 9^{56}\stackrel{(1)}\equiv 9^{56\pmod{\phi(25)}}\equiv 9^{56\pmod {20}}\equiv 9^{-4}\equiv \left(\frac{1}{81}\right)^2$$

$$\equiv \left(\frac{1+5\cdot 25}{6+3\cdot 25}\right)^2\equiv \left(\frac{126}{6}\right)^2\equiv 21^2\equiv (-4)^2\equiv 16\equiv 4m+1$$

$$\iff 4m\equiv 15\equiv 40\iff m\equiv 10\iff m=25l+10$$

$9^{56}=4(25l+10)+1=100l+41$. In $(1)$ I used Euler's theorem.

$\endgroup$
1
$\begingroup$

By Carmichael's function, the order of any residue of $100$ divides, and is a maximum of, $20$ (the same as for $25$). We see that $9$ is a square, so the maximum order of $9 \bmod 100$ is $10$ (or divides $10$ if it is less). This gives

$$9^{56}\equiv 9^6 \bmod 100$$

Then we can simply multiply a few small powers:

$$9^2 \equiv 81,\quad 9^4 \equiv 61, \quad 9^6 \equiv 41 \equiv 9^{56}$$

(This result also shows - since $9^6 \not\equiv 9$ - that the order of $9 \bmod 100$, not being $2$ or $5$, must be $10$, as others have shown by direct calculation)

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