10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mathreadler Feb 27 '15 at 18:17
  • $\begingroup$ Related: How do I compute $a^b\,\bmod c$ by hand? $\endgroup$ – punctured dusk Aug 20 '15 at 11:45
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – anon Sep 18 '11 at 7:09
  • $\begingroup$ 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. $\endgroup$ – Logan M Sep 18 '11 at 7:16
20
$\begingroup$

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

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

So $\rm \bmod 100\!:\, \ 9^{\large 9^{\LARGE 9}}\!\!\equiv\ 9^{\large 9^{\LARGE 9}\, mod\ \color{#c00}{10}} \equiv\ 9^{\large (-1)^{\LARGE 9}}\!\! \equiv 9^{\large -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}{\large 10}}\equiv 1}\!\!\pmod{\!m},\,\ J\equiv K\!\!\!\pmod{\!\color{#c00}{10}}\ \,\Rightarrow\,\ a^{\large J}\equiv a^{\large 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^{\large J}\! = a^{\large K+10N}\! = a^{\large K} (\color{#c00}{\large a^{10}})^{\large N}\!\equiv a^{\large K} \color{#c00}1^{\large N}\!\equiv a^{\large 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.

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – anon Sep 18 '11 at 7:39
17
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$ ... $\endgroup$ – Quixotic Nov 11 '11 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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