Pages

modulo - Part 6


We recall the definition of modulo. Two numbers $a$ and $b$ are said to be equal modulo $n$ if and only if $a-b$ is a multiple of $n$, and we write $a = b \pmod{n}$. For example, $9 = 1 \pmod{8}$ and $14 = -2 \pmod{8}$. 


In our usual arithmetic, we picture our integer numbers lying on the number line and we do addition and multiplication like this $2 + 7 = 9$, $2 \times 7 = 14$, etc...
our number line



Now imagine that somewhere in the universe we have a planet called Modulo8. The aliens living there also have numbers  -4, -3, -2, -1, 0, 1, 2, 3, 4... just like us. These numbers are lying on the number line, but their number line is not a straight line. Instead, on Modulo8 planet, the aliens have a cyclic number line where the numbers -8, 0, 8, 16 lying on top of each others, and numbers -7, 1, 9, 17 occupying the same spot. So the aliens also do normal calculation like us $2 + 7 = 9$, $2 \times 7 = 14$, but the aliens can also write down the answer as $2 + 7 = 1$ and $2 \times 7 = -2$ because for them the numbers $1$ and $9$ are the same and there is no difference between $14$ and $-2$. These aliens are doing calculations in modulo 8!

number line on the Modulo8 planet



Now arithmetic does not depend on whether the number line is curved or straight, we expect that modulo arithmetic is very similar to our normal arithmetic. We have the following rules
  • Addition rule: if $a=b \pmod{n}$ and $c=d \pmod{n}$ then $a+c = b+d \pmod{n}$
  • Multiplication rule:  if $a=b \pmod{n}$ and $c=d \pmod{n}$ then $ac = bd \pmod{n}$
  • Exponentiation rule:  if $a=b \pmod{n}$ then $a^k = b^k \pmod{n}$


Among these rules, the exponentiation rule is especially useful. For example, using the exponentiation rule, we can explain the divisibility rules for 9 and 11 quite simple as follows.



Divisibility by 9

The key point is $10 = 1 \pmod{9}$, and by the exponentiation rule, $10^k = 1^k = 1 \pmod{9}$. So
$$\overline{a_n a_{n-1} \dots a_1 a_0} = 10^n a_n + 10^{n-1}a_{n-1}+ \dots + 10 a_1+ a_0$$ $$= a_n + a_{n-1} + \dots + a_1 + a_0 \pmod{9}$$

By modulo arithmetic, we have shown that
$$\overline{a_n a_{n-1} \dots a_1 a_0} = a_n + a_{n-1} + \dots + a_1 + a_0 \pmod{9}$$
Therefore, to check whether or not a number is divisible by 9, we sum up all its digits, if the sum of the digits is a multiple of 9 then the original number is divisible by 9.

Let's say we want to find out if the number  2457  is divisible by 9 or not, we calculate
$$2457 = 2 + 4 + 5 + 7 = 0 \pmod{9}$$
So the number 2457  is divisible by 9.

How about this number  83699, we have
$$83699 = 8 + 3 + 6 + 9 + 9 = 8 \pmod{9}$$
So the number 83699 is not divisible by 9.



Divisibility by 11

The key point is $10 = -1 \pmod{11}$ and $10^k = (-1)^k = \pm 1 \pmod{11}$. So
$$\overline{a_n a_{n-1} \dots a_1 a_0} =  10^n a_n + 10^{n-1}a_{n-1}+ \dots + 10 a_1+ a_0$$ $$= (-1)^n a_n + (-1)^{n-1}a_{n-1} + \dots + (-1) a_1 + a_0 \pmod{11}$$

To check whether or not a number $\overline{a_n a_{n-1} \dots a_1 a_0}$ is divisible by 11, we calculate $a_0 - a_1 + a_2 - a_3 + \dots $, if this sum is a multiple of 11 then the original number is divisible by 11.

If we want to check whether the number  2457  is divisible by 11 or not, we calculate
$$2457 = - 2 + 4 - 5 + 7 = 4 \pmod{11}$$
So the number 2457  is not divisible by 11.

With  83699 , we have
$$83699 = 8 - 3 + 6 - 9 + 9 = 0 \pmod{11}$$
So the number  83699 is divisible by 11.



Modulo is a very important concept in number theory and algebra. We have learnt about modulo for integer numbers. What we are doing here with integers can also be done with other things as well. One of such things is polynomials. For example, we can have
$$2 t^2 + 3t + 7 = 3t + 5 \pmod{t^2 + 1}$$
$$(t+2)(3t+4) = 3t^2 + 10 t + 8 = 10 t + 5 \pmod{t^2+1}$$
Here we define that $a = b \pmod{n}$ if and only if $a-b = \alpha n$ for some polynomial $\alpha$. 

We can also take modulo based on two or more things at the same time too. For example,
$$2 t^2 + 3t + 7 = 2 \pmod{t^2 + 1, 3}$$
$$(t+2)(3t+4) = 3t^2 + 10 t + 8 = 10 t + 5 = t + 2 \pmod{t^2+1,3}$$
Here we define that $a = b \pmod{n_1, n_2}$ if and only if $a-b = \alpha_1 n_1 + \alpha_2 n_2$. 


That's all for now. This is the last post of the "modulo" series. If you like these posts please share them with your friends. In the next few posts, I am going to write about geometry and then I will come back to number theory to tell stories about "Pythagorean triples", "Wilson's theorem", "Fermat's sum of two squares theorem" and many other cool things!