Textbook

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.)

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(mod3)$”

…or just “$≡0(mod3)$”, as in $6≡0(mod3)$.

Similarly, $7≡1(mod3)$

and $8≡5≡2(mod3)$.

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

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

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≡−1(mod3)$, and since multiplication (and thus exponentiation) works as expected under all moduluses, $2_{16}≡(−1)_{16}≡1(mod3)$. This rules out B, C, and E, all of which are congruent to $2(mod3)$.

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≡1(mod5)$, and that $2_{16}=(2_{4})_{4}≡1_{4}≡1(mod5)$. 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 $mod5$ from the beginning, we could have finished in one step instead of the two we took.)

Sign up for free to take 14 quiz questions on this topic

All rights reserved ©2016 - 2024 Achievable, Inc.