Modular Arithmetic - An Introduction

Modular Arithmetic is an extremely useful way of thinking about numbers. It can be used to calculate the last three digits of $2011^{2011}$ by hand. The day of the week, the time of the day, and the flipping of a light switch are all based upon modular arithmetic. The day of the week is in $\mod 7$ (cycles in a period of $7$), the time of the day is in $\mod 24$, and a light switch is either on or off; $\mod 2$.

$\textbf{Definitions}$

Two integers are congruent modulo $n$ if their difference is a multiple of $n$. We write this as $a \equiv b \pmod{n}$ For example, $36 \equiv 71 \pmod{7}$, because $71 - 36 = 35$, and $\dfrac{35}{7} = 5$. We can alternatively write this as $a-b = qn$, for an integer $q$, or $a = b + qn$ (by adding $b$ to both sides). Notice that for any integers $x$ and $y$, if $x \equiv y \pmod{n}$, $x$ and $y$ leave the same remainder when divided by $n$. This is sometimes used as another definition for modular arithmetic. Since modular arithmetic is only defined for integers, let all variables be integers unless otherwise specified.

$\textbf{Addition}$

$\textbf{Theorem 1:}$ If $a \equiv b \pmod{n}$, then $a+c \equiv b+c \pmod{n}$.

If $a \equiv b \pmod{n}$, we know that $a-b = qn$ for some integer $q$. This means $(a+c) - (b+c) = a-b = qn$, so $a+c \equiv b+c \pmod{n}$. $\blacksquare$

If we know that $123$ leaves a remainder of $2$ when divided by $11$, and want the remainder when $127$ is divided by $11$, we can simply use Theorem 1: $123 \equiv 2 \pmod{11} \implies 123 + 4 \equiv 2 + 4 \pmod{11}$, so $127 \equiv 6 \pmod{11}$. A similar proof can be used to prove a stronger theorem:

$\textbf{Theorem 2:}$ If $a \equiv b \pmod{n}$, and $c \equiv d \pmod{n}$, then $a+c \equiv b+d \pmod{n}$.

We know that $a-b = qn$ for some integer $q$ and $c-d = rn$ for some integer $r$. Adding the equations gives $(a+c) - (b+d) = qn + rn = (q+r)n$. This means that the difference of $a+c$ and $b+d$ is a multiple of $n$, so $a+c \equiv b+d \pmod{n}$. $\blacksquare$

Theorem 2 can be generalized even further:

$\textbf{Theorem 3:}$ If $a_1 \equiv b_1 \pmod{n}$, $a_2 \equiv b_2 \pmod{n}$, $\cdots , \ a_k \equiv b_k \pmod{n}$ then $a_1 + a_2 + \cdots + a_k \equiv b_1 + b_2 + \cdots + b_k \pmod{n}$.

By the definition of modulos, we get $a_1 - b_1 = q_1 n, \ a_2 - b_2 = q_2 n, \cdots , \ a_k - b_k = q_k n$. Adding these, we get $(a_1 + a_2 + \cdots + a_k) - (b_1 + b_2 + \cdots + b_k) = (q_1 + q_2 + \cdots + q_k)n$,so $a_1 + a_2 + \cdots + a_k \equiv b_1 + b_2 + \cdots + b_k \pmod{n}$. $\blacksquare$

Theorem 3 can be used to solve the following problem:

$\textbf{Problem 1}$ Find the remainder when $123 + 234+ 32+ 56+ 22 + 12 + 78$ is divided by $3$

We know that $123 \equiv 0 \pmod{3}$, $234 \equiv 0 \pmod{3}$, $32 \equiv 2 \pmod{3}$, $56 \equiv 2 \pmod{3}$, $22 \equiv 1 \pmod{3}$, $12 \equiv 0 \pmod{3}$, and $78 \equiv 0 \pmod{3}$. From Theorem 3, $123 + 234+ 32+ 56+ 22 + 12 + 78 \equiv 0+0+2+2+1+0+0 \equiv 5 \pmod{3}$. $5$ has a remainder of $2$ when divided by $3$, so $123 + 234+ 32+ 56+ 22 + 12 + 78$ does too, and the answer is $\boxed{2}$.

