Modular arithmetic

The hard part about this topic is knowing what tiny fraction of it you need for the AMC, and what massively huge proportion of it you can save for grad school (or never).

Let’s get into it. (Not to worry, it won’t take long.)

The basic idea

As you know, integers are either even or odd. And there are just as many even numbers as odd ones.

Next, some numbers are divisible by three and others aren’t. But have you noticed that twice as many numbers aren’t divisible by three as those that are?

Number theorists would say that when it comes to divisibility by three, there aren’t just two categories (divisible or not), Instead there are three categories:

Has no remainder when divided by three
Has a reminder of one when divided by three
Has a reminder of two when divided by three

As we will see shortly, these categories are also called “congruence classes.”

Now, notice two key things:

All integers fall into one of those three categories
All three categories have the same number of integers in them

We say that numbers in the first category are *congruent to $0$ where divisibility by $3$ is concerned."

We more commonly use shorthand, of course: “congruent to $0 (mod 3)$ ”

…or just “ $\equiv 0 (mod 3)$ ”, as in $6 \equiv 0 (mod 3)$ .

Similarly, $7 \equiv 1 (mod 3)$

and $8 \equiv 5 \equiv 2 (mod 3)$ .

By extension, this applies to other moduluses (i.e. other numbers we might divide by).

Definitions

modulus: the number we are dividing by
remainder: the integer “left over” after removing as many integer multiples of the modulus as possible
congruence class: a category of integers including all those with a certain remainder when divided by a certain modulus. For example, $2$ and $5$ are in the same congruence class $(mod 3)$ .

How it gets used

The most important idea here is that addition, subtraction, and multiplication (but not division) work reliably under “mod math.”

Example

Which of the following numbers is equal to $2^{16}$ ?

A) $1024$

B) $2048$

C) $32768$

D) $65536$

E) $131072$

(spoiler)

Brute force works fine here, but consider how reframing this problem under a few different moduluses helps get you to the right answer more easily:

Since $2 \equiv - 1 (mod 3)$ , and since multiplication (and thus exponentiation) works as expected under all moduluses, $2^{16} \equiv (- 1)^{16} \equiv 1 (mod 3)$ . This rules out B, C, and E, all of which are congruent to $2 (mod 3)$ .

Now we know that the answer is either A or D, there are plenty of ways to determine that it must be D. Or, to put it another way, those two answers are so far apart from each other that you have more ways to easily and correctly choose D over A.

Keeping with the theme of using modular arithmetic, one of the many ways to pick D over A would be to observe that $2^{4} = 16 \equiv 1 (mod 5)$ , and that $2^{16} = (2^{4})^{4} \equiv 1^{4} \equiv 1 (mod 5)$ . Therefore the correct answer is one more than a multiple of $5$ , which makes A wrong and D right.

(And now in retrospect we can see that if we had examined this problem under $mod 5$ from the beginning, we could have finished in one step instead of the two we took.)