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

Here is a cute example of the power of theory of congruences. Monster numbers can be tamed !!

Question :

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

Solution:

A famous mathematician, George Polya said that a good problem solving technique is to solve an analagous less difficult problem.

So, for example, if the problem posed was “find the last two digits of 2479”. How do we go about it? Find the remainder upon division by 100. Now, how does it relate to congruences ? Modulo 100 numbers !

So, the problem reduces to — find out 9^{9^{9}} \equiv 9 \pmod {10}.

Now, what is the stumbling block…the exponent 9^{9} makes the whole problem very ugly. But,

9^{9} \equiv 9 \pmod {10}, which means 9^{9}-9=10k, that is, 9^{9} = 9 + 10k,

also, use the fact 9^{9} \equiv 89 \pmod {100}

Hence, 9^{9^{9}}=9^{9+10k} = 9^{9}.9^{10k}

9^{9^{9}} \pmod {100}  = 9^{9}.9^{10k} \pmod {100} \equiv 89. 9^{10k} \pmod {100}

So, now we need to compute 9^{10k} \pmod {100} = (9^{10})^{k} \pmod {100} = (89.9)^{k} \pmod {100} = 89^{k}. 9^{k} \pmod {100}

Hence, 9^{9^{9}} \pmod {100} \equiv 89^{k+1}.9^{k} \pmod {100} \equiv (89.9)^{k}.89 \pmod {100} \equiv (1)^{k}.89 \pmod {100} \equiv 89 \pmod {100}.

-Nalin Pithwa.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.