Modular Arithmetic

An introduction to the fundamentals

The Basics

Modular Arithmetic is an incredibly important aspect of practically all asymmetric cryptography. A common way to refer to it is as clock arithmetic - imagine it's eleven o'clock right now. Three hours later it'll be two o'clock, right? Well we do the same thing in modular arithmetic:

11+3=142mod1211 + 3 = 14 \equiv 2 \mod 12

​Essentially we take the sum of 1111 and 33 and then divide by 1212 and keep the remainder. Here, the 1212 is called the modulus. The triple equals \equiv denotes a congruence, and we say 1414 is congruent to 22 mod12\mod 12.

We can think of this another way and say that two numbers aa and bb are congruent modulo mm if their difference aba-b is divisible by mm. For example, 2626 and 22 are congruent modulo 1212 because 262=2426-2=24 which is divisible by 1212.

Modular (Multiplicative) Inverses

In normal maths, every number has an inverse - another number that, when multiplied with them, equals 11. In maths terms, we would say that for every number aa there is another bb where ab=1ab=1. Generally, we can say that b=1ab=\frac{1}{a} as that fits the equation - the inverse of 77, for example, is 17\frac{1}{7}.

In modular arithmetic, there are no fractions. Instead of finding bb such that ab=1ab=1, we instead find bb such that ab1modmab \equiv 1 \mod m. This means that for different values of mm there are different inverses for aa. For example, the inverse of 3mod53 \mod 5 is 22, because 32=61mod53 \cdot 2 = 6 \equiv 1 \mod 5. This inverse is called the modular multiplicative inverse. We can therefore say that 312mod53^{-1} \equiv 2 \mod 5.

Yet not every number aa has an inverse modulo mm - for example, 22 has no inverse modulo 66. Why? This is because gcd(a,m)=1gcd(a,m)=1. Let's prove this in the general case and see why that is.


Assume there is bb such that ab1modma \cdot b \equiv 1 \mod m. This would mean that there also exists cc such that ab=cm+1ab = cm + 1 and therefore abcm=1ab - cm = 1. It follows therefore that both sides must be divisible by gcd(a,m)gcd(a,m), meaning gcd(a,m)=1gcd(a,m)=1.

As a result, if there is an inverse of aa modulo mm, such an inverse can only exist if gcd(a,m)=1gcd(a,m)=1 \square

An Intuitive Approach

If you're struggling to visualise this proof, think back to the previous example of 22 having no inverse modulo 66. Why is this? Well, regardless of how much you multiply 22 with, the sequence will go 0,2,4,0,2,4,...0, 2, 4, 0, 2, 4, ... and loop around because it is a factor of 6.

Actually, the fact that a number it is not coprime with the modulus shows that it can never have an inverse. Again, why? Think about it this way: if they have a common factor, the remainder when one is divided by the other will also have that factor - and therefore not be 11. If we choose 44 rather than 22, we can see this - if there is a common factor (as there is of 22 in this case) there is no value xx for which 4x4x will return 11 modulo 66. Any number you can multiply 44 by will always give a remainder divisible by 22 when divided by 6.

I suggest you spend some time reflecting on this fact, as it is a very important result.


The uses of modular multiplicative inverses are similar to those of regular inverses - as division. Normally, if we divide two numbers, we can treat the number being divided by as multiplying by its inverse.

8÷2=821=812=48 \div 2 = 8 \cdot 2^{-1} = 8 \cdot \frac{1}{2} = 4

​We can use the modular multiplicative inverse the same way - say we want to divide 33 by 22, modulo 77:

3÷232134125mod73 \div 2 \equiv 3 \cdot 2^{-1} \equiv 3 \cdot 4 \equiv 12 \equiv 5 \mod 7 \\

Note that 44 is the inverse of 22 as 241mod72 \cdot 4 \equiv 1 \mod 7.

And just like that we realise that dividing 33 by 22 modulo 77 gives us 55.

Last updated