Relvora Prep

GMAT Quant lesson · Factors & multiples

GMAT factors, multiples and divisibility: GCF, LCM and counting

Divisibility for GMAT Quant: counting factors and multiples, the LCM for events that line up, the GCF for equal groups, and what must divide a product.

The core idea

Divisibility questions are about prime building blocks: a number divides another when all its prime factors fit inside. Use the greatest common factor (GCF) when you split things into equal groups, the least common multiple (LCM) when repeating events happen together again, and prime factorizations to decide what must divide a number.

Core ideas

Words used here

  • Factor (or divisor): a whole number that divides another with nothing left over. The factors of 12 are 1, 2, 3, 4, 6 and 12.
  • Multiple: a number times a whole number. The multiples of 5 are 5, 10, 15, 20, …
  • "a divides b" or "b is divisible by a": b ÷ a is a whole number.
  • Prime: a whole number above 1 whose only factors are 1 and itself: 2, 3, 5, 7, 11, 13, …
  • Exponent: the small raised number. 2³ means 2 × 2 × 2 = 8, and 3² means 3 × 3 = 9.
  • Prime factorization: a number written as a product of primes, such as 72 = 2³ × 3².
  • Greatest common factor (GCF): the largest number that divides all the given numbers. GCF(12, 18) = 6.
  • Least common multiple (LCM): the smallest positive number that all the given numbers divide. LCM(4, 6) = 12.
  • Factorial: k! = k × (k − 1) × … × 2 × 1. For example, 3! = 6 and 4! = 24.
  • Consecutive integers: whole numbers in a row, such as 7, 8, 9.

Find the prime factorization by dividing by the smallest prime that works, again and again, until you reach 1:

Number Divide by Result
72 2 36
36 2 18
18 2 9
9 3 3
3 3 1

The primes used are 2, 2, 2, 3 and 3, so 72 = 2 × 2 × 2 × 3 × 3 = 2³ × 3².

722362182933
Split off the smallest prime each time: 72 = 2 × 2 × 2 × 3 × 3 = 2³ × 3²
  • Factors come in pairs that multiply to n, such as 2 × 36 = 72. The pairs meet near √n (the square root of n). A perfect square has one factor paired with itself (6 × 6 = 36).
  • GCF: take only the primes that appear in every number, each with its smaller exponent. LCM: take every prime that appears, each with its larger exponent. For 12 = 2² × 3 and 18 = 2 × 3²: GCF = 2 × 3 = 6 and LCM = 2² × 3² = 4 × 9 = 36.
  • For two numbers, GCF × LCM = a × b. Check: 6 × 36 = 216 and 12 × 18 = 216.
  • Multiples of k from a to b: (last multiple − first multiple) ÷ k + 1.
  • The product of k consecutive integers is divisible by k!

Try it. Find the GCF and the LCM of 20 and 30.

Show the answer
  1. 20 = 2² × 5 and 30 = 2 × 3 × 5.
  2. GCF: the primes in both are 2 and 5, with smaller exponents 2¹ and 5¹. GCF = 2 × 5 = 10.
  3. LCM: every prime with its larger exponent: 2² × 3 × 5 = 4 × 3 × 5 = 60.
  4. Check: 10 × 60 = 600 and 20 × 30 = 600. ✓

Counting the factors of n

Method 1: list factor pairs from 1 upward, until the pairs meet near √n (the square root of n).

Method 2: write n as a product of primes, add 1 to each exponent, and multiply. Why it works: for 72 = 2³ × 3², every factor is 2ᵃ × 3ᵇ, where a can be 0, 1, 2 or 3 (4 choices) and b can be 0, 1 or 2 (3 choices). The + 1 counts the choice "exponent 0". So there are 4 × 3 = 12 factors.

How to spot it: "how many positive factors (divisors) does n have?"

Example. How many positive factors does 72 have?

  1. Pairs: 1 × 72, 2 × 36, 3 × 24, 4 × 18, 6 × 12, 8 × 9.
  2. Stop after 8 × 9: √72 is about 8.5, so the next factor, 9, is already in a pair.
  3. 6 pairs make 12 factors.
  4. Check with the formula: 72 = 2³ × 3², and (3 + 1) × (2 + 1) = 4 × 3 = 12. ✓