$\textbf{Subtraction}$

The same theorems hold for subtraction as well:

$\textbf{Theorem 4:}$ If $a \equiv b \pmod{n}$, then $a-c \equiv b-c \pmod{n}$.

If $a \equiv b \pmod{n}$, we know that $a-b = qn$ for some integer $q$. This means $(a-c) - (b-c) = a-b = qn$, so $a-c \equiv b-c \pmod{n}$. $\blacksquare$

$\textbf{Theorem 5:}$ If $a \equiv b \pmod{n}$, and $c \equiv d \pmod{n}$, then $a-c \equiv b-d \pmod{n}$.

We know that $a-b = qn$ for some integer $q$ and $c-d = rn$ for some integer $r$. Subtracting the equations gives $(a-c) - (b-d) = qn - rn = (q-r)n$. This means that the difference of $a-c$ and $b-d$ is a multiple of $n$, so $a-c \equiv b-d \pmod{n}$. $\blacksquare$

$\textbf{Multiplication}$

Similar theorems hold for muliplication as well, but the proofs are different.

$\textbf{Theorem 6:}$ If $a \equiv b \pmod{n}$, then $ac \equiv bc \pmod{n}$.

If $a \equiv b \pmod{n}$, we know that $a-b = qn$ for some integer $q$. This means $ac-bc = qcn$, so $ac \equiv bc \pmod{n}$. $\blacksquare$

There is also another proof of this:

We know that $\underbrace{a \equiv b \pmod{n}, \ a \equiv b \pmod{n}, \cdots , \ a \equiv b \pmod{n}}_{\text{c statements}}$ From Theorem 3, we get $\underbrace{a+a+a+a+\cdots + a}_{\text{c "a"s}} \equiv \underbrace{b+b+b+b+\cdots + b}_{\text{c "b"s}}$ or $ac \equiv bc \pmod{n}$. $\blacksquare$

$\textbf{Theorem 7:}$ If $a \equiv b \pmod{n}$, and $c \equiv d \pmod{n}$, then $ac \equiv bd \pmod{n}$.

We repeatedly use Theorem 6: Since $a \equiv b$, $ac \equiv bc$, and since $c \equiv d$, $bc \equiv bd$. Therefore, $ac \equiv bc \equiv bd$, or $ac \equiv bd \pmod{n}$. $\blacksquare$

$\textbf{Theorem 8:}$ If $a_1 \equiv b_1 \pmod{n}$, $a_2 \equiv b_2 \pmod{n}$, $\cdots , \ a_k \equiv b_k \pmod{n}$ then $a_1 a_2 \cdots a_k \equiv b_1 b_2 \cdots b_k \pmod{n}$.

We repeatedly use Theorem 7: Because $a_1 \equiv b_1 \pmod{n}$, $a_2 \equiv b_2 \pmod{n}$, we get $a_1a_2 \equiv b_1b_2 \pmod{n}$ We also know $a_3 \equiv b_3 \pmod{n}$, so $a_1a_2a_3 \equiv b_1b_2b_3 \pmod{n}$ Also, $a_4 \equiv b_4 \pmod{n}$, so $a_1a_2a_3a_4 \equiv b_1b_2b_3b_4 \pmod{n}$ Continuing to do this will give $a_1 a_2 \cdots a_k \equiv b_1 b_2 \cdots b_k \pmod{n}$ $\blacksquare$

$\textbf{Problem 2:}$ Find the remainder when $124 \cdot 134 \cdot 23 \cdot 49 \cdot 235 \cdot 13$ is divided by $3$.

