Suppose we want to compute \(24^{38} \pmod{7}\). Anything other than \(1\) to the \(38\)th power is very large and could be quite challenging to calculate, especially by hand.
By Fermat's Little Theorem, if \(p\) is prime and \(a\) and \(p\) are co-prime, then,
\[a^{p-1}\equiv 1 \pmod{p}\,. \]First of all, we're working in modulo \(7\) and since \(24 > 7\), we know that \(24^{38} \equiv 3^{38}\) since \(24 \equiv 3 \pmod{7}\).
Applying Fermat's Little Theorem, we know that \(3^{6} \equiv 1 \pmod{7}\). By the law of exponents and division algorithm, we can re-write \(3^{38}\) as \(3^{6\cdot 6 + 2}\). Since we know that \(3^{6}\) is congruent to \(1\) in modulo \(7\), then \((3^{6})^6 \cdot 3^2 \equiv (1)^6\cdot 3^2 = 3^2\). Therefore, we can re-write our original equation and easily solve.
\[ 24^{38} \equiv 3^2 \equiv 2 \pmod{7} \]We can easily verify this using the Julia function powermod which takes three arguments, \(x\), \(y\), and \(m\) such that,
powermod(24, 38, 7)
> 2