Trap: leaving out 1 and 72.

Edge cases.

  • Perfect squares have an odd number of factors. For 36 the middle pair is 6 × 6, and 6 is counted once: 36 = 2² × 3² has 3 × 3 = 9 factors.
  • 1 has one factor; a prime has exactly two.
  • Even factors only: force at least one 2. For 72 = 2³ × 3², the 2 can have exponent 1, 2 or 3: 3 × 3 = 9 even factors.

In the grid, each square is one factor 2ᵃ × 3ᵇ of 72 (column a = 0 to 3, row b = 0 to 2); the shaded squares are the even ones.

12 factors of 72, 9 of them even
4 choices for the exponent of 2 times 3 for the exponent of 3 gives 12 factors; forcing a 2 leaves 3 × 3 = 9

GMAT-level example. How many positive integers less than 50 have exactly 3 positive factors?

  1. With exponents a, b, …, the factor count is (a + 1)(b + 1)…. To get 3, which is prime, there must be one prime with exponent 2.
  2. So the numbers are squares of primes: 2² = 4, 3² = 9, 5² = 25, 7² = 49. (11² = 121 is too big.)
  3. Answer: 4.
  4. Check 25: its factors are 1, 5 and 25 ✓.

Check yourself. How many of the factors of 72 are even?

Check your answer

9: the exponent of 2 is 1, 2 or 3 (3 choices) and the exponent of 3 is 0, 1 or 2 (3 choices). (The other 3 factors, 1, 3 and 9, are odd.)

Counting multiples in a range

Find the first and the last multiple inside the range. Then count: (last − first) ÷ k + 1. The + 1 is there because the first multiple counts too.

Why it works. Multiples of k are evenly spaced, k apart. (last − first) ÷ k counts the gaps between them, and there is always one more multiple than gaps.

How to spot it: "how many multiples of k are there between a and b (inclusive)?"

Example. How many multiples of 7 are there from 50 to 200?

  1. First multiple: 7 × 7 = 49 is below 50, so the first is 7 × 8 = 56.
  2. Last multiple: 7 × 29 = 203 is above 200, so the last is 7 × 28 = 196.
  3. (196 − 56) ÷ 7 + 1 = 140 ÷ 7 + 1 = 20 + 1 = 21.
  4. Check: the multiples are 7 × 8 up to 7 × 28, and 28 − 8 + 1 = 21. ✓

Divisible by both, or by either. A number divisible by both 4 and 6 is divisible by their least common multiple (LCM), 12, not by 4 × 6 = 24 (24 skips 12, 36, 60, …). From 1 to 60 there are 15 multiples of 4, 10 multiples of 6 and 5 multiples of 12. So "divisible by 4 or 6" is 15 + 10 − 5 = 20, because the multiples of 12 were counted twice.

Trap: dropping the + 1 gives 20 and loses one of the end multiples.

Edge cases.

  • "Between" usually leaves out the ends. Check whether the ends themselves are multiples.
  • 0 is a multiple of every number. From −40 to 40, the multiples of 9 are −36, −27, …, 0, …, 36.
  • "Neither" = total − "either".

GMAT-level example. How many integers from 1 to 200 are divisible by neither 4 nor 6?

  1. Multiples of 4: 200 ÷ 4 = 50. Multiples of 6: 200 ÷ 6 = 33.3, so 33.
  2. Multiples of both are multiples of the LCM, 12: 200 ÷ 12 = 16.7, so 16.
  3. Divisible by 4 or 6: 50 + 33 − 16 = 67.
  4. Neither: 200 − 67 = 133.
1 to 200Multiples of 4Multiples of 6341617neither133
The 16 multiples of 12 sit in both circles: 34 + 16 + 17 = 67 in either, and 133 in neither

Check yourself. How many multiples of 9 are there from −40 to 40?

Check your answer

First −36, last 36: (36 − (−36)) ÷ 9 + 1 = 8 + 1 = 9.

Events that coincide: the LCM

