digitális matek

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 n and q> 1 then n can be divided by q with remainder uniquely in the form

    \[n=k\cdot q+r,\]

where k,r are whole numbers satisfying 0\leq r<q. The divisibility of n by q is exactly the case when r=0. We mentioned this Euclidean Division Algorithm in our previous post. Here q is called the quotient and r is the remainder. So, the remainder may take the following values only: 0,1,2,\dots,q-1, the number of them is exactly the quotient q. Using this observation we classify the whole numbers in the following way: we put those numbers n in the same class which have the same remainder on division by q. For instance, if q=2, 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 n is denoted by \overline{n}. Of course, here we have to agree on the fixed value of q: it is called the modulus, and the fact that n belongs to the same class as m is denoted by n\equiv m\enskip (mod~q). We read it as „n is congruent to m modulo q„. In everyday language this means that n has the same remainder on division by q as m.

Now we have q 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: n=k\cdot q+r and m=l\cdot q+s implies that

    \[n+m=(k+l)\cdot q+(r+s).\]

The problem is here that r+s not necessarily satisfies the condition
r+s<q. In fact, we know that r+s<2q. If r+s<q then we can relax, but if r+s\geq q, then we can write

    \[n+m=(k+l+1)\cdot q+(r+s-q)\]

and here 0\leq r+s-q<q. Of course, the remainder of r+s and that of r+s-q is the same on dividing by q, 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 \overline{n} and \overline{m} is the class \overline{n+m}. Well, well, but what happens if instead of n and m we take another n' from the class of n and an m' from the class of m — is it true that \overline{n'+m'} will be the same class?

Let’s try this with the two classes modulo 2: 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 \equiv then we have a true statement. We can write 7+19\equiv 206, 6+1000004\equiv 0, etc. And this works, obviously, for subtraction, too, as it is addition of negative numbers: 82-107\equiv 1. The sign \equiv 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: even\cdoteven=even\cdotodd=odd\cdoteven=even, odd\cdotodd=odd. We can write 7\cdot 19\equiv1, 240\cdot (-37)\equiv 2, 802\cdot 44\equiv0, etc. How about division? We have a golden rule: it is impossible to divide by 0. But what is 0 in the world of residue classes? It is the class of the 0 number, the „even” class: all even numbers represent the class \overline{0}, and all odd numbers represent the class \overline{1}. So, we can divide by \overline{1}, only. Hmmm, not much. What if we change the modulus? If q=3, then we have the three classes \overline{0}, \overline{1} and \overline{2}. In the world of classes \overline{0} behaves like 0 and \overline{1} behaves like 1, further we have


for addition and

    \[\overline{2}\cdot \overline{2}=\overline{1}\]

for multiplication. It follows that -\overline{1}=\overline{2}, -\overline{2}=\overline{1} and the reciprocal of \overline{2} is itself.

What does it mean „modular arithmetic”? It means that we choose a modulus q which is a whole number greater than 1, and we „reduce” each whole number to the smallest positive number in its residue class modulo q. 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 \equiv. 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 3. As everyone knows, an integer is divisible by 3 if and only if the sum of its digits is divisible by 3. More generally, every integer is congruent to the sum of its digits modulo 3. Indeed, if we write the integer N in the decimal system in the form abc...de_{10}, where a,b,c,\dots,d,e are the digits, that is, integers between 0 and 9, then any nonnegative power of 10 is congruent to 1 modulo 3, hence we can write

    \[N=a\cdot 10^n+b\cdot 10^{n-1}+\cdot+d\cdot 10+e\equiv a+b+\cdot+d+e\enskip(mod~3).\]

Clearly, this works with 9, as well. Now how to find out if the number 2309557843472 is a complete square? The basic observation is that complete squares have remainder either 0 or 1 on division by 3. Indeed, by our modular arithmetic, if n\equiv 0 \enskip(mod~3), then n^2\equiv 0 \enskip(mod~3), and if n\equiv \pm1\enskip(mod~3), then n^2\equiv 1\enskip(mod~3). On the other hand,

    \[2309557843472\equiv 2+0+0+0+2+2+1+2+1+0+1+1+2\equiv 2\enskip(mod~3),\]

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 n is the number 3^{2 n}+5 divisible by 8? We apply modular arithmetic: we write

    \[3^{2 n}+5=9^n+5\equiv 1^n+5\equiv 6 \enskip(mod~8),\]

hence there is no such n.

We finish with another very nice application. Someone tells us that the decimal expression of 2^{29} has exactly 9 different digits. What is the missing digit? Of course, we want to answer this without using a calculator. Well,

    \[2^{29}=2^{3\cdot 9+2}=2^2\cdot (2^3)^9\equiv 4\cdot (-1)^9\equiv -4\enskip(mod~9).\]

On the other hand, we know that 2^{29} is congruent with the sum of its digits modulo 9. Finally, the sum of all digits is 0+1+2+\dots+9=45 is divisible by 9, which implies that 2^{29} is off by 4 from a multiple of 9. Hence the missing digit is 4. Wow!

Now you can see how efficient is our Magic Sword: the modular arithmetic.