Modular arithmetic

January 28, 2021

It is a strange beast, this modular arithmetic. The numbers start again at

when a certain value is reached.

If a certain value (called modulus) is

:

We can say that we only consider the remainders upon division by modulus. In case modulus is

:

is the same as

is the same as

is the same as


But why would

be the same as
the same as
the same as

Bob finds it ridiculous. Perhaps it is some kind of a cryptographic joke? Like Alice and Bob?

Congruence

We say that

is congruent to
modulo
if
divides

is congruent to
modulo
because
is congruent to
modulo
because

In other words:

and
are congruent modulo
if they both have the same remainder when dividing by
In the above case, the remainder is

We denote this relation as:

There are some interesting properties. For example:

If

and
then:

OK, so what is

We know that

so:

According to the above property,

A bit more surprising is perhaps that:

We didn't need to compute

at all.

Bob discovered that the two properties are actually not that surprising. We know that there exists

and
such that:

That means:

And:

Is modular arithmetic useful?

Bob wants examples. Can modular arithmetic be used to solve any kind of problems at all?

Well, it can actually help solve many number theoretical problems.

Let's observe the number:

Can

be written as the sum of two integer squares?

Let's say it can. Then there are integers

and
such that:

Now, if

is an even number:

If

is an odd number:

The same is true for

That means
is congruent modulo
to one of the following options:

That's because:

But our

is congruent to
modulo
It suffices to observe the last two digits of
as
divides
That means
cannot be written as the sum of two integer squares.

Also, modular arithmetic is a cornerstone of cryptography. But we are yet to come there.

The Alice and Bob newsletter

Get highlights of Alice and Bob's adventures delivered to your email box.

Made by XLAB with ❤️
Follow us
Twitter Twitter