It is a strange beast, this modular arithmetic. The numbers start again atwhen 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 wouldbe 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?
We say thatis 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:
OK, so what is
We know thatso:
According to the above property,
A bit more surprising is perhaps that:
We didn't need to computeat all.
Bob discovered that the two properties are actually not that surprising. We know that there existsand such that:
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:
Canbe written as the sum of two integer squares?
Let's say it can. Then there are integersand such that:
Now, ifis an even number:
Ifis an odd number:
The same is true forThat means is congruent modulo to one of the following options:
But ouris 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.