### 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 *a *and *b *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

- 3a + 5b = 8
- 3a + b = 2

If I apply mod 3 to these equations:

- 0 + 2b ≡ 2 mod 3, or b ≡ 1 mod 3
- 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.

Have you come across modular arithmetic before? M x

I’m mostly utterly baffled but love the patterns and elegance of it all. Maybe I should try and play with numbers a little more to get to know them. Enjoy your posts.

LikeLike

It’s a really handy technique to master! Thanks 🙂

LikeLike