modulo - Part 2

Last time, we have learnt about modulo. Two integers $a$ and $b$ are said to be equal modulo $n$, denoted by $a = b \pmod{n}$, iff $a-b$ is divisible by $n$.

For example, $15 = 3 \pmod{4}$ and $99 = -1 \pmod{10}$.

We have also learnt about modulo properties.

Addition Rule:

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

Addition Rule (special case):

If $a = b \pmod{n}$ then $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}$.

Among them, the Exponentiation Rule is particularly useful.

We are going to look at some examples now. In the first example, we will do it slowly and try to explain each step.

Example: Prove that $2012^{2013} + 1$ is divisible by 7.

Analysing: This problem is obviously a modulo problem
$$2012^{2013} = ~~? ~\pmod{7}$$

First of all, we take 2012 and divide it by 7, we get 287 and the remainder is 3. It means that
$$2012 = 3 \pmod{7}.$$

We now apply the Exponentiation Rule and get
$$2012^{2013} = 3^{2013} \pmod{7}.$$

As you can see, from a gigantic number $2012^{2013}$, by the Exponentiation Rule, we can reduce it to a smaller number $3^{2013}$. However, this number $3^{2013}$ is still gigantic.

We are now investigating the numbers $3^{k}$ one by one and hopefully we may find out some pattern. We have
$$3^0 = 1 \pmod{7},$$ $$3^1 = 3 \pmod{7},$$ $$3^2 = 9 = 2 \pmod{7},$$ by the Multiplication Rule, we have
$$3^3 = 3 \times 2 = 6 \pmod{7},$$
Multiplication Rule again gives us
$$3^4 = 3 \times 6 = 18 = 4 \pmod{7},$$ $$3^5 = 3 \times 4 = 12 = 5 \pmod{7},$$ $$3^6 = 3 \times 5 = 15 = 1 \pmod{7},$$ $$3^7 = 3 \times 1 = 3 \pmod{7},$$ $$3^8 = 3 \times 3 = 9 = 2 \pmod{7},$$ $$3^9 = 3 \times 2 = 6 \pmod{7},$$ $$3^{10} = 3 \times 6 = 18 = 4 \pmod{7},$$ $$3^{11} = 3 \times 4 = 12 = 5 \pmod{7},$$ $$3^{12} = 3 \times 5 = 15 = 1 \pmod{7},$$ $$3^{13} = 3 \times 1 = 3 \pmod{7},$$ $$3^{14} = 3 \times 3 = 9 = 2 \pmod{7},$$ $$3^{15} = 3 \times 2 = 6 \pmod{7},$$
Wait a minute! We've found it. Base on modulo 7, the numbers $3^k$ are equal to 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3, 2, 6,... -  this is a cyclic pattern. So, depending on the exponent $k$, the number $3^k$ will get one of the following values: 1, 3, 2, 6, 4, 5. The cyclic circle length is 6. We have found the pattern:

• if $k = 6n$ then $3^k = 1 \pmod{7}$
• if $k = 6n + 1$ then $3^k = 3 \pmod{7}$
• if $k = 6n + 2$ then $3^k = 2 \pmod{7}$
• if $k = 6n + 3$ then $3^k = 6 \pmod{7}$
• if $k = 6n + 4$ then $3^k = 4 \pmod{7}$
• if $k = 6n + 5$ then $3^k = 5 \pmod{7}$

In our problem, the exponent $k$ is $2013 = 3 \pmod{6}$, so it is of the form $6n + 3$, thus, $3^{2013} = 6 \pmod{7}$. After successfully analyzing the problem, now we will write down the proof.

Proof: We have $2012 = 3 \pmod{7}$, so $2012^{2013} = 3^{2013} \pmod{7}$.

We have
$$3^2 = 9 = 2 \pmod{7},$$ $$3^3 = 6 \pmod{7},$$ $$3^4 = 18 = 4 \pmod{7},$$ $$3^5 = 12 = 5 \pmod{7},$$ $$3^6 = 15 = 1 \pmod{7}.$$ Therefore, for any $n$, we have $3^{6n} = (3^6)^n = 1^n = 1 \pmod{7}$.

We have $2013 = 2010 + 3 = 6n + 3$, thus,
$$3^{2013} = 3^{6n+3} = 3^{6n} \times 3^3 = 1 \times 6 = 6 \pmod{7}.$$

Finally, we have $2012^{2013} = 3^{2013} = 6 \pmod{7}$. Therefore, $2012^{2013} + 1$ is divisible by 7. $\blacksquare$


Reading the proof again, we can see that the key point is when we find out $3^6 = 1 \pmod{7}$. This is definitely a key point because by using the Exponentiation Rule, we derive a very important formula
$$3^{6n} = 1 \pmod{7}.$$

We have made use of a special property of the number 1. We then suddenly realize that the number $-1$ is also special. In modulo 7, the number $-1$ is the number 6. Now going back to the problem, we have
$$3^3 = 6 = -1 \pmod{7},$$
so
$$3^{3n} = (3^3)^n = (-1)^n \pmod{7}.$$


So for any number $k$, to determine $3^k = ~?~ \pmod{7}$, we only need to take $k$ and divide it by 3 to get $k = 3n + r$ where $r = 0, 1, 2$, and then we have

$$3^k = 3^{3n+r} = 3^{3n} \times 3^r = (-1)^n \times 3^r \pmod{7}.$$

In our case, $2013 = 3 \times 671$, so
$$3^{2013} = (-1)^{671} = -1 \pmod{7}.$$
We have found a second proof of the problem!

Second proof: We have $2012 = 3 \pmod{7}$, so $2012^{2013} = 3^{2013} \pmod{7}$.

We have
$$3^3 = 6 = -1 \pmod{7}.$$

So
$$3^{2013} = 3^{3 \times 671} = (3^3)^{671} = (-1)^{671} = -1 \pmod{7}.$$

Therefore, $2012^{2013} + 1$ is divisible by 7. $\blacksquare$



Homework: Prove that $11 + 2011^{2012} + 2012^{2013}$ is divisible by 13.

See you again at "modulo - Part 3"