Modular arithmetic

modular arithmetic GMAT test strategies

A tool to refute integer-valued answer choices.

Skip counting

Even and odd numbers split integers into two residue classes \[ \begin{aligned} \{\ldots, -8, -6, -4, -2, &0, 2, 4, 6, 8, 10,\ldots\} \\ \{\ldots, -7, -5, -3, -1, &1, 3, 5, 7, 9, 11,\ldots\}. \end{aligned} \] Two members of the same residue class are said to be congruent modulo 2 and one writes \[ -5 \equiv 7 \pmod 2 \] or shorter \[ -5 \equiv_{\,2}7 \,. \] 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: \[ \begin{aligned} \{\ldots, -10,-5, &{\color{red}0}, 5, 10, 15, \ldots\} \\ \{\ldots, -9, -4, &{\color{red}1}, 6, 11, 16,\ldots\} \\ \{\ldots, -8, -3, &{\color{red}2}, 7, 12, 17,\ldots\} \\ \{\ldots, -7, -2, &{\color{red}3}, 8, 13, 18,\ldots\} \\ \{\ldots, -6, -1, &{\color{red}4}, 9, 14, 19,\ldots\} \end{aligned} \] Each class is again an arithmetic progression (count by \(5\)).
Let \(\bar{x}\) denote the least non-negative representative of the residue class \(x\) belongs to. It’s the remainder when dividing \(x\) by \(n\). From \(\bar{x}\), you can reach \(x\) by counting (up or down) by \(n\), \[ x = \bar{x} +\underbrace{k\cdot n}_{\text{$n$-steps}}\,. \] What happens when we multiply modulo \(n\)? \[ x\cdot y = (\bar{x} +k\cdot n)\cdot (\bar{y} +l\cdot n) = \bar{x}\cdot \bar{y}+ \underbrace{(\bar{x}l +k\bar{y} +kln)\cdot n}_{\text{$n$-steps}} \] We conclude that the numbers \(xy\) and \(\bar{x}\bar{y}\) are in the same residue class modulo \(n\). Similarily, \(x +y\) and \(\bar{x} +\bar{y}\) are in the same residue class. To summarize: \[ xy \equiv_{\,n} \bar{x}\bar{y}\quad \text{and}\quad x+y \equiv_{\,n} \bar{x}+\bar{y} \] for all integers \(x\) and \(y\).

Application: Test for divisibility

If \(x\) is divisible by \(7\), one can say that \(x \equiv_{\,7} 0\). Since \(1937 = 19\cdot 10\cdot 10 +37\), we have \[1937 \equiv_{\,7} 5\cdot 3 \cdot 3 +2 \equiv_{\,7} 1\cdot 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 \[5x^2 -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 \equiv_{\,2} 1\) and \(-34 \equiv_{\,2} +24 \equiv_{\,2} 0\), the above equation becomes modulo \(2\) the congruence \[x^2 \equiv_{\,2} 0\quad \text{or}\quad \bar{x}^2 \equiv_{\,2} 0\,,\] 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 \equiv_{\,5} 0\), \(-34 \equiv_{\,5} 1\) and \(+24 \equiv_{\,5} 4\), we infer the congruence \[x +4 \equiv_{\,5} 0\,,\] 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 \(5x^2 = 34x -24\).
  2. Since \(x\) is an integer, \(5x^2\) 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 \equiv_{\,14} 0\] 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\cdot 7 \equiv_{\,14} 0\). You could safely divide by \(3\) and get \[2x \equiv_{\,14} 0\,,\] which means \(2x = 0 +k\cdot 14\) or \(x = k\cdot 7\). All multiples of \(7\) solve the above congruence.