In Problem 1, manually adding the numbers up wouldn't take that much time, though the modular arithmetic solution is faster. However, in Problem 2, multiplying the numbers would be very tedious. Instead, we use Theorem 8: We know that $124 \equiv 1$, $134 \equiv 2$, $23 \equiv 2$, $49 \equiv 1$, $235 \equiv 1$, and $13 \equiv 1$. Therefore, from Theorem 8, $124 \cdot 134 \cdot 23 \cdot 49 \cdot 235 \cdot 13 \equiv 1 \cdot 2 \cdot 2 \cdot 1 \cdot 1 \cdot 1 \equiv 4 \equiv 1 \pmod{3}$ so the product leaves a remainder of $\boxed{1}$ when divided by $3$.

$\textbf{Exponentiation}$ Note that a corollary of Theorem 8, when $a_1 = a_2 = \cdots = a_k$ and $a_1 = a_2 = \cdots = a_k$, is that

$\textbf{Theorem 9:}$ If $a \equiv b \pmod{n}$, then $a^k \equiv b^k \pmod{n}$. One might expect the following theorem to hold:

If $x \equiv y \pmod{n}$, then $a^x \equiv a^y \pmod{n}$.

However, taking $n = 3$, $a =2$, $x = 2$, and $y = 5$, we get $2 \equiv 5 \pmod{3}$, but $2^2 \equiv 1 \not\equiv 2 \equiv 2^5 \pmod{3}$.

$\textbf{Problem 3:}$ What is the remainder when $23^{12345}$ is divided by $22$?

From Theorem 9, since $23 \equiv 1 \pmod{22}$, $23^{12345} \equiv 1^{12345} \equiv 1 \pmod{22}$, so $23^{12345}$ leaves a remainder of $\boxed{1}$ when divded by $22$.

$\textbf{Problem 4:}$ Find the last three digits of $2^{40}$

$\begin{aligned}2^{40} &=& \left(2^{10}\right)^4 \\ &=& 1024^4 \\ &\equiv& 24^4 \\ &\equiv& 576^2 \pmod{1000}\end{aligned}$ We can write $576^2$ as $\begin{aligned}(500+76)(500+76) &=& 250000+2*500*76+76*76 \\ &=& 250000 + 76000 + 5776 \\ &\equiv& 0 + 5776 \\ &\equiv& 776 \pmod{1000}\end{aligned}$. Since $2^{40}$ leaves a remainder of $776$ when divided by $1000$, its last three digits are $\boxed{776}$.

And finally, we get to the problem mentioned in the introduction:

$\textbf{Problem 5:}$ Find the last three digits of $2011^{2011}$

We know that $2011 \equiv 11 \pmod{1000}$, so $2011^{2011} \equiv 11^{2011} \pmod{1000}$. We can write $11^{2011}$ as $(10+1)^{2011}$ and use the Binomial Theorem to expand it. We get $\begin{aligned} 11^{2011} &=& (10+1)^{2011} \\ &=& \dbinom{2011}{0} 10^{2011}1^{0}+\dbinom{2011}{1} 10^{2010}1^{1} + \cdots + \dbinom{2011}{2010} 10^11^{2010} + \dbinom{2011}{2011} 1^{2011} \end{aligned}$ However, all powers of 10 above $10^2$ are divisible by $1000$, so are $0 \pmod{1000}$. Therefore, we can reduce them to $0$. All terms at the beginning are nullified, and we are left with $\dbinom{2011}{2009} 10^2 1^{2009} + \dbinom{2011}{2010} 10^11^{2010} + \dbinom{2011}{2011} 1^{2011} = 100 \cdot \dbinom{2011}{2} + 10 \cdot \dbinom{2011}{1} + 1 \cdot \dbinom{2011}{0}$ because of the property that $\dbinom{2011}{2009} = \dbinom{2011}{2}$, $\dbinom{2011}{2010} = \dbinom{2011}{1}$, and $\dbinom{2011}{2011} = \dbinom{2011}{0}$. We can write this as $\begin{aligned}100 \cdot \dfrac{2011 \cdot 2010}{2} + 10 \cdot 2011 + 1 &\equiv& 100 \cdot \dfrac{11 \cdot 10}{2}+ 10 \cdot 11 + 1 \\ &=& 5500 + 110 + 1 \\ &\equiv& \boxed{611} \pmod{1000}\end{aligned}$ $\blacksquare$