Modular Arithmetic
An introduction to the fundamentals
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:
Essentially we take the sum of
and
and then divide by
and keep the remainder. Here, the
is called the modulus. The triple equals
denotes a congruence, and we say
is congruent to
.
We can think of this another way and say that two numbers
and
are congruent modulo
if their difference
is divisible by
. For example,
and
are congruent modulo
because
which is divisible by
.
In normal maths, every number has an inverse - another number that, when multiplied with them, equals
. In maths terms, we would say that for every number
there is another
where
. Generally, we can say that
as that fits the equation - the inverse of
, for example, is
.
In modular arithmetic, there are no fractions. Instead of finding
such that
, we instead find
such that
. This means that for different values of
there are different inverses for
. For example, the inverse of
is
, because
. This inverse is called the modular multiplicative inverse. We can therefore say that
.
Yet not every number
has an inverse modulo
- for example,
has no inverse modulo
. Why? This is because
. Let's prove this in the general case and see why that is.
Assume there is
such that
. This would mean that there also exists
such that
and therefore
. It follows therefore that both sides must be divisible by
, meaning
.
As a result, if there is an inverse of
modulo
, such an inverse can only exist if
If you're struggling to visualise this proof, think back to the previous example of
having no inverse modulo
. Why is this? Well, regardless of how much you multiply
with, the sequence will go
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
. If we choose
rather than
, we can see this - if there is a common factor (as there is of
in this case) there is no value
for which
will return
modulo
. Any number you can multiply
by will always give a remainder divisible by
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.
We can use the modular multiplicative inverse the same way - say we want to divide
by
, modulo
:
Note that
is the inverse of
as
.
And just like that we realise that dividing
by
modulo
gives us
.