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.

Clock face numbered 1--24

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

 

Advertisements

2 comments

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

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s