Journey into cryptography

# Modular arithmetic

## An introduction to modular math

When we divide two integers, use the following equation:

\dfrac{A}{B} = Q \text{ remainder } R

A is the dividend.
B is the divisor.
Q is the quotient.
R is the remainder.

Sometimes, we are only interested in what the remainder is when we divide A by B.
For these cases, there is an operator called the modulo operator, abbreviated as "mod".

Using the same A, B, Q, and R as above, we would have A \text{ mod } B = R

We would say, "A modulo B is congruent to R." Where B is referred to as the modulus.

For example:

\begin{eqnarray} \dfrac{13}{5} &=& 2 \text{ remainder } \bf{3} \\ 13 \text{ mod } 5 &=& \bf{3} \\ \end{eqnarray}

## Visualize modulus with clocks

Observe what happens when we increment numbers by one and then divide them by 3:

\begin{eqnarray} \frac{0}{3} &=& 0 \text { remainder } \bf{0} \\ \frac{1}{3} &=& 0 \text { remainder } \bf{1} \\ \frac{2}{3} &=& 0 \text { remainder } \bf{2} \\ \frac{3}{3} &=& 1 \text { remainder } \bf{0} \\ \frac{4}{3} &=& 1 \text { remainder } \bf{1} \\ \frac{5}{3} &=& 1 \text { remainder } \bf{2} \\ \frac{6}{3} &=& 2 \text { remainder } \bf{0} \end{eqnarray}

The remainder starts at zero and increases by one each time until the number reaches one less than the number we are dividing by. After that, the sequence repeats.

We can visualize the modulo operator by using circles. We write "0" at the top of a circle and continue clockwise writing integers starting with "1" up to one less than the modulus.

For example, a clock with the 12 replaced by a zero would be the circle for a modulus of 12.

To find the result of A \text{ mod } B , we can follow these steps:

1. Construct this clock for size B
2. Start at zero and move around the clock A steps.
3. Wherever we land is our solution.

Note: If the number is positive, we step clockwise; if it's negative, we step counter-clockwise.

## Examples

### 8 \text{ mod } 4 = ?

With a modulus of 4, we make a clock with numbers 0, 1, 2, 3.
We start at zero and go through eight numbers in a clockwise sequence: 1, 2, 3, 0, 1, 2, 3, 0.

We ended up at 0, so 8 \text{ mod } 4 = \bf{0}.

### 7 \text{ mod } 2 = ?

With a modulus of 2, we make a clock with numbers 0, 1.
We start at zero and go through seven numbers in a clockwise sequence: 1, 0, 1, 0, 1, 0, 1.

We ended up at 1, so 7 \text{ mod } 2 = \bf{1}.

### -5 \text{ mod } 3 = ?

With a modulus of 3, we make a clock with numbers 0, 1, 2.
We start at zero and go through five numbers in counter-clockwise sequence since the five is negative: 2, 1, 0, 2, 1.

We ended up at 1, so -5 \text{ mod } 3 = \bf{1}.

## Conclusion

If we have A \text{ mod } B and we increase A by a multiple of \bf{B}, we will end up in the same spot, i.e.

A \text{ mod } B = (A + K \cdot B) \text{ mod } B for any integer \bf{K}.

For example:

\begin{eqnarray} 3 \text{ mod } 10 = 3 \\ 13 \text{ mod } 10 = 3 \\ 23 \text{ mod } 10 = 3 \\ 33 \text{ mod } 10 = 3 \\ \end{eqnarray}

### mod in programming languages and calculators

Many programming languages, and calculators, have a mod operator, typically represented with the % symbol. If you calculate the result of a negative number, some languages will give you a negative result.
e.g.

-5 % 3 = -2.In a future article we will explain, why this happens, and what it means.

### Congruence Modulo

You may see an expression like:

A \equiv B\ (\text{mod } C)

This says that A is congruent to B modulo C. It is similar to the expressions we used here, but not quite the same.

In the next article we will explain what it means and how it is related to the expressions above.