Factors, Multiples, and Divisibility — Apply divisibility...

SECTION 1

Historical Context & Motivation

The study of divisibility and prime numbers represents one of the oldest branches of mathematics, predating even the formal notion of proof. Ancient civilizations recognized that certain numbers could be split evenly into groups while others resisted such decomposition, and this observation became the seed from which modern number theory grew. For GMAT test-takers, these concepts are far more than historical curiosities: they form the structural backbone of problems involving remainders, least common multiples, greatest common divisors, and integer constraints. Understanding the deep mechanics of factorization allows you to dissect complex word problems with speed and precision, a critical advantage under timed conditions.

~300 BCE

Euclid's Elements

Euclid proved the infinitude of primes and formalized the Euclidean algorithm for computing the greatest common divisor, establishing divisibility as a rigorous mathematical discipline.

~200 BCE

Sieve of Eratosthenes

Eratosthenes devised a systematic method to enumerate all primes up to a given limit by iteratively eliminating multiples, a procedure that remains conceptually foundational in computational number theory.

1801

Gauss's Disquisitiones Arithmeticae

Carl Friedrich Gauss published his landmark treatise, in which the Fundamental Theorem of Arithmetic — asserting unique prime factorization — was rigorously established as a cornerstone of number theory.

1977

RSA Cryptography

Rivest, Shamir, and Adleman leveraged the computational difficulty of factoring large semiprimes into the RSA encryption algorithm, demonstrating that prime factorization has profound practical implications in information security.

The central question that these centuries of inquiry resolve is deceptively simple: given any positive integer, how can we systematically determine its building blocks and relationships to other integers? On the GMAT, this question manifests as problems requiring you to identify factors, compute LCM and GCD, assess divisibility without performing full division, and reason about the structure of integers through their prime decomposition. The tools developed over millennia — divisibility rules, the Fundamental Theorem of Arithmetic, and prime factorization algorithms — are precisely the tools tested on exam day.

SECTION 2

Core Principles & Definitions

Before tackling GMAT-style problems, it is essential to internalize the precise definitions and relationships among factors, multiples, and primes. These concepts are interdependent: understanding one deeply illuminates the others, and a gap in any one area creates vulnerabilities across an entire class of quantitative problems.

Factor (Divisor)

An integer d is a factor of n if there exists an integer k such that n = d × k. Equivalently, n ÷ d leaves remainder 0. Every positive integer n ≥ 1 has at least the factors 1 and n itself.

Multiple

An integer m is a multiple of n if m = n × k for some integer k. The set of multiples of n is infinite: {n, 2n, 3n, …}. On the GMAT, 'Is x a multiple of y?' is logically equivalent to 'Is x divisible by y?'

Prime Number

A positive integer p > 1 whose only positive divisors are 1 and p. The first several primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Note that 2 is the only even prime, a frequently tested fact. The number 1 is neither prime nor composite.

Fundamental Theorem of Arithmetic

Every integer greater than 1 can be expressed as a product of prime numbers in exactly one way, up to the order of the factors. For example, 360 = 2³ × 3² × 5. This unique decomposition is the basis for computing GCD, LCM, and the total number of factors.

Divisibility

The relation 'a divides b' (written a | b) holds if b/a is an integer. Divisibility rules provide shortcuts for testing this relation for small divisors (2 through 12) without performing long division — a critical time-saver on the GMAT.

✦ KEY TAKEAWAY

Think of prime factorization as a number's DNA. Just as a biologist sequences an organism's genome to understand its traits, decomposing an integer into its prime factors reveals every structural property the GMAT might test: its divisors, its relationship to other integers via GCD and LCM, and its behavior under multiplication and division. Two numbers sharing a prime factor are, in a sense, 'genetically related,' and the degree of overlap determines their greatest common divisor.

SECTION 3

Visual Explanation — Factor Trees & Prime Decomposition

