Find the reminder when is divided by ?
Source: NCTM Mathematics Teacher, October 2006
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 .
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 .