modulo - Part 1

Today we will look at an important concept in number theory -- the concept of modulo. Two integer numbers $a$ and $b$ are said to be equal modulo $n$ iff they have the same remainder when divided by $n$. Or equivalently, iff $(a-b)$ is divisible by $n$. We will write $a = b \pmod{n}$.

For example, $5 = 9 \pmod{2}$, $-1 = 3 \pmod{2}$, $-2 = -8 \pmod{2}$. Based on modulo 2 then  for any number $a$, either $a=0 \pmod{2}$ when it is an even number, or $a=1 \pmod{2}$ when it is an odd number. 

Here are a few other examples:

$$0 = 3 = 6 = 9 = 12 = -3 = -6 \pmod{3},$$

$$1 = 4 = 7 = -2 = -5 \pmod{3},$$

$$2 = 5 = 8 = -1 = -4 \pmod{3},$$

$$0 = 4 = 8 = -4 \pmod{4},$$

$$1 = 5 = -3 = -7 \pmod{4},$$

$$2 = 6 = -2 = - 6 \pmod{4},$$

$$-2 = -14 \pmod{6}, ~~~7 = -14 \pmod{7}, ~~~5 = -3 \pmod{8}, ~~~16 = -2 \pmod{9}, ...$$

Recall the definition, we define that $a = b \pmod{n}$ when $a-b$ is divisible by $n$ and read "$a$ is equal to $b$ modulo $n$".

Let us look at some of the properties of modulo.

Addition Rule:

If $a = b \pmod{n}$ and $x = y \pmod{n}$ then $a +x = b + y \pmod{n}$.

This is similar to our usual addition rule, that is when $a = b$ and $x=y$ then $a+x = b+y$. Here, we just simply add modulo $n$ to the end of the formula. For example, from $13 = 1 \pmod{4}$ and $2 = 6 \pmod{4}$ we have $15 = 7 \pmod{4}$.

To prove this Addition Rule, we just need to use the definition. Since $a = b \pmod{n}$, $a-b$ is divisible by $n$. Again, since $x = y \pmod{n}$, $x-y$ is divisible by $n$. Sum of two multiples of $n$ is a multiple of $n$, so $(a-b)+(x-y)$ is divisible by $n$. We have $(a-b)+(x-y) = (a+x) - (b+y)$, so because $(a+x) - (b+y)$ is divisible by $n$, by the definition, we have $a +x = b + y \pmod{n}$.  So the Addition Rule is proved. Let us look at other properties.

Addition Rule (special case): 

If $a = b \pmod{n}$ then $a + z = b + z \pmod{n}$.

This special case is derived from the main Addition Rule. We apply $a = b \pmod{n}$ and $z = z \pmod{n}$ and get $a + z = b + z \pmod{n}$.

Subtraction Rule:

If $a = b \pmod{n}$ and $x = y \pmod{n}$ then $a - x = b - y \pmod{n}$.

Subtraction Rule (special case): 

If $a = b \pmod{n}$ then $a - z = b - z \pmod{n}$.

Multiplication Rule:

If $a = b \pmod{n}$ and $x = y \pmod{n}$ then $a x = b y \pmod{n}$.

Multiplication Rule (special case): 

If $a = b \pmod{n}$ then $a z = b z \pmod{n}$.

Exponentiation Rule:

If $a = b \pmod{n}$  then $a^k = b^k \pmod{n}$.

The Exponentiation Rule is derived from the Multiplication Rule. We apply $a = b \pmod{n}$ and $a = b \pmod{n}$ and get $a^2 = b^2 \pmod{n}$ from the Multiplication Rule. Again using the Multiplication Rule for $a^2 = b^2 \pmod{n}$ and $a = b \pmod{n}$, we get $a^3 = b^3 \pmod{n}$.  So by repeating this process, we get $a^k = b^k \pmod{n}$ for all values of $k$.

Homework: Prove the Subtraction Rule and the Multiplication Rule.

We will meet again in "modulo - Part 2" when we talk about some applications of modulo.