It is easy to compute the remainder left behind upon dividing, for example, \( 2^{100} \) by \(3\) using modular arithmetic.

Modular arithmetic is a system of arithmetic in which numbers wrap around, or get ‘reset’ once they reach a certain value. You can think of it as arithmetic using a number circle as opposed to a number line.

Consider a circle having circumference \(2\) units:

First, notice that if you start at the point marked \(0\) and move \(2\) units clockwise, you would return to the point marked zero. Also note that, if we start at \(0\), moving \(3\) units clockwise and \(1\) unit clockwise will result in reaching the same destination. We represent this fact using the notation, \( 3 \equiv 1 \pmod 2 \), which is read as “\(3\) is congruent to \(1\) modulo \(2\)”. This is equivalent to saying that \(3\) and one leave the same remainder when divided by \(2\), or that \( (3 – 1) \) is an integral multiple of \(2\).

Hence, the statement \( x \equiv y \pmod a \) is equivalent to the following statements:

1. \( x-y \) is an integral multiple of \(a\), and
2. \(x\) and \(y\) leave the same remainder upon division by \(a\).

Modular arithmetic is very useful because of some of the properties of congruence relations. If \( a_1 \equiv b_1 \pmod n \) and \( a_2 \equiv b_2 \pmod n\), then the following properties will hold true.

$$ (a_1 + a_2) \equiv (b_1 + b_2) \pmod n $$ $$ (a_1 – a_2) \equiv (b_1 – b_2) \pmod n $$ $$ (a_1 \cdot a_2) \equiv (b_1 \cdot b_2) \pmod n $$

We will find the last property to be particularly useful.

Example 1: Remainder upon dividing \( 2^{100} \) by \( 3 \)

First, we note that \( 2 \equiv -1 \pmod 3 \).

Because of the last property, this implies that \( 2^{100} \equiv (-1)^{100} \pmod 3 \).

Because \( (-1)^{100} = 1 \), the remainder will be 1. This can be verified using Wolfram|Alpha.

Example 2: Remainder upon dividing \( \; 7^{2010} \) by \(25\)

First, we note that \( 7^{2010} = 49^{1005} \). Now, because \( 49 \equiv -1 \pmod {25} \),

$$ 49^{1005} \equiv (-1)^{1005} \pmod {25} $$ $$ \Rightarrow 49^{1005} \equiv -1 \pmod {25} $$ $$ \Rightarrow 49^{1005} \equiv 24 \pmod {25} $$

In the last step, I added \(25\) to the right side of the congruence. I was able to do so because of the first property.

Hence, the remainder on dividing \( 7^{2010} \) by \(25\) is \(24\).