Examples Of Finding Remainders Of Large Numbers

Recall that the following three theorems:

 Theorem (Fermat): If p is a prime, and $(a, p) = 1$ (a and p are relatively prime), then $a^{p-1} \equiv 1 \pmod p$.
 Theorem (Wilson): A positive integer p is prime if and only if $(p - 1)! \equiv -1 \pmod p$.
 Theorem (Euler): For all integers m ≥ 1 and $\phi (m)$ be the number of positive integers less than or equal to m and relatively prime to m, then $a^{\phi (m)} \equiv 1 \pmod m$ whenever $(a, m) = 1$

We will now apply these theorems to finding remainders of rather large numbers.

# Example 1

Calculate the least residue of $2^{345} \pmod {11}$.

We will solve this problem by breaking it down. First note that 2 is not divisible by 11. We know that by Fermat's theorem that since $(2, 11) =1$, then $2^{10} \equiv 1 \pmod {11}$. Let's now rewrite the exponent 345 = 34(10) + 5. Hence it follows that:

(1)
\begin{align} 2^{345} \equiv (2^{10})^{34} \cdot 2^5 \pmod {11} \\ 2 ^{345} \equiv (1)^{34} \cdot 2^5 \pmod {11} \\ 2^{345} \equiv 2^5 \pmod {11} \end{align}

We can easily calculate that $2^5 \equiv 32 \equiv 10 \pmod {11}$. Hence:

(2)
\begin{align} 2^{345} \equiv 10 \pmod {11} \end{align}

So the least residue of 2345 (mod 11) is 10.

# Example 2

Calculate the least residue of $3^{1203} \pmod {17}$.

We first notice that $(3, 17) = 1$, so then by Fermat's theorem $3^{16} \equiv 1 \pmod {17}$. By the division algorithm we can rewrite 1203 as 1203 = 16(75) + 3. Hence it follows that:

(3)
\begin{align} 3^{1203} \equiv (3^{16})^{75} \cdot 3^3 \pmod {17} \\ 3^{1203} \equiv (1)^{75} \cdot 3^3 \pmod {17} \\ 3^{1203} \equiv 27 \pmod {17} \\ 3^{1203} \equiv 10 \pmod {17} \end{align}

Hence:

(4)
\begin{align} 3^{1203} \equiv 10 \pmod {17} \end{align}