1
$\begingroup$

By Euler's theorem, $a^{\varphi(100)} \equiv\ 1 \pmod {100}$.

We know that the last two digits of $9^{40}$ are non-zero. So they can't even be $01$.

Since $1\equiv\ 1 \pmod {100}$, how come $9^{40}\equiv\ 1 \pmod {100}$?

I have looked at: Find the last two digits of $9^{{9}^{9}}$,

Find the last two digits of the number $9^{9^9}$ ,

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

$\endgroup$
6
  • $\begingroup$ "We know that the last two digits of $9^{40}$ are non-zero." That doesn't mean neither digit is zero; it just means they can't both be zero. So why do you think it can't be $01$? $\endgroup$ – Erick Wong Dec 22 '15 at 17:14
  • 1
    $\begingroup$ you're right i was thinking only of the the units digit $\endgroup$ – AkaiShuichi Dec 22 '15 at 17:17
  • 2
    $\begingroup$ @pyUser: When a more experienced user edits your post, learn from it, don't roll back to your own improperly formatted version. $\endgroup$ – Alex M. Dec 22 '15 at 17:18
  • $\begingroup$ @AlexM. can you teach me how to apply edits from one version to another one? or did you just manually MathJax the thing? $\endgroup$ – gt6989b Dec 22 '15 at 17:19
  • $\begingroup$ You quoted one way of doing it. We have $\varphi(100)=\varphi(25)\varphi(4)=40$. So $9^{40}\equiv 1\pmod{100}$, the last two digits, going righttwards, are $0$ and $1$. $\endgroup$ – André Nicolas Dec 22 '15 at 17:24
10
$\begingroup$

By binomial theorem:

$$(10-1)^{40} = \sum_{i=0}^{40} \binom{40}{i}(-1)^{40-i}10^{i}$$

Modulo $10^2$, you only need to look at $i=0,1$.

So: $$9^{40}\equiv (-1)^{40} + \binom{40}{1}(-1)^{39}\cdot 10 \equiv (-1)^{40}\equiv 1\pmod{100}$$

Note that this works for $9^{10}$, too.

$\endgroup$
5
$\begingroup$

$9^2\equiv\ -19\ (mod100)$

$9^4 \equiv\ 61\ (mod 100)$

$9^8\equiv\ 21 \ (mod 100)$

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

$9^{40}\equiv\ 1 \ (mod 100)$

$\endgroup$
1
  • 2
    $\begingroup$ Better formatting if you write 9^2\equiv -19\pmod{100} yielding $$9^2\equiv -19\pmod{100}$$ $\endgroup$ – Thomas Andrews Dec 22 '15 at 18:01
2
$\begingroup$

Calculate $$9^{10} = 3486784401$$ So $$9^{40} \mod 100 \equiv (9^{10}\mod 100)^4 \mod 100 $$ $$\equiv(1)^4 \mod 100 \equiv 1 \mod 100$$

$\endgroup$
4
  • $\begingroup$ How did you go about your third step? $\endgroup$ – AkaiShuichi Dec 22 '15 at 17:20
  • $\begingroup$ $x^y \mod m$ is the same as $(x \mod m)^y \mod m$. You can move the $\mod$ function into multiplies, etc. $\endgroup$ – amcalde Dec 22 '15 at 17:22
  • $\begingroup$ i was talking about the (1)^4 part $\endgroup$ – AkaiShuichi Dec 22 '15 at 17:23
  • $\begingroup$ In the first calculation I showed that $9^{10} \equiv 1 \mod 100$. $\endgroup$ – amcalde Dec 22 '15 at 17:24
1
$\begingroup$

Note that $$99^2=9801\equiv 1\pmod{100}\implies99^{40}\equiv 1\pmod{100}\implies9^{40}11^{40}\equiv 1\pmod{100}$$

$$9^{40}\equiv 1\pmod{100}$$

$\endgroup$
1
$\begingroup$

It is straightforward $9^{40} = 81^{20} = 6561^{10} \equiv 61^{10} \pmod{100} = 3721^5 \pmod{100} \equiv\ 21^5 \pmod{100}$
$= 441 \times 441 \times 21 \pmod{100}\equiv\ 41 \times 41 \times 21 \pmod{100}$
$= 35301 \pmod{100} \equiv\ 1 \ \pmod{100}$

and this is just one of the many many routes you could take.

$\endgroup$
1
$\begingroup$

If you want to avoid the equation

$9^{40}=147808829414345923316083210206383297601$,

the question is how low you prefer your numbers to be.

One alternative is using $40=4*2*5$ (and 7 digits for the last operation).

$9^4=61$ (mod 100)

$61^2=21$ (mod 100), and

$21^5=01$ (mod 100)

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