Modular Arithmetic

Definition

Modular Arithmetic is a system of arithmetic for the integers, in which two integers $a$ and $b$ are equivalent (or in the same equivalence class) modulo $N$ if they have the same remainder upon division by $N$. In mathematical notation,

$a \equiv b \pmod{N}.$

Here are a few properties of Modular Arithmetic:

A. If $a+b = c$, then $a + b \equiv c \pmod {N}$.

B. If $a \cdot b = c$, then $a\cdot b \equiv c \pmod{N}$.

C. If $a \equiv b \pmod{N}$, then $a+k \equiv (b+k) \pmod {N}$ for any integer $k$.

D. If $a\equiv b$ and $c\equiv d \pmod{N}$, then $a + c \equiv (b + d) \pmod {N}$.

E. If $a \equiv b \pmod{N}$, then $ka \equiv kb \pmod{N}$ for any integer $k$.

F. If $a \equiv b$ and $c \equiv d \pmod{N}$, then $ac \equiv bd \pmod{N}$.

These properties show that addition and multiplication on equivalence classes modulo $N$ are well defined. Are subtraction and division also well defined? We have the property:

G. If $a \equiv b \pmod {N}$, then $-a \equiv -b \pmod{N}$

We can then use the properties of addition to show that subtraction is defined.

What about division? Consider $4 \equiv 8 \pmod{4}$. Note that we cannot simply divide both sides of the equation by 2, since $2 \not \equiv 4 \pmod{4}$. This shows that in general, division is not well defined. As the following property shows, if we add the condition that $k, N$ are coprime, then division becomes well defined:

H. If $\gcd(k,N)=1$ and $ka \equiv kb \pmod{N}$, then $a \equiv b \pmod{N}$.

This property is true because if $k(a-b)$ is a multiple of $N$ and $\gcd(k,N)=1$, then $N$ must divide $a-b$, or equivalently, $a \equiv b \pmod{N}$. We state one final property.

I. If $a$ and $N$ are integers such that $\gcd (a, N)=1$, then there exists an integer $x$ such that $ax \equiv 1 \pmod{N}$. $x$ is called the multiplicative inverse of $a$ modulo $N.$

Worked Examples

1. It is currently 7:00 PM. What time will it be in 1000 hours?

Solution: Time repeats every 24 hours, so we work modulo 24. Since

$1000 \equiv 16 + (24\times 41) \equiv 16 \pmod{24},$

the time in 1000 hours is equivalent to the time in 16 hours. Therefore, it will be 11:00AM in 1000 hours.

2. What is the last digit of $17^{17}$?

Solution: The last digit of a number is equivalent to the number taken modulo 10. Working modulo 10, we have

$\begin{array} { l l l l } 17^{17} & \equiv 7^{17} & \equiv (7^2)^8 \cdot 7 & \pmod{10}\\ & \equiv (49)^8 \cdot 7 & \equiv 9^8 \cdot 7 & \pmod{10} \\ & \equiv (9^2)^4 \cdot 7 & \equiv (81)^4 \cdot 7 & \pmod{10} \\ & \equiv 1^4 \cdot 7 & \equiv 7 & \pmod{10}. \end{array}$