# A calculus of the absurd

##### 19.2.3 Fermat’s little theorem

There is also Fermat’s non-little theorem (called Fermat’s Last Theorem which was unproven for 358 years).

• Theorem 19.2.4 (Fermat’s little theorem) Let $$a$$ and $$m$$ be two coprime integers (i.e. $$\gcd (a, m) = 1$$) then

$$a^{m} \equiv _{m} m$$

todo: proof (it’s by induction, or using some abstract algebra).

• Example 19.2.2 Find the value of

$R_{11}\left (2^{3^{40}}\right )$

.

That is, the remainder when $$2^{3^{40}}$$ is divided by $$11$$.

The first thing to do is quickly write down that by Fermat’s Little Theorem (Theorem 19.2.4) we know that

$$2^{11} \equiv _{11} 2 \implies 2^{10} \equiv _{11} 1.$$

Therefore, if we let $$q$$ be the quotient and $$r$$ the remainder of dividing $$3^{40}$$ by $$10$$, we can then write

\begin{align} 2^{3^{40}} &\equiv _{11} 2^{q \times 10 + r} \\ &\equiv _{11} 2^{q \times 10} 2^{r} \\ &\equiv _{11} \left (2^{10}\right )^{q} 2^{r} \\ &\equiv _{11} 1^{q} 2^{r} \\ &\equiv _{11} 2^{r} \end{align}

We have substantially simplified this problem because it is now only a problem of finding $$r$$, which we can do by computing $$3^{40} \mod 10$$. This requires a bit of arithmetic, but (if you know the rules of modular arithmetic) nothing too horrible;

\begin{align} 3^{40} &\equiv _{11} \\ &\equiv _{11} (3^{4})^{10} \\ &\equiv _{11} 1^{10} \\ &\equiv _{11} 1. \end{align}

Therefore, the answer is that $$R_{11}(2^{3^{40}}) = R_{11}(2) = 2$$.