# Clarification needed on finding last two digits of $9^{9^9}$

I stumbled across this problem here. In the answer given by the user Gone, I don't see how he makes use of the second line in the last line. Could someone explain why he calculated $9^{10}$ via binomial theorem and where it is applied?

• Did you read the comment made by Anon? – Calvin Lin Jun 10 '13 at 5:09

The idea is that he wanted to calculate a value of $N$ such that $9^N \equiv 1 \pmod{100}$. (He determined that $N = 10$ would work.)

Once we found such an $N$, in order to calculate $9^M \pmod{100}$, we merely need to look at $M \pmod{N}$, and then we know that

$9 ^ M \equiv 9^{M \pmod{N}} \pmod{100}$.

In particular, this gives us that

$$9^{9^9} \equiv 9^{ 9 ^ 9 \pmod{10} } \pmod{100}.$$

As to how it is proven, you can read the answer by anon (to the original question).

• Why do you refer to anon's answer for "how it is used"? Anon's answer is a solution using Euler's totient function (the final step of the OP's method), but Gone's answer avoids that, using only the binomial theorem and modular arithmetic. – Key Ideas Jun 10 '13 at 22:29
• @KeyIdeas Indeed. Anon shows how to do the calculation, while I was explaining how gone used it. updating. – Calvin Lin Jun 11 '13 at 0:12
• I still don't understand your edit. Both anon and Gone apply a binomial expansion (for different powers). Neither "proves" the binomial theorem - they simply invoke it. I'll add an answer explaining the matter more carefully. – Key Ideas Jun 11 '13 at 4:01
• @KeyIdeas We're not talking about proving the binomial theorem, but proving that $9 ^10 \equiv 1 \pmod{100}$. – Calvin Lin Jun 11 '13 at 4:12
• Read closer, Gone proves it using the binomial formula just like anon does for $\,9^9\,$ (though Gone doesn't explicitly write out the binomial coefs as does anon). – Key Ideas Jun 11 '13 at 4:22

The binomial theorem states $$(a + b)^n = \sum_{i = 0}^n \binom{n}{i} a^i b^{n-i}$$ Gone made use of the fact that $\binom{n}{i}$ is an integer, along with the fact that $10|10^k$ for any $k \geq 1$. So we see that $10| \binom{10}{i}10^i (-1)^{10-i}$ for any $i \geq 1$, and we may reduce the expression

$$9 ^ {10} = (10 - 1)^{10} = \sum_{i = 0}^{10} \binom{10}{i}10^i (-1)^{10-i} = 1 + 10 \cdot 10 \cdot(-1) + 90 \cdot 10^2 + \ldots$$

modulo 10 to see $$9^{10} = 1 + 0 + 0 + \ldots$$

Although, we have an even simpler way... In the same vein,

$$9^{10} = (10-1)^{10} \equiv -1^{10} \equiv 1$$

Without having to do any binomial work.

• I'm not sure about your last line. We want to calculate it mod 100, not mod 10. – Calvin Lin Jun 10 '13 at 5:39
• Oh okay, I had thought it said mod 10. – Andrew Maurer Jun 11 '13 at 5:38