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?

  • $\begingroup$ Did you read the comment made by Anon? $\endgroup$ – 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).

  • $\begingroup$ 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. $\endgroup$ – Key Ideas Jun 10 '13 at 22:29
  • $\begingroup$ @KeyIdeas Indeed. Anon shows how to do the calculation, while I was explaining how gone used it. updating. $\endgroup$ – Calvin Lin Jun 11 '13 at 0:12
  • $\begingroup$ 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. $\endgroup$ – Key Ideas Jun 11 '13 at 4:01
  • $\begingroup$ @KeyIdeas We're not talking about proving the binomial theorem, but proving that $9 ^10 \equiv 1 \pmod{100}$. $\endgroup$ – Calvin Lin Jun 11 '13 at 4:12
  • $\begingroup$ 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). $\endgroup$ – 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.

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

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.