Modular arithmetic

A tool to refute integer-valued answer choices.

Skip counting

Even and odd numbers split integers into two residue classes {…,−8,−6,−4,−2,0,2,4,6,8,10,…}{…,−7,−5,−3,−1,1,3,5,7,9,11,…}.

Two members of the same residue class are said to be congruent modulo 2 and one writes −5≡7(mod2)

or shorter −5≡27.

Each residue class is an arithmetic progression (count by 2). In the same manner, one defines residue classes modulo n for any positive integer n. For n=5, one gets five classes: {…,−10,−5,0,5,10,15,…}{…,−9,−4,1,6,11,16,…}{…,−8,−3,2,7,12,17,…}{…,−7,−2,3,8,13,18,…}{…,−6,−1,4,9,14,19,…}

Each class is again an arithmetic progression (count by 5).
Let ˉx denote the least non-negative representative of the residue class x belongs to. It’s the remainder when dividing x by n. From ˉx, you can reach x by counting (up or down) by n, x=ˉx+k⋅n⏟n-steps.

What happens when we multiply modulo n? x⋅y=(ˉx+k⋅n)⋅(ˉy+l⋅n)=ˉx⋅ˉy+(ˉxl+kˉy+kln)⋅n⏟n-steps

We conclude that the numbers xy and ˉxˉy are in the same residue class modulo n. Similarily, x+y and ˉx+ˉy are in the same residue class. To summarize: xy≡nˉxˉyandx+y≡nˉx+ˉy

for all integers x and y.

Application: Test for divisibility

If x is divisible by 7, one can say that x≡70. Since 1937=19⋅10⋅10+37, we have 1937≡75⋅3⋅3+2≡71⋅3+2=5.

We conclude that dividing 1937 by 7 leaves the remainder 5.

Application: Eliminating answer choices

Let’s say you boiled down a question on the GMAT to the equation 5x2−34x+24=0,

and the given answer choices are (A) 2, (B) 3, (C) 4, (D) 5, and (E) 6.
Instead of plugging in all these numbers or solve the quadratic equation, we can test them modulo n to simplify the calculations. Since 5≡21 and −34≡2+24≡20, the above equation becomes modulo 2 the congruence x2≡20orˉx2≡20,

which is obviously wrong for x=3,5, but true for x=2,4,6.
So far, we were able to refute answer choices (B) and (D). Let’s get rid of the square by calculating modulo 5. From 5≡50, −34≡51 and +24≡54, we infer the congruence x+4≡50,

which is false for x=2,3,4,5 but true for x=6. Calculating modulo 5 has instantly revealed the correct answer choice (E) by refuting (A), (B), (C), and (D).

The concept of residue classes just formalizes divisibility questions. The same reasoning can be used without it, in plain English:

1. Read the equation as 5x2=34x−24.
2. Since x is an integer, 5x2 is divisible by 5, so must be 34x−24.
3. 35x and 20 are also divisible by 5, and so must be 35x−20−(34x−24)=x+4.

Modular arithmetic with its residue classes just takes the ingenuity of the argument out of the equation.

A warning

When you solve the equation 6x=0, it’s safe to divide by 6 to conclude x=0. The same reasoning applied to the congruence 6x≡140

would miss the solution x=7 (among many others). The problem is that 6 and 14 have a (non-trivial) common factor 2, and 2⋅7≡140. You could safely divide by 3 and get 2x≡140,

which means 2x=0+k⋅14 or x=k⋅7. All multiples of 7 solve the above congruence.