A factor tree provides a visual algorithm for decomposing any composite number into its prime constituents. Starting from the target integer at the root, you repeatedly split each composite node into two factors until every leaf is prime. The product of all leaves equals the original number, and collecting like primes yields the canonical prime factorization. The diagram below illustrates this process for 360, showing how the tree terminates at the primes 2, 3, and 5.

The factor tree decomposes 360 by repeatedly splitting composite nodes (purple borders) until only prime leaves (green borders) remain. Collecting like primes yields the canonical form 2³ × 3² × 5.

Regardless of the branching choices you make — for instance, starting with 360 = 4 × 90 instead of 36 × 10 — the Fundamental Theorem of Arithmetic guarantees that the same set of prime leaves will appear. This invariance is precisely what makes prime factorization so powerful as an analytical tool. On the GMAT, once you have the canonical factorization, you can immediately compute the total number of positive divisors, determine divisibility by any candidate, and calculate the GCD or LCM with any other integer.

SECTION 4

Mathematical Framework

The algebraic machinery of prime factorization yields closed-form expressions for counting divisors, computing GCD and LCM, and verifying divisibility. These formulas convert what might otherwise be tedious enumeration into rapid calculation — essential for the GMAT's time-pressured environment.

CANONICAL PRIME FACTORIZATION

n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ

where p₁ < p₂ < … < pₖ are distinct primes and each aᵢ ≥ 1. Every positive integer n > 1 has exactly one such representation.

NUMBER OF POSITIVE DIVISORS

τ(n) = (a₁ + 1)(a₂ + 1) … (aₖ + 1)

Each divisor of n is formed by choosing an exponent for each prime pᵢ from 0 to aᵢ. The total count is the product of (aᵢ + 1) across all prime factors. For 360 = 2³ × 3² × 5¹, τ(360) = 4 × 3 × 2 = 24 divisors.

GCD VIA PRIME FACTORIZATION

GCD(a, b) = p₁^min(α₁,β₁) × p₂^min(α₂,β₂) × … × pₖ^min(αₖ,βₖ)

For each prime appearing in either factorization, take the minimum exponent. If a prime does not appear in one number, its exponent in that number is 0.

LCM VIA PRIME FACTORIZATION

LCM(a, b) = p₁^max(α₁,β₁) × p₂^max(α₂,β₂) × … × pₖ^max(αₖ,βₖ)

For each prime, take the maximum exponent. A critical identity connects GCD and LCM: GCD(a, b) × LCM(a, b) = a × b.

💡 GMAT STRATEGY NOTE

The identity GCD(a, b) × LCM(a, b) = a × b is a powerful shortcut. If a Data Sufficiency question provides LCM and one of the two numbers, you can determine GCD immediately (and vice versa), often making the second statement redundant.

SECTION 5

Divisibility Rules — A Complete Reference

Divisibility rules allow you to determine whether one integer divides another without performing full division. On the GMAT, these rules accelerate both Problem Solving and Data Sufficiency questions, particularly when you need to narrow down the possible values of an unknown integer. The table below presents the rules for divisors 2 through 12, along with examples for each. Memorize these; they are tested frequently and serve as the first line of attack when a problem asks about factors or remainders.

Divisibility rules for common GMAT divisors

Divisor	Rule	Example
2	Last digit is even (0, 2, 4, 6, 8)	4,738 → last digit 8 → divisible
3	Sum of digits is divisible by 3	924 → 9+2+4 = 15 → 15/3 = 5 ✓
4	Last two digits form a number divisible by 4	3,516 → 16/4 = 4 ✓
5	Last digit is 0 or 5	7,230 → last digit 0 ✓
6	Divisible by both 2 AND 3	312 → even, 3+1+2 = 6 ✓
8	Last three digits form a number divisible by 8	5,320 → 320/8 = 40 ✓
9	Sum of digits is divisible by 9	2,718 → 2+7+1+8 = 18 → 18/9 = 2 ✓
11	Alternating sum of digits is divisible by 11	9,163 → 9−1+6−3 = 11 ✓
12	Divisible by both 3 AND 4	1,452 → digits sum 12 (÷3 ✓), last two 52/4 = 13 ✓

