I'm having a bit of trouble computing $\bmod{mod}$s of large numbers using Fermat's Little Theorem.
For example, how would you compute $7^{435627650}\mod 13$? The solution given is
$435627650\mod 12=2,$ so $7^2\mod{13} = 10.$
In general, how does one solve this type of question with large exponents and mods by paper and pencil? I'm also a bit confused about where the $12$ came from and how this problem was solved.
Best Answer
Say we're given a number $a$ and some big exponent $N$ and we want to compute $$a^N\mod p.$$ We know that $a^{p-1}\equiv 1 \pmod p$. In general, if $a_1\equiv x_1\pmod{n}$ and $a_2\equiv x_2\pmod{n}$, then $a_1a_2\equiv x_1x_2\pmod{n}$. Therefore, we have that $$a^{k(p-1)}=\underbrace{a^{p-1}\cdot a^{p-1}\cdot \cdots \cdot a^{p-1}}_{k\text{ times}}\equiv \underbrace{1\cdot 1 \cdot \cdots \cdot 1}_{k\text{ times}}\pmod p\equiv 1 \pmod p. $$ Thus we can ignore the part of $N$ which is the biggest multiple of $p-1$. Writing $N=m(p-1)+r$ where $0\leq r < p-1$, we have $$\begin{eqnarray*}a^N &=& a^{m(p-1)+r}\\&=&\left(a^{p-1}\right)^ma^r\\ &\equiv& 1^ma^r\pmod p\\ &\equiv& a^r\pmod p.\end{eqnarray*}$$ Thus we have reduced this to the much easier problem of computing $a^r\mod p$. If this is still too hard to work out with pen and paper, you might try using the method of repeat squaring.