It is easy to compute the remainder left behind upon dividing, for example, 2100 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.

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$.