GMAT Quantitative: Number Theory and Divisibility

Mastering number theory and divisibility is a non-negotiable for a high GMAT quantitative score. While the math involved is often pre-algebraic, the test-makers craft questions that demand sharp pattern recognition, logical reasoning, and systematic problem-solving. Success in this domain shifts the battle from brute-force calculation to elegant, time-saving application of core principles.

Prime Factorization: The Foundational Toolkit

Every positive integer greater than 1 is either prime or can be broken down uniquely into a product of prime numbers—its prime factorization. This is your most powerful weapon. Consider the integer 360. Its prime factorization is $360=2^3\ast 3^2\ast 5^1$. This single representation unlocks answers to a multitude of questions.

From this factorization, you can instantly determine that 360 is divisible by any number whose prime factors are a subset of these (e.g., $2^2\ast 3=12$ works). You can also find the greatest common divisor (GCD) and least common multiple (LCM) efficiently. For two numbers, the GCD is the product of the lowest powers of shared primes, while the LCM is the product of the highest powers of all primes present. For example, for 360 ($2^3\ast 3^2\ast 5$) and 270 ($2^1\ast 3^3\ast 5$), the GCD is $2^1\ast 3^2\ast 5^1=90$, and the LCM is $2^3\ast 3^3\ast 5^1=1080$. In word problems involving repeating cycles or grouping items, LCM tells you when events coincide, while GCD helps determine the size of groups.

Mastering Trailing Zeros and Units Digit Cycles

Two frequently tested pattern concepts involve the ends of numbers: trailing zeros and units digits. The number of trailing zeros in a factorial like $25!$ is determined by the number of factor pairs of 2 and 5 in its prime factorization. Since factors of 2 are always more abundant, you only need to count the factors of 5. The formula is: $$\text{Number of trailing zeros}=\lfloor \frac{n}{5}\rfloor +\lfloor \frac{n}{25}\rfloor +\lfloor \frac{n}{125}\rfloor +...$$ For $25!$, it's $\lfloor \frac{25}{5}\rfloor +\lfloor \frac{25}{25}\rfloor =5+1=6$ trailing zeros.

Units digit patterns rely on cyclicity. For any integer, its units digit repeats in a predictable cycle (often of length 1, 2, or 4). For instance, the units digit of powers of 7 cycle every 4: $7^1=7$, $7^2=49$, $7^3=343$, $7^4=2401$, then repeats (7, 9, 3, 1). To find the units digit of $7^{23}$, find the remainder when the exponent (23) is divided by the cycle length (4). $23/4$ gives a remainder of 3, so the units digit corresponds to the third position in the cycle: 3. This shortcuts massive calculations.

The Modular World of Divisibility and Remainders

GMAT divisibility questions rarely ask for straight division. Instead, they test properties and shortcuts. Know the rules for 2, 3, 4, 5, 6, 8, 9, and 10. For example, a number is divisible by 3 if the sum of its digits is divisible by 3. A number is divisible by 8 if its last three digits form a number divisible by 8.

Remainder arithmetic—often called "modular arithmetic"—is crucial. The key principle is that you can often add, subtract, and multiply remainders (usually taking the remainder again at the end). If you need to find the remainder when $137\ast 29$ is divided by 7, find the remainder of each factor first: $137/7$ has remainder $4$, $29/7$ has remainder $1$. Multiply the remainders: $4\ast 1=4$. Thus, the remainder is 4. This avoids huge calculations. Be careful with addition: the remainder when $(32+19)$ is divided by 6 is the remainder of $(2+1)=3$.

GCD, LCM, and Properties of Special Numbers

Word problems often disguise GCD and LCM concepts. GCD Application: If you are splitting 24 pencils and 36 erasers into identical packs with no leftovers, the maximum number of packs is the GCD of 24 and 36, which is 12. LCM Application: If a red light flashes every 18 seconds and a blue light every 24 seconds, they will flash together at times that are multiples of the LCM of 18 and 24, which is 72 seconds.

You must also recognize properties of perfect squares and perfect cubes. A perfect square's prime factorization has only even exponents. This means that in a perfect square, the exponent for every prime factor is a multiple of 2 (e.g., $2^4\ast 3^2$). A perfect cube's exponents are multiples of 3. This is vital for "what must be true" data sufficiency questions. For instance, if $n$ is a positive integer and $45n$ is a perfect square, what must be true about $n$? Factor: $45n=(3^2\ast 5^1)\ast n$. For this to be a perfect square, all exponents must be even. Thus, $n$ must provide the missing odd exponent for 5, so $n$ must have a factor of 5 at minimum.

Consecutive integer patterns are another testing ground. The product of $k$ consecutive integers is always divisible by $k!$ (k factorial). For example, the product of any three consecutive integers is divisible by $3!=6$ because it contains at least one multiple of 3 and at least one multiple of 2 (in fact, it contains at least one even number and one multiple of 3, guaranteeing divisibility by 6).

Common Pitfalls

1. Assuming Divisibility is Additive: A common trap is thinking that if $x$ is divisible by $a$ and $y$ is divisible by $a$, then $(x+y)$ is divisible by $a$. This is true. However, the reverse is not: if $(x+y)$ is divisible by $a$, you cannot conclude that $x$ and $y$ individually are divisible by $a$. (Example: $5+7=12$ is divisible by 4, but neither 5 nor 7 is.)
2. Misapplying Remainder Rules with Division: You cannot simply divide remainders. The remainder when $(32-14)$ is divided by 6 is the remainder of $(2-2)=0$. However, the remainder when $(32/14)$ is divided by 6 is not $(2/2)=1$. Remainder arithmetic does not generally apply to division or exponentiation directly without more advanced modular techniques.
3. Overlooking the "1" in LCM/GCD: In word problems, a subtle trap involves the number 1. When finding the GCD of two numbers that share no common prime factors (like 7 and 15), the GCD is 1, not 0. Similarly, if a problem asks for the smallest positive integer divisible by several numbers, you are finding the LCM, and 1 is often a tempting but incorrect answer if the numbers are not relatively prime.
4. Confusing "Must Be True" with "Could Be True": In data sufficiency and problem-solving, a critical distinction is what must be true versus what could be true. For example, if $n^2$ is divisible by 36, $n$ must be divisible by 6 (since $n^2$ has factors $2^2\ast 3^2$, so $n$ itself must have at least $2^1\ast 3^1$). However, $n$ could also be divisible by 12, but it is not required.

Summary

• Prime factorization is your central command center for solving most divisibility, GCD, LCM, and perfect square/cube questions.
• Master the trailing zero formula for factorials and the cyclical patterns of units digits to answer complex questions about large numbers without direct calculation.
• Use divisibility shortcuts for speed and understand the basic arithmetic of remainders (addition, subtraction, multiplication) to simplify otherwise impossible computations.
• In word problems, identify whether you need the GCD (for splitting into largest equal groups) or the LCM (for determining when repeating events coincide).
• Recognize the prime factor signatures of perfect squares (all even exponents) and perfect cubes (all exponents multiples of 3) to solve abstract "must be true" constraints.
• Always be vigilant for the subtle logical traps on the GMAT, particularly the difference between what must be true and what could be true based on the given divisibility information.