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

    \begin{equation} a^{m} \equiv _{m} m \end{equation}

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

\begin{equation} 2^{11} \equiv _{11} 2 \implies 2^{10} \equiv _{11} 1. \end{equation}

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\).