Repeating events that start together happen together again at the common multiples of their cycle lengths. The first time is the least common multiple (LCM): the smallest number that every cycle length divides.

Why it works. A moment when both buses leave must be a multiple of 12 and a multiple of 18. The first such moment is the smallest common multiple. Taking each prime with its larger exponent is exactly what makes both 12 and 18 divide it, and nothing more.

How to spot it: "the next time both happen together", "every a minutes and every b minutes".

Example. Two buses leave a station together at 7:00 a.m. One leaves every 12 minutes, the other every 18 minutes. When do they next leave together?

  1. Prime factors: 12 = 2² × 3 and 18 = 2 × 3².
  2. LCM: every prime with its larger exponent: 2² × 3² = 4 × 9 = 36 minutes.
  3. 7:00 + 36 minutes = 7:36 a.m. (Check: 12, 24, 36 and 18, 36 first meet at 36.)

Same leftover every time. If a total leaves the same remainder r with every group size, it is r more than a common multiple: LCM + r, 2 × LCM + r, and so on. For example, a number that leaves 1 when divided by 4 and when divided by 6 is 12 + 1 = 13, or 25, or 37, …

Trap: 12 × 18 = 216 minutes is a common multiple, but not the first one.

Try it. Two lights blink together now. One blinks every 8 seconds, the other every 20 seconds. After how many seconds do they next blink together?

Show the answer
  1. 8 = 2³ and 20 = 2² × 5.
  2. LCM = 2³ × 5 = 8 × 5 = 40 seconds. (Check: 8, 16, 24, 32, 40 and 20, 40 first meet at 40.)

Timeline from 0 to 80 minutes after 7:00. Bus A ticks every 12 minutes (0, 12, 24, 36, 48, 60, 72); bus B ticks every 18 minutes (0, 18, 36, 54, 72). They leave together at 0, 36 and 72 minutes: the multiples of the LCM, 36.

Edge cases.

  • LCM × GCF = the product of the two numbers. 36 × 6 = 216 = 12 × 18. So if you know one, you get the other.
  • Three cycles: take the LCM of all three.
  • Events that start at different times don't simply line up at the LCM; list the times or use remainders.

GMAT-level example. Three lights flash every 10, 12 and 15 seconds. They flash together now. How many more times do all three flash together in the next 10 minutes?

  1. 10 = 2 × 5, 12 = 2² × 3, 15 = 3 × 5. LCM = 2² × 3 × 5 = 60 seconds.
  2. 10 minutes = 600 seconds.
  3. They flash together at 60, 120, …, 600 seconds: 600 ÷ 60 = 10 more times.

Check yourself. The GCF of 12 and 18 is 6. Use it to find their LCM.

Check your answer

LCM = 12 × 18 ÷ 6 = 216 ÷ 6 = 36.

Equal groups: the GCF

If items must be split into identical groups with nothing left over, the number of groups must divide every count. The largest such number is the greatest common factor (GCF).

Why it works. The number of identical groups must divide each count exactly, or something is left over. The largest number that divides all the counts is the GCF, built from the primes they share, each with its smaller exponent.

How to spot it: "identical kits/bags/teams", "none left over", "greatest number of groups".

Example. A craft store has 84 red beads and 126 blue beads to divide into identical bracelets. What is the greatest number of bracelets it can make?

  1. Prime factors: 84 ÷ 2 = 42, 42 ÷ 2 = 21, 21 ÷ 3 = 7, so 84 = 2² × 3 × 7. And 126 ÷ 2 = 63, 63 ÷ 3 = 21, 21 ÷ 3 = 7, so 126 = 2 × 3² × 7.
  2. GCF: the shared primes, each with its smaller exponent: 2 × 3 × 7 = 42 bracelets.
  3. Each bracelet gets 84 ÷ 42 = 2 red beads and 126 ÷ 42 = 3 blue beads.

Trap: answering 2 or 3. Those are the beads in one bracelet, not the number of bracelets.

Edge cases.

  • Counts with no common prime have GCF 1: only one "group", with everything in it.
  • Largest square tile for a rectangle with no cutting: the GCF of the two side lengths.
  • Greatest number of groups and greatest group size are different questions: the first is the GCF, the second is each count ÷ GCF.

