modulo - Part 3

Today, we are going to look at some more examples about modulo.

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




Proof: We have $2011 = 9 \pmod{13}$. So $2011^{2012} = 9^{2012} \pmod{13}$.

We have
$$9^2 = (-4)^2 = 16 = 3 \pmod{13},$$
$$9^3 = 9 \times 3 = 27 = 1 \pmod{13}.$$

To calculate $9^n$ modulo 13, we take the exponent $n$ and divide it by 3. So if $n = 3 q + r$ (where $r$ = 0, 1, or 2) then
$$9^n = 9^{3q + r} = (9^3)^q \times 9^r = 1^q \times 9^r = 9^r \pmod{13}$$

In this problem, we need to calculate $9^{2012} \pmod{13}$, so we take the exponent 2012 and divide it by 3. We have $2012 = 3 \times 670 + 2$. So
$$9^{2012} = 9^{3 \times 670 + 2} = (9^3)^{670} \times 9^2 = 1^{670} \times 3 = 3 \pmod{13}$$

Similarly, $2012 = 10 \pmod{13}$, so $2012^{2013} = 10^{2013} \pmod{13}$.

We have
$$10^2 = (-3)^2 = 9 \pmod{13},$$
$$10^3 = 10 \times 9 = (-3) \times (-4) = 12 = -1 \pmod{13}.$$

To calculate $10^n$ modulo 13, we take the exponent $n$ and divide it by 3. So if $n = 3 q + r$ (where $r$ = 0, 1, or 2) then
$$10^n = 10^{3q + r} = (10^3)^q \times 10^r = (-1)^q \times 10^r   \pmod{13}$$

In our problem, we need to calculate $10^{2013} \pmod{13}$, so we take the exponent 2013 and divide it by 3. We have $2013 = 3 \times 671$, so
$$10^{2013} = 10^{3 \times 671} = (10^3)^{671} = (-1)^{671} = -1 \pmod{13}.$$

Therefore,
$$11 + 2011^{2012} + 2012^{2013} = 11 + 9^{2012} + 10^{2013} = 11 + 3 + (-1) = 0 \pmod{13}. \blacksquare$$




Let us look at other examples.

Example 2: Find all the natural numbers $n$ such that $2012^n + n^{2012}$ is divisible by 3.

Solution: We have $2012 = 2= -1 \pmod{3}$, so $2012^n = (-1)^n \pmod{3}$. It follows that if $2012^n + n^{2012}$ is divisible by 3 then
$$(-1)^n + n^{2012} = 0 \pmod{3}.$$

We have $n$ = 0, 1, or 2 $\pmod{3}$. In other words, $n$ = $0$, $1$, or $-1\pmod{3}$.

Case 1: If $n = 0 \pmod{3}$ then $(-1)^n + n^{2012} = (-1)^n \pmod{3}$. This does not satisfy our condition.

Case 2: If $n = \pm 1 \pmod{3}$ then $(-1)^n + n^{2012} = (-1)^n + (\pm 1)^{2012}= (-1)^n + 1 \pmod{3}$. To get $(-1)^n + 1 = 0 \pmod{3}$, $n$ must be an odd number.

In summary, in order that $2012^n + n^{2012}$ is divisible by 3,  $n$ must satisfy two conditions: $n \neq 0 \pmod{3}$ and $n = 1 \pmod{2}$.

Since the least common divisor of 3 and 2 is 6, we consider $n \pmod{6}$.

If $n = 0,2,4 \pmod{6}$ then $n = 0 \pmod{2}$ - not satisfy.

If $n = 0,3 \pmod{6}$ then $n =0 \pmod{3}$ - not satisfy.

The only case left is $n = 1,5 \pmod{6}$.

In conclusion, $2012^n + n^{2012}$ is divisible by 3 if and only if $n = \pm 1 \pmod{6}$. $\blacksquare$



Example 3: A perfect square number is a number of the form $n^2$. For instance, 0, 1, 4, 9, 16,...
Find all perfect square numbers in the following number sequence: 7, 77, 777, 7777,...

Solution: The last digit of a perfect square number can only be 0, 1, 4, 5, 6, or 9, therefore, in the given number sequence, there is no perfect squares. $\blacksquare$


We can see that the above solution is quite simple and does not mention about modulo. However, the crucial observation is actually based on modulo. Indeed, when we talk about the last digit of a number, we are actually talking about taking modulo 10 of that number. For any number $n$, $n$ is equal to either 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9 $\pmod{10}$, so $n^2 \pmod{10}$ can only have the following values: $0^2 = 0$, $1^2 = 1$, $2^2 = 4$, $3^2 = 9$, $4^2 = 16 = 6$, $5^2 = 25 = 5$, $6^2 = 36 = 6$, $7^2 = 49 = 9$, $8^2 = 64 = 4$, $9^2 = 81 = 1 \pmod{10}$. So a perfect square number can only be equal to 0, 1, 4, 5, 6, or 9 $\pmod{10}$. On the other hand, all the numbers in the sequence 7, 77, 777, 7777,... are equal $7 \pmod{10}$, so none of them is a perfect square.


As been shown above, to find $n^2 \pmod{10}$, we use the fact that an arbitrary number $n$ is equal to either 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9 $\pmod{10}$. Actually, we can make the argument a bit shorter by observing that an arbitrary number $n$ is equal to either $0$, $\pm 1$, $\pm 2$, $\pm 3$, $\pm 4$, or 5 $\pmod{10}$. So $n^2$ can only be $0^2=0$, $(\pm 1)^2=1$, $(\pm 2)^2=4$, $(\pm 3)^2=9$, $(\pm 4)^2=16=6$, $5^2=25=5 \pmod{10}$. So negative numbers are sometimes quite useful in modulo argument.



Homework: Find all perfect square numbers in the following number sequence: 1, 11, 111, 1111,...


That's all for now. We will meet again in "modulo - Part 4".