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=14≡2mod  1211 + 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
mod  12\mod 12
.
We can think of this another way and say that two numbers
aa
and
bb
are congruent modulo
mm
if their difference
a−ba-b
is divisible by
mm
. For example,
2626
and
22
are congruent modulo
1212
because
26−2=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
ab≡1mod  mab \equiv 1 \mod m
. This means that for different values of
mm
there are different inverses for
aa
. For example, the inverse of
3mod  53 \mod 5
is
22
, because
3⋅2=6≡1mod  53 \cdot 2 = 6 \equiv 1 \mod 5
. This inverse is called the modular multiplicative inverse. We can therefore say that
3−1≡2mod  53^{-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.

Proof

Assume there is
bb
such that
a⋅b≡1mod  ma \cdot b \equiv 1 \mod m
. This would mean that there also exists
cc
such that
ab=cm+1ab = cm + 1
and therefore
ab−cm=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.

Uses

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=8⋅2−1=8⋅12=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÷2≡3⋅2−1≡3⋅4≡12≡5mod  73 \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
2⋅4≡1mod  72 \cdot 4 \equiv 1 \mod 7
.
And just like that we realise that dividing
33
by
22
modulo
77
gives us
55
.