GMAT-level example. A floor 360 cm by 504 cm is covered with identical square tiles, with no cutting. What is the least number of tiles needed?

  1. Fewest tiles means the largest tile. Its side must divide both 360 and 504.
  2. 360 = 2³ × 3² × 5 and 504 = 2³ × 3² × 7. GCF = 2³ × 3² = 72 cm.
  3. Tiles: 360 ÷ 72 = 5 along one side, 504 ÷ 72 = 7 along the other.
  4. Total: 5 × 7 = 35 tiles.
360 cm side72727272725 tiles504 cm side727272727272727 tiles
A 72 cm tile fits both sides exactly: 5 × 7 = 35 tiles

Check yourself. What is the GCF of 48 and 180?

Check your answer

48 = 2⁴ × 3 and 180 = 2² × 3² × 5, so the GCF is 2² × 3 = 12.

Products of consecutive integers

Among any 2 consecutive integers, one is even. Among any 3, one is a multiple of 3. In general, among any k consecutive integers there is a multiple of k, a multiple of k − 1, and so on. So their product is divisible by k! (k factorial = k × (k − 1) × … × 1). Factor an expression to find consecutive integers hidden in it.

Why it works. Every 2nd integer is even, every 3rd is a multiple of 3, and so on, so any run of k consecutive integers contains a multiple of each number from 1 to k. In fact the product of k consecutive positive integers ÷ k! is the number of ways to choose k items, which is always a whole number.

How to spot it: n(n + 1)(n + 2), n³ − n, or "must be divisible by" for every integer n.

Example. For every integer n > 1, which must divide n³ − n: 4, 6 or 12?

  1. Factor: n³ − n = n(n² − 1) = (n − 1) × n × (n + 1). These are three consecutive integers.
  2. Their product is divisible by 3! = 3 × 2 × 1 = 6.
  3. Test 4 and 12 with n = 2: 2³ − 2 = 8 − 2 = 6. Neither 4 nor 12 divides 6.
  4. Answer: 6.

Trap: testing only one value of n. n = 3 gives 27 − 3 = 24, which 12 divides, so it seems to "confirm" 12. n = 2 shows that 12 does not always work.

Edge cases.

  • A 0 in the run makes the product 0, which every number divides.
  • Even starting points give more 2s. If n is even, n(n + 1)(n + 2) has two even factors, and one of them is a multiple of 4, so it is divisible by 24.
  • To disprove "must divide", one value of n is enough. To prove it, you need a reason.

GMAT-level example. If n is an odd integer, which must divide n² − 1: 8, 16 or 24?

  1. Factor: n² − 1 = (n − 1)(n + 1). With n odd, these are two consecutive even numbers.
  2. Of two consecutive even numbers, one is a multiple of 4. So the product has at least 2 × 4 = 8 as a factor.
  3. Test the others with n = 3: 3² − 1 = 8. Neither 16 nor 24 divides 8.
  4. Answer: 8.

Check yourself. Must 6 divide n(n + 1)(2n + 1) for every positive integer n?

Check your answer

Yes. n(n + 1) is even. For 3: if n or n + 1 is a multiple of 3, done; otherwise n is 1 more than a multiple of 3, and then 2n + 1 is a multiple of 3. (Check n = 1: 1 × 2 × 3 = 6.)

What must divide n

Write the condition in prime factors and find the smallest number that meets it. Every number that meets the condition is a multiple of that smallest case, so the smallest case's factors must divide n.

Why it works. A prime that divides n² must already divide n, because squaring n creates no new primes; it only doubles the exponents. So the condition on n² translates into a condition on the exponents in n.

How to spot it: "if n² (or 3n, or n/14) is an integer divisible by …, which must divide n?"

Example. n is a positive integer and n² is divisible by 72. What is the largest number that must divide n?

  1. 72 = 2³ × 3².
  2. n² = n × n, so every exponent in n² is double an exponent in n. That makes every exponent in n² even.
  3. n² needs at least 2³, and the next even exponent is 4. So n² needs at least 2⁴ × 3².
  4. Halve the exponents: n needs at least 2² × 3 = 4 × 3 = 12.
  5. Check n = 12: 12² = 144 = 2 × 72. ✓ So 12 is the smallest n, and the answer is 12.