The flowchart applies divisibility rules sequentially to 1,260, confirming divisibility by 2, 3, 5, 6, 9, and 10 using only digit inspection — no long division required.

⚠️ RULE OF 7 — THE MISSING SHORTCUT

There is no simple digit-based rule for 7. On the GMAT, if divisibility by 7 is relevant, the problem is typically structured so that you can test it by direct division or by recognizing that the number in question is a known multiple of 7 (e.g., 42, 63, 91, 119, 147). Memorizing multiples of 7 up to 100 is a worthwhile investment.

SECTION 6

Worked Example — GMAT-Style Problem

Consider the following GMAT-style problem: If the integer n is a multiple of both 12 and 18, which of the following must be a factor of n? The answer choices might include values like 8, 24, 36, 48, and 54. Let us apply prime factorization to resolve this efficiently.

Finding the factors guaranteed by LCM constraints

Step 1 — Prime-factorize the given divisorsDecompose 12 and 18 into primes: 12 = 2² × 3 and 18 = 2 × 3². These canonical forms reveal the prime 'requirements' each divisor imposes on n.

12 = 2² × 3, 18 = 2 × 3²

Step 2 — Compute LCM(12, 18)The LCM takes the maximum exponent of each prime: max(2, 1) = 2 for the prime 2, and max(1, 2) = 2 for the prime 3. Therefore, LCM(12, 18) = 2² × 3² = 36. Any integer that is a multiple of both 12 and 18 must be a multiple of 36.

LCM(12, 18) = 36

Step 3 — Identify guaranteed factors of nSince n is a multiple of 36, every factor of 36 is also a factor of n. The factors of 36 = 2² × 3² are: 1, 2, 3, 4, 6, 9, 12, 18, 36. Any value from the answer choices that appears in this list must divide n.

Factors of 36: {1, 2, 3, 4, 6, 9, 12, 18, 36}

Step 4 — Evaluate answer choicesAmong the proposed answers: 8 = 2³ (requires three 2s, but n only guarantees two — fails); 24 = 2³ × 3 (same issue — fails); 36 is in the factor list (passes); 48 = 2⁴ × 3 (fails); 54 = 2 × 3³ (requires three 3s — fails). The answer is 36.

Answer: 36 must be a factor of n

🎯 PATTERN RECOGNITION

Whenever a GMAT problem states that n is a multiple of two or more integers, your first move should be to compute their LCM. The LCM defines the 'minimal blueprint' that n must follow, and any factor of the LCM is guaranteed to divide n. This converts a 'must be true' question into a simple factor-checking exercise.

SECTION 7

GMAT Strategies & Common Pitfalls

Mastery of factorization extends beyond knowing the rules; it requires disciplined application under time pressure and awareness of the traps that the GMAT sets for test-takers who rely on intuition rather than systematic reasoning. The table below contrasts effective strategies with the common errors they prevent.

Strategy vs. Pitfall comparison for GMAT factorization problems

Effective Strategy	Common Pitfall	Why It Matters
Always prime-factorize before comparing factors or multiples	Mentally checking divisibility without decomposition, leading to missed factors	Prime factorization is exhaustive; mental estimation is not. This is especially critical when exponents are ≥ 2.
Use LCM for 'must be true' questions and GCD for 'could be true' constraints	Confusing LCM and GCD, or computing one when the other is needed	LCM represents the minimum multiple; GCD represents the maximum common factor. Swapping them inverts the logic of the problem.
Remember that 1 is not prime and 2 is the only even prime	Treating 1 as prime or assuming all primes are odd	These two facts appear in Data Sufficiency traps where the number of prime factors affects the answer.
Apply the τ(n) formula to count divisors	Listing all divisors by hand and missing pairs	The formula is O(1) once you have the factorization; listing is error-prone for numbers with many divisors.
Check divisibility rules in order of increasing computational cost (2, 5, 3, 9, then 4, 8)	Jumping to trial division for every candidate divisor	Efficient ordering saves 20–30 seconds per problem, compounding across the quantitative section.

