# Modular arithmetic

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 asis the same as

is the same as

But why would

be the same as the same as the same asBob 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 becauseIn other words:

and are congruent modulo if they both have the same remainder when dividing by In the above case, the remainder isWe 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.