n² needs 2³ × 3²round upeven exponents: 2⁴ × 3²halven needs 2² × 34 × 3smallest n = 12
A square has even exponents, so the 2³ in 72 forces 2⁴ in n²; halving gives n = 12

Trap: answering 6. It forgets that the 2³ in 72 forces at least 2⁴ in a perfect square. (6² = 36, which 72 does not divide.)

Edge cases.

  • Cubes work the same way, with exponents tripled. If n³ is divisible by 2⁴, n needs at least 2², because 3 × 2 = 6 ≥ 4.
  • "Must divide" vs. "could divide". If n² is divisible by 72, n could be 24 or 36, but only the factors of 12 must divide every such n.

GMAT-level example. n is a positive integer and n³ is divisible by 360. What is the smallest possible value of n?

  1. 360 = 2³ × 3² × 5.
  2. n³ has exponents 3 times those of n. It needs at least 2³ (so n needs 2¹), 3² (so n needs 3¹, because 3 × 1 = 3 ≥ 2) and 5¹ (so n needs 5¹).
  3. Smallest n = 2 × 3 × 5 = 30.
  4. Check: 30³ = 27,000, and 27,000 ÷ 360 = 75 ✓.

Check yourself. n² is divisible by 50. What is the largest number that must divide n?

Check your answer

50 = 2 × 5². n² needs at least 2² × 5², so n needs at least 2 × 5 = 10.

How hard questions disguise it

For harder questions (L4–L5)

L4 questions ask what must be true for every integer that meets a condition, so test the smallest case and one other. At L5, divisibility connects to prime factorization (counting divisors, powers of p in a factorial), to remainders (n leaves remainder 1 when divided by 4 and by 6, so n − 1 is a multiple of 12), and to counting (how many multiples of 3 or 5 are in a range). Break everything into primes first.

Practice

Drill factors, multiples, GCF and LCM in timed sets on the divisibility practice page.

Common traps

  • Mixing up GCF and LCM

    Splitting into identical groups needs a common factor: the GCF. Cycles or totals that must match up need a common multiple: the LCM. A product of the numbers is a multiple, never a common factor.

  • Using a common multiple that isn't the least

    a × b is always a common multiple, but when a and b share a factor there is a smaller one. Divide the product by the GCF, and check whether a smaller multiple also fits the question.

  • Adding or subtracting the numbers

    Sums and differences of the given numbers rarely divide, or are divisible by, those numbers. Ask what must divide what, and test the candidate.

  • Answering what's in each group instead of the number of groups

    The GCF is the number of groups; each count divided by the GCF is what goes in one group. Check which of the two the question asks for.

  • Choosing a number that fails one of the conditions

    A common factor must divide every number, and a common multiple must be divisible by every number. Test the choice against each one, not just the first.

  • Miscounting the multiples in a range

    Count from the first multiple inside the range to the last: (last − first) ÷ k + 1. Dividing the length of the range, or counting from 1, gives the wrong count.

  • Counting 'divisible by both' or 'by either' wrong

    Divisible by both a and b means divisible by LCM(a, b), not by a × b. 'Either' counts the two groups minus the overlap once; 'exactly one' removes the overlap from both groups.

  • Ignoring the range limit or the leftover

    If every grouping leaves r over, the total is r more than a common multiple, and it must also meet any size limit in the question. Check both conditions on your final number.

  • Over- or undershooting what must divide n

    If n² is a multiple of N, each prime in n needs at least half its exponent in N, rounded up. Find that smallest n; only its factors are guaranteed to divide every such n.

  • Forgetting 1 and n as factors

    Every integer above 1 has at least two factors, 1 and itself. Include both when you list or count factors.

  • Using a common factor that isn't the greatest

    Several numbers may divide both counts, but the most identical groups come from the greatest one. Compare prime factorizations and take every prime the two numbers share.