# Modular Numbers and Cryptography

## Modular Arithmetic

In mathematicsmodular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

Let's use the hours of a clock as an example, except we will start with 0 instead of 12 on top. Starting at noon, the hour hand goes in the order:

$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, \ldots$

You can see the numbers continue to "wrap around" every 12 count. We called this count in modulo 12. In modulo 3, we "wrap around" every 3 count

$1, 2, 0, 1, 2, 0 \ldots$

All integers can be expressed as $$0, 1$$, or $$2$$ in modulo 3, we give these set of integers that can be represented with $$0, 1$$, or $$2$$ in modulo 3 the name residue classes. In general, for any natural number n, the module n residues are the integers that are whole numbers less than n: meaning you can represented from 0 to $$n-1$$

 We say that $$a$$ is the modulo-$$m$$ residue of $$n$$ when $$n \equiv a \pmod{m},$$ and $$0 \leq a ## Congruence We saw above that all of the integers can be represented by one of the modulo 3 residues. However, multiple integers can be represented as the same residue. For example, if we found 4 in modulo 3, we count four residues in order \(0, 1, 2, 0$$. So 4 is represented by the residue 0 in modulo 3.

Now 7 in modulo 3, we count seven residues in order $$0, 1, 2, 0, 1, 2, 0$$. So 7 is also represented by the residue 0 in modulo 3.

So we say that 0, 4, and 7 are congruent in modulo 3.

$1 \equiv 4 \equiv 7 \pmod{3}$

The $$\pmod{3}$$ tells us that we are working with the integers in modulo 3. Notice that the difference between congruent numbers in modulo 3 is also 3.

 Two integers $$a$$ and $$b$$ are congruent in modulo $$n$$ when $$a-b$$ is a multiple of $$n$$. In other words, $$a \equiv b \pmod{n}$$ when $$\frac{a-b}{n}$$ is an integer. Otherwise, $$a \not \equiv b \pmod{n}$$, which means that $$a$$ and $$b$$ are not congruent in modulo $$n$$.

### Examples

Find the following residues in the stated modulo.

1. 1$$5 \pmod{4}$$

One method is to count 15 residues in modulo 4.

$1,2,3,0,1,2,3,0,1,2,3,0,1,2,3$

Thus, $$15\equiv 3 \pmod{4}$$ or 3 is the residue of 15 in modulo 4. However, this can become tedious as the numbers increase in size.

A shorter method is to find the remainder using long division. For example, $$15 \div 4 = 3 R3$$. Which means 15 wraps around 3 times and has a remainder of 3. Thus, we only have to count 3 residues in modulo 3.

2. $$82 \pmod{11}$$

$$82 \div 11 = 7 R5$$. Thus, the remainder 5 means you only have to count 5 residues in modulo 11, so $$82 \equiv 5\pmod{11}$$. This also means that $$11 \times 7 +5 = 82$$.

3. $$-17 \pmod{10}$$

For negative integers, when you perform the division $$-17 \div 10 = -1 R-7$$, the remainder is -7. However, we know that the reside for 10 must be one of the numbers $$1,2,3,4,5,6,7,8,9,0$$. Thus, we must work out the division such that the remainder is positive.

$-17 \div 10 = -2 R3$

Above when we increase the quotient by 1 to 2, it results in a positive remainder. This also means that $$-2 \times 10 + 3 = 17$$.

$$\therefore -17 \equiv 3 \pmod{10}$$

4. $$-73 \pmod{7}$$

$$-73 \div 7 = -10 R-3$$ or $$= -11 R4$$. Since we want the positive remainder.

$-73 \equiv 4 \pmod{7}$

5. $$907,342 \pmod{23}$$

How do we find the remainder of a really big number?

You can first use your calculator to find $$907,342 \div 23 = 39,449.65217$$

What is important is the value before the decimal 39,449

Now to find the remainder $$907,342 - 39,449 \times 23 = 15$$

$$\therefore 907,342 \pmod{23} \equiv 15 \pmod{23}$$