Take the 2-minute tour ×
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.

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
    
Unless I made an error, the cycle is: 1, 9, 81, 29, 61, 49, 41, 69, 21, 89 Which is 10 numbers, so now you need to find 9^9 mod 10, 9^9 = (10-1)^9 and you see that it will be (-1)^9 mod 10. –  mathreadler Feb 27 at 18:17

3 Answers 3

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

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

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

Hence $\rm\ mod\ 100:\ \ 9^{\large 9^{\Large 9}}\!\equiv\ 9^{\large 9^{\Large 9}\, mod\ \color{#c00}{10}}\ \equiv\ 9^{(-1)^{\Large 9}}\! \equiv 9^{-1}\equiv\ \dfrac{1}9\ \equiv\ \dfrac{-99}9\ \equiv\ {-}11\ \equiv\ 89 $

Remark $ $ Above we used the useful fact that if the powers of $\,a=9\,$ repeat with period length $\color{#c00}{10}\,$ then all exponents on $\,a\,$ can be taken modulo $\,\color{#c00}{10}.\,$ Said more precisely we used the following

$$\ \ \color{#c00}{a^{\color{#c00}{10}}\equiv 1}\!\!\pmod{\!m},\,\ J\equiv K\!\!\!\pmod{\!\color{#c00}{10}}\ \,\Rightarrow\,\ a^J\equiv a^K\!\!\!\!\pmod{\!m}$$

for the specific values $\ a=9,\,$ and $\,J = 9^{\large 9},\,$ and $\,K = (9^{\large 9}\,{\rm mod}\ 10).\,$ A proof is easy:

$$ J = K\! +\! 10N\,\Rightarrow\, a^J\! = a^{K+10N}\! = a^K (\color{#c00}{a^{10}})^N\!\equiv a^K \color{#c00}1^N\!\equiv a^K\!\!\!\!\pmod{\!m}\qquad $$

where we have employed the $ $ Congruence Product and Power Rules.

Beware $ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

share|improve this answer
5  
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

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.