# How is $9^{40}\equiv\ 1 \pmod {100}$?

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 $9^{9^{9}}$

• "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$? Commented Dec 22, 2015 at 17:14
• you're right i was thinking only of the the units digit Commented Dec 22, 2015 at 17:17
• @pyUser: When a more experienced user edits your post, learn from it, don't roll back to your own improperly formatted version. Commented Dec 22, 2015 at 17:18
• @AlexM. can you teach me how to apply edits from one version to another one? or did you just manually MathJax the thing? Commented Dec 22, 2015 at 17:19
• 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$. Commented Dec 22, 2015 at 17:24

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.

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

• Better formatting if you write 9^2\equiv -19\pmod{100} yielding $$9^2\equiv -19\pmod{100}$$ Commented Dec 22, 2015 at 18:01

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

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

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

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.

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)

To answer your question, we know the last digit cannot be 0, as this would make it divisible by 10. There is no such restriction on the second to last digit.

When taking mod 100, one must divide the result by 100, so $$9^{40}$$ becomes much smaller. Euler's theorem says that this much smaller value is 1, and this can be verified by computation as shown in the other answers.