🔍 THE DATA SUFFICIENCY LENS

In Data Sufficiency questions involving factors and multiples, the key question is often whether a statement narrows the prime factorization enough to answer definitively. A statement like 'n is divisible by 12' tells you that n contains at least 2² × 3, but n could also contain additional primes. Always ask: does the statement constrain the exponents sufficiently, or does ambiguity remain?

SECTION 8

Connections to Advanced Number Properties

The concepts of factorization and divisibility extend naturally into several advanced topics that appear on higher-difficulty GMAT questions. Understanding these connections transforms isolated techniques into a unified framework for reasoning about integers.

From core factorization to advanced GMAT number theory

Core Concept	Advanced Extension	GMAT Application
Prime Factorization	Perfect Squares & Cubes: A number is a perfect square iff all exponents in its factorization are even; a perfect cube iff all are multiples of 3.	DS questions asking 'Is n a perfect square?' can be resolved by checking exponent parity.
Number of Divisors τ(n)	Odd vs. Even Divisor Count: τ(n) is odd if and only if n is a perfect square, because only perfect squares have a divisor that 'pairs with itself.'	Problems asking 'How many integers from 1 to k have an odd number of factors?' reduce to counting perfect squares.
GCD and LCM	Consecutive Integer Properties: GCD of consecutive integers is always 1. The product of any k consecutive integers is divisible by k!.	Frequently tested in problems involving factorial divisibility and combinatorial arguments.
Divisibility Rules	Remainder Arithmetic (Modular): Divisibility rules are special cases of modular arithmetic. For instance, the digit-sum rule reflects the fact that 10 ≡ 1 (mod 9).	Remainder problems on the GMAT are elegantly solved by working mod the divisor, applying the same digit-based logic.

One particularly powerful connection deserves emphasis: the relationship between trailing zeros and prime factorization. The number of trailing zeros in n! (n factorial) equals the number of times 10 divides n!, which in turn equals the number of (2, 5) pairs in the factorization. Since factors of 2 are always more plentiful than factors of 5 in a factorial, the count reduces to ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …. This is a classic 700-level GMAT question type, and it is entirely a prime factorization problem in disguise.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Explain why a number cannot have more than one prime factorization (ignoring the order of factors). What theorem guarantees this, and what would be the consequence for GCD and LCM computations if this theorem were false?

PROBLEM 2 — BASIC CALCULATION

Find the prime factorization of 2,520 and determine the total number of positive divisors.

PROBLEM 3 — INTERMEDIATE

If GCD(a, b) = 15 and LCM(a, b) = 630, and a < b, find all possible pairs (a, b) of positive integers.

PROBLEM 4 — APPLIED

A company ships products in cases of 12 or cases of 18. A warehouse manager wants to repackage all items into the largest possible uniform groups with no items left over. If the warehouse has 12,600 items, how many items are in each group, and how many groups of each original case size would be needed?

PROBLEM 5 — CRITICAL THINKING

Prove that for any integer n ≥ 1, the product n(n+1)(n+2) is always divisible by 6. Then extend: prove that the product of any four consecutive positive integers is divisible by 24. What general principle governs these results?

SUMMARY

Summary & Key Concepts

This lesson established that every integer greater than 1 admits a unique prime factorization guaranteed by the Fundamental Theorem of Arithmetic. From this decomposition, you can compute the total number of divisors using the formula τ(n) = (a₁+1)(a₂+1)…(aₖ+1), determine the GCD by taking minimum exponents and the LCM by taking maximum exponents, and apply the identity GCD × LCM = a × b. Divisibility rules for divisors 2 through 12 allow rapid screening without computation, and the systematic approach of factoring before reasoning prevents the most common GMAT errors.

On the GMAT, these tools interconnect: 'must be true' factor questions resolve via LCM, trailing zero problems reduce to counting factors of 5 in a factorial, and perfect square identification depends on all prime exponents being even. Master these connections, and approximately one-fifth of the quantitative section becomes significantly more tractable.