Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 8 down vote favorite
7

I tried to calculate the last two digits of $9^{9^9}$ using Euler's Totient theorem, what I got is that it is same as the last two digits of $9^9$.

How do I proceed further?

share|improve this question

3 Answers

up vote 2 down vote accepted

At this point, it would seem to me the easiest thing to do is just do $9^9 \mod 100$ by hand. The computation should only take a few minutes. In particular, you can compute $9^3$ and then cube that.

share|improve this answer
Another route is 9*((9^2)^2)^2 mod 100, because repeated modular squaring is faster and just about as easy as repeated modular multiplication. – anon Sep 18 '11 at 7:09
Both take 4 multiplications in this case. For me this was faster because I knew $9^3=729$ off the top of my head, but repeated squaring is certainly faster in most cases. – Logan Maingi Sep 18 '11 at 7:16
up vote 15 down vote

Euler's Theorem is not needed. It can be solved completely using only the Binomial Theorem:

$$\rm 9^{10}\: =\ (10-1)^{10} =\: (-1)^{10} - 10\cdot 10 + 10^2\:(\cdots)\ \equiv\ 1\ \ (mod\ 100)$$

Hence $\rm\ mod\ 100:\ \ 9^{\:9^9}\!\equiv\ 9^{\:9^9\ mod\ 10}\ \equiv\ 9^{\:(-1)^9}\! \equiv\ 1/9\ \equiv\ {-99}/9\ \equiv\ {-}11\ \equiv\ 89\:. $

share|improve this answer
3  
Nice, you went and applied BT to the original problem. It should be noted that you chose to look at $9^{10}$ because all but the first and second terms invariably vanish, but choosing an exponent of $10$ makes the second vanish as well. And $1/9\equiv-99/9$ was a fast way to compute a modular inverse. – anon Sep 18 '11 at 7:39
up vote 13 down vote

By the binomial theorem, we have $$(-1+10)^9\equiv{9\choose0}(-1)^910^0+{9\choose1}(-1)^810^1+{9\choose2}(-1)^7{\color{Red}{10^2}}+\cdots$$ $$\equiv-1+90=89\pmod{10^2}.$$ (All summands with powers of $10$ greater than $1$, the first instance in red, can be ignored.)

share|improve this answer
Decent explanation +1; I am wondering how the OP is using Euler theorem for the reduction?, If am not wrong it gives $9^{40} \equiv 1 \pmod {100}$ ... – Quixotic Nov 11 '11 at 6:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.