# Modular Arithmetic, What’s the Point?

### What is Modular Arithmetic?

Modular arithmetic, also known informally as ‘clock arithmetic’, is when numbers ‘wrap around’ upon reaching a fixed quantity – the modulus.

To illustrate this, consider a 12 hour clock divided into 12 hour periods.

When it is “13 o’clock” we say it is 1 o’ clock again, and “14 o’ clock” becomes 2 o’clock, etc. What we are saying essentially is that “13 = 1 + a multiple of 12” or alternatively “the remainder when you divide 13 by 12 is one”. To write this mathematically, we say 13 ≡ 1 mod 12 (13 is congruent to 1 modulo 12).

More formally, for a positive integer n, two integers and are said to be congruent modulo n:

if a – b is an integer multiple of n.

### Why is it useful?

Modular arithmetic is extremely useful in number theory; it can be used to find out information about the solutions of a specific equations, such as Diophantine equations.

For example, let us take the equations

1. 3a + 5b = 8
2. 3a + b = 2

If I apply mod 3 to these equations:

1. 0 + 2b ≡ 2 mod 3, or b ≡ 1 mod 3
2. 0 + b ≡ 2 mod 3, or b ≡ 2 mod 3

This is a contradiction, as there is no integer b that that can be 1 mod 3 AND 2 mod 3, hence there is no integer b that satisfies these equations.

Modular arithmetic is used in the video below as a tool to prove something about an equation:

Additionally, in cryptography, modular arithmetic underpins public key systems such as RSA.

The basic principle of RSA is the fact that it is practical to find three very large positive integers e, d and n such that for all m:

However, even if you know e, n or even m it is extremely difficult to find d. As d is essential for decryption, this ensures that the informations remains protected. Click here for more information on RSA.

Sources: 1 | 2 | 3

Have you come across modular arithmetic before? M x