Let’s have some more fun with modulo calculation.

What is (5^{25} \mod 3)?

We can calculate 5^{25} and after that start casting out 3’s. A lot of work.

However; we can start by casting out a 3 before we start raising it to the 25th power. 5 - 3 = 2, so

(5^{25} \mod 3) = (2^{25} \mod 3)

Calculating 2^{25} is still a lot of work. Can we do better. Well, yes!

We can cast out another 3:

2 - 3 = -1

({2}^{25} \mod 3) = ({-1}^{25} \mod 3)

{-1}^{25} = -1 because -1 to any even power is 1 and -1 to any odd power is -1.

Let’s take a step back. What does {-1} \mod 3 mean?

The modulo of a number is the remainder after division.

The remainder of 11 / 3 is 2 because we can repeatedly subtract 3 from 11 and get: 11, 8, 5, 2.

If we continued the repetition we would get: 11, 8, 5, 2, **-1**, -4, -7, etc.

The modulo is the lowest, **positive number** below the number we divide by.

In the range 11, 8, 5, 2, **-1**, -4, -7, … the modulo 3 is **2**.

In plain English, if we get a negative number, we have casted out **too many 3’s**. We have subtracted too many 3’s.

So put one 3 back: -1 + 3 = **2**.

**TLDR;**

5^{25} \mod 3 = 2