Finding the remainder left behind when dividing a large number

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