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