The Magic Sword: Modular Arithmetic
It is common mathematical knowledge, and as we have seen in our previous posts, equations are fundamental in mathematics. Solving equations is an important job and a lot of elementary problems are related to this field.
Nevertheless, it turns out that in some cases we are interested not in exact equalities between objects, but in their „similarities”. This means that we make things „equal” disregarding certain, not very interesting properties. For instance, in geometry we know what the congruency of triangles means: their locations are different, otherwise they look „like the same”. Moving ahead on this way, we arrive at the algebraic concept of congruency. We will see that this concept provides us with a magic sword with which we can cut off important properties from unimportant ones.
Division is a very sophisticated operation in the set of whole numbers. Here „division” means „division with remainder” as it has been formulated since Euclid, the Greek: given the integers and
then
can be divided by
with remainder uniquely in the form
where are whole numbers satisfying
. The divisibility of
by
is exactly the case when
. We mentioned this Euclidean Division Algorithm in our previous post. Here
is called the quotient and
is the remainder. So, the remainder may take the following values only:
, the number of them is exactly the quotient
. Using this observation we classify the whole numbers in the following way: we put those numbers
in the same class which have the same remainder on division by
. For instance, if
, then we shall have two classes: the class of even numbers, and the class of odd numbers. These classes are called residue classes and they have the following simple property: they form a partition of the set of all integers in the sense that every whole number belongs to exactly one residue class. Sometimes the residue class of the number
is denoted by
. Of course, here we have to agree on the fixed value of
: it is called the modulus, and the fact that
belongs to the same class as
is denoted by
. We read it as „
is congruent to
modulo
„. In everyday language this means that
has the same remainder on division by
as
.
Now we have classes — what can we do with these residue classes? We observe that if we take two numbers then the remainder of their sum is the same as the sum of their remainders: more exactly, as the remainder of the sum of their remainders. This sounds funny: it is easier to understand when we write it down:
and
implies that
The problem is here that not necessarily satisfies the condition
. In fact, we know that
. If
then we can relax, but if
, then we can write
and here . Of course, the remainder of
and that of
is the same on dividing by
, that is, we can write
This is a very nice observation: the class of the sum of the two numbers is the same as the class of the remainders of the two numbers. This suggests that we can „define” a summation of classes as follows: the sum of the classes and
is the class
. Well, well, but what happens if instead of
and
we take another
from the class of
and an
from the class of
— is it true that
will be the same class?
Let’s try this with the two classes modulo : the sum of two even numbers is even, the sum of two odd numbers is even, and the sum of an even number and an odd number is odd. Shortly: even+even=even, odd+odd=even, even+odd=odd+even=odd. The meaning of these equations is that if we replace the word „even” by any even number and the word „odd” by any odd number, {\bf and} we replace
by
then we have a true statement. We can write
,
, etc. And this works, obviously, for subtraction, too, as it is addition of negative numbers:
. The sign
expresses the property that the numbers on the two sides have the same {\it parity}. All other properties of the numbers become uninteresting — we simply identify numbers with the same parity.
That sounds good, right? We just ask quietly, carefully: does it work with multiplication, too? Let’s see: eveneven=even
odd=odd
even=even, odd
odd=odd. We can write
,
,
, etc. How about division? We have a golden rule: it is impossible to divide by
. But what is
in the world of residue classes? It is the class of the
number, the „even” class: all even numbers represent the class
, and all odd numbers represent the class
. So, we can divide by
, only. Hmmm, not much. What if we change the modulus? If
, then we have the three classes
and
. In the world of classes
behaves like
and
behaves like
, further we have
for addition and
for multiplication. It follows that ,
and the reciprocal of
is itself.
What does it mean „modular arithmetic”? It means that we choose a modulus which is a whole number greater than
, and we „reduce” each whole number to the smallest positive number in its residue class modulo
. This means that when making arithmetical calculations, like addition and multiplication we may replace each whole number with any other whole number which is „congruent” to it: which is in the same residue class. Then, obviously, we lose some information, that’s why we have to replace
by
. But it turns out that the information we lose is irrelevant in several problems. Let’s see some applications.
The first observation is related to divisibility by . As everyone knows, an integer is divisible by
if and only if the sum of its digits is divisible by
. More generally, every integer is congruent to the sum of its digits modulo
. Indeed, if we write the integer
in the decimal system in the form
, where
are the digits, that is, integers between
and
, then any nonnegative power of
is congruent to
modulo
, hence we can write
Clearly, this works with , as well. Now how to find out if the number
is a complete square? The basic observation is that complete squares have remainder either
or
on division by
. Indeed, by our modular arithmetic, if
, then
, and if
, then
. On the other hand,
hence it cannot be a complete square. Easy, right? In the above congruence we replaced the given huge number by the sum of its digits, and in addition, each digit is replaced by its smallest positive representative of its residue class.
The next application is the problem from the Final Contest for secondary school students in Botswana: for which positive integer values of is the number
divisible by
? We apply modular arithmetic: we write
hence there is no such .
We finish with another very nice application. Someone tells us that the decimal expression of has exactly
different digits. What is the missing digit? Of course, we want to answer this without using a calculator. Well,
On the other hand, we know that is congruent with the sum of its digits modulo
. Finally, the sum of all digits is
is divisible by
, which implies that
is off by
from a multiple of
. Hence the missing digit is
. Wow!
Now you can see how efficient is our Magic Sword: the modular arithmetic.