2
$\begingroup$

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?

  • 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...2011-01-30

1 Answers 1

5

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

  • 0
    Perfect, that makes sense. I don't know why I didn't see it. Thanks!2011-01-30