Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
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|cite|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

Your Answer


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.