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'm new to modular exponentiation. Is this procecdure correct?

$$5^{300} \bmod 11$$


$$5^{1} \bmod 11 = 5\\ 5^{2} \bmod 11 = 3\\ 5^{4} \bmod 11 = 3^2 \bmod 11 = 9\\ 5^{8} \bmod 11 = 9^2\bmod 11 = 4\\ 5^{16} \bmod 11 = 4^2 \bmod 11 = 5\\ 5^{32} \bmod 11 = 5^2 \bmod 11 = 3$$


$$5^{300} = 3 + 3 + 3 + 3 +3 +3 + 3 + 3 +3 +4 + 9$$

share|improve this question
    
you didn't explain anything, why are you adding all those numbers? –  Jorge Fernández Jul 3 at 18:11
    
You were doing well until that last line. What is up with adding all of those numbers? –  Paul Z Jul 3 at 18:11
    
Now use $5^{300}=5^{256}\cdot5^{32}\cdot5^8\cdot5^4$. –  user84413 Jul 3 at 18:13

3 Answers 3

up vote 6 down vote accepted

You're almost there. Instead of your last line, you want: $$5^{300} \equiv 5^{4}5^{8}5^{32}5^{256} \pmod{11}$$ Now you replace each of those factors with the modular equivalent you found before (e.g. $5^4\implies 9$)

Let me know if you need more help.

share|improve this answer

You could also notice $11$ is prime, so by Fermat's Little Theorem $ 5^{10}\equiv 1 \bmod 11$

from here we get $5^{300}=(5^{10})^{30}\equiv1^{30}\equiv 1 \bmod 11$

share|improve this answer

I see what you were trying to do with adding the numbers at the end.

Multiply them instead, and take that product $\mod 11$.

share|improve this answer

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.