# Applying Fermat's Little Theorem

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,

$x^y \pmod{m} \,.$
powermod(24, 38, 7)
> 2