### 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=evenodd=oddeven=even, oddodd=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.