Find the reminder when is divided by ?

Source: NCTM Mathematics Teacher, October 2006

**Solution
** is such a large number that it is impractical to use modulo arithmetic to find the remainder. So we are going to find the remainders of a few powers of and hope to see a pattern emerge.

Remainders when are divided by

The pattern of remainders is . The remainder equals when the even exponent is the product of and an even number, for example, the remainder of equals because . The remainder equals when the even exponent is the product of and an odd number, for example, the remainder of equals because .

Since , the remainder of divided by equals .

**Answer**:

**Alternative solution
**We can group the powers according to their remainders as follows:

This is exactly what modulo arithmetic does, divide the whole numbers into four groups

Since divided by will have the same remainder as divided by .