Using Fermat's Little Theorem to find remainders My professor does not want us to use mods.
Use Fermat's Little Theorem to find the remainder of $12^{7641}$ divided by $7$.
I have $7 \mid \left(\,12^{7} - 12\,\right)$ and that $12^{7651}=\left(\,12^{7}\,\right)^{1093}$
but I'm basically stuck because a remainder of $12^{1093}$ makes no sense.

By Fermat's Little Theorem we know that $12^6 = 1 \pmod 7$


*

*Now $7641 =6 \times 1273 + 3$. So that $(12^6)^{1273} = 1^{1273} = 1 \pmod 7$    

*hence $12^{7638} = 1 \pmod 7$

*hence $12^{7638} \times 12^3 = 12^3 \pmod 7$

*hence $12^{7641} = 12^3 \pmod 7$



Now $12 = 2^2 3$. Hence $12^3 = 2^6 \times 3^3$


*

*now $2^3 = 1  \pmod 7$

*hence $(2^3)^2 = 1^2 = 1 \pmod 7$ and $3^3 = 6 \pmod 7$

*now we know that $a = b \pmod p$ and $c = d \pmod p$

*then $a \times c = b \times d \pmod p$

*hence $2^6 \times 3^3 = 1 \times 6 \pmod 7$

*hence $12^3 = 6 \pmod 7$

*hence $12^{7641} = 12^3 = 6 \pmod 7$


so the remainder is 6.
