A Modular Arithmetic Primer

Sean Markan

Here are some of the main definitions, theorems, and techniques involving modular arithmetic. This is geared towards students preparing for math competitions (see here for some relevant contest problems), but others might find it useful as well. I have tried to make this as short as possible, so if you're studying modular arithmetic for the first time you'll want to supplement this article with a real number theory book!

First, note that $p \mid q$ (pronounced "p divides q") is a shorthand for "$p$ is a divisor of $q$". More precisely, if $p$ is a positive integer and $q$ is an integer, then $p \mid q$ means that $q = px$ for some integer $x$.

Suppose that $a$ and $b$ are integers and $m$ is a positive integer. We write $a \equiv b \pmod m$ (pronounced "a is congruent to b mod m") if $m \mid a-b$.

Examples: $43 \equiv 53 \pmod{ 10}$. $-2 \equiv 6 \equiv 14 \equiv 78 \pmod 8$.

You can go back and forth between congruences and equations. For example, if $n \equiv 6 \pmod 9$, then $n = 9j + 6$ for some integer $j$, and vice versa.

In mod 5 (for example), we sometimes say there are 5 distinct "residues", namely 0, 1, 2, 3, and 4. All other integers are congruent to one of these.

Congruences obey certain rules. For example, if $a \equiv b \pmod m$ and $c \equiv d \pmod m$, then $a + c \equiv b + d \pmod m$, $ac \equiv bd \pmod m$, and $a^n \equiv b^n \pmod m$. And if $a \equiv b \pmod {km}$ then $a \equiv b \pmod m$. You should convince yourself these things are true.

A common application of these rules is to find the remainder when some ugly expression is divided by some number. For example, suppose we want to know the remainder when $135^6$ is divided by 13. We can reason as follows:

$$135^6 \equiv 5^6 \equiv 25^3 \equiv (-1)^3 \equiv -1 \equiv 12 \pmod {13}.$$

So the answer is 12. Make sure you understand each step of that argument.

One has to be careful when dividing congruences. For example, just because $ab \equiv ac \pmod m$ does not mean $b \equiv c \pmod m$. (Find a counterexample.) However, $ab \equiv ac \pmod {am}$ does imply $b \equiv c \pmod m$. Also, if $a$ and $m$ are relatively prime, then $ab \equiv ac \pmod m$ implies $b \equiv c \pmod m$.

With the above rules, you should be able to "simplify" (for example) the congruence $4x \equiv 68 \pmod{90}$ to obtain $x \equiv 17 \pmod {45}$. These two congruences are equivalent.

Inverses. If $a$ and $m$ are relatively prime, then there is always an integer $x$ satisfying $ax \equiv 1 \pmod m$ (try to prove that). Such an $x$ is said to be an inverse of $a \pmod m$. It follows that (if $a$ and $m$ are relatively prime) $ax \equiv b \pmod m$ always has a solution for $x$ (and you should know how to find it efficiently, though I won't go into it here). This solution is "unique up to congruence", which means that any two solutions are congruent. If $a$ and $m$ are not relatively prirme, $a$ won't have an inverse mod $m$ and $ax \equiv b$ may or may not be solvable (find examples of both cases).

Probably the most famous and important theorems involving modular arithmetic are the Chinese Remainder Theorem, Fermat's Little Theorem, and Euler's Theorem.

The Chinese Remainder Theorem (CRT) states that for any constants $a$ and $b$ and any relatively prime mods $m$ and $n$, the system of congruences \begin{align} x & \equiv a \pmod{m} \\ x & \equiv b \pmod{n} \end{align} has a unique solution up to congruence $\pmod{mn}$. (That means any two solutions are congruent $\pmod {mn}$.) The same thing works for more than two congruences, provided each mod is relatively prime to each other one. By the way, there is an efficient method for solving these systems of congruences, which I won't go into here. But you should know it.

The CRT can be used when faced with questions like "find the remainder of $47^{54} \pmod{10}$", because one can separately find the remainder mod 2 and mod 5 and then put the results together. (Try it yourself after you read about Fermat's Little Theorem below.) If you are asked about a remainder mod 100 (say), CRT is not quite as useful, because you can only break 100 down into 4 and 25 (breaking those down further would produce numbers that are no longer relatively prime to one another). However, to compute something (call it $n$) mod 25 you can often determine $n$ mod 5 (say it turns out to be $k$), substitute $n=5j+k$, and proceed from there.

Fermat's Little Theorem: If $p$ is prime and $a \not\equiv 0 \pmod p$, then $a^{p-1} \equiv 1 \pmod p$. Example: $14^{161} \equiv 14(14^{16})^{10} \equiv 14 \pmod{17}.$

Euler's Theorem is a generalization of Fermat's Theorem, and says that if $a$ is relatively prime to $m$, then $a^{\phi(m)} \equiv 1 \pmod m$. (By the way, $\phi(n)$ is Euler's "totient" function, defined as the number of positive integers less than $n$ that are relatively prime to it. There is a quick way of computing $\phi(n)$ from the prime factorization of $n$, which you'll want to learn.)

Incidentally, if $p$ is prime, then $p-1$ is the lowest positive exponent to which you can raise $a$ and get 1. This implies the numbers $1, a, a^2, a^3, \dots a^{p-2}$ hit all the residues $\pmod p$ except 0. If $m$ is not prime, it is sometimes, but not always, the case that $\phi(m)$ is the lowest positive exponent of $a$ that gives you 1. (But if there is a lower one, it has to divide $\phi(m)$, which you should prove.)

If you want to get a bit more in depth, you might find these notes by Ben Lynn interesting.

Want to know more about this subject?

You might be interested in my problem-solving classes or tutoring.

© 2015-2016 Sean Markan - sean@markan.net