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 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?

share|improve this question
    
Did you read the comment made by Anon? –  Calvin Lin Jun 10 '13 at 5:09
add comment

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
    
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
show 2 more comments

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.

share|improve this answer
2  
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. –  andybenji Jun 11 '13 at 5:38
add comment

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.