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)We can easily calculate that $2^5 \equiv 32 \equiv 10 \pmod {11}$. Hence:

(2)So the least residue of 2^{345} (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)Hence:

(4)