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!
$$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!
