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$? – Erick Wong Dec 22 '15 at 17:14
• you're right i was thinking only of the the units digit – AkaiShuichi Dec 22 '15 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. – Alex M. Dec 22 '15 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? – gt6989b Dec 22 '15 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$. – André Nicolas Dec 22 '15 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}$$ – Thomas Andrews Dec 22 '15 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? – AkaiShuichi Dec 22 '15 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. – amcalde Dec 22 '15 at 17:22
• i was talking about the (1)^4 part – AkaiShuichi Dec 22 '15 at 17:23
• In the first calculation I showed that $9^{10} \equiv 1 \mod 100$. – amcalde Dec 22 '15 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)