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.

For an assignment, I've been asked to evaluate $7^{10507} \bmod 13$.

I know it's possible to do this using binary fast exponentiation - in fact the question refers to a previous question where I calculated $7^{12} \bmod 13$ to help prove $13$ is prime using Fermat's Little Theorem.

I could simply perform the exponentiation, but I feel like I'm missing some way to simplify the question here - why bother referencing the $7^{12}$ question if I couldn't somehow use it to simplify my task.

Is there some sort of simplification I can perform here? Am I missing something?

share|improve this question
1  
How did you "prove $13$ is prime using Fermat's Little Theorem"? The existence of Carmichael numbers shows that you can have a composite number $n$ such that $b^{n-1}\equiv 1 \pmod{n}$ for all $b$ such that $\gcd(b,n)=1$. Of course, you could check all numbers $1,2,3,\ldots,n-1$ to see if they satisfy $b^{n-1}\equiv 1\pmod{n}$, but you might as well check for gcds in that case... –  Arturo Magidin Jan 30 '11 at 21:05
add comment

1 Answer 1

up vote 5 down vote accepted

If you can prove $7^a \equiv 1 \pmod{13}$ for some $a$, then $7^{ka} \equiv 1$ for any natural $k$. Then $7^{(ka+b)} \equiv 7^b$, and you can reduce the exponent mod $a$.

share|improve this answer
    
Perfect, that makes sense. I don't know why I didn't see it. Thanks! –  Zxaos Jan 30 '11 at 18:30
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.