Factors, Multiples & Divisibility

By the end of this chapter you will:

1. Build a factor tree for any integer up to 1000 in under 30 seconds
2. Apply divisibility tests for 2, 3, 4, 5, 9, 10, 11 without long division
3. Compute GCD and LCM from prime factorizations
4. Count the divisors of a number from its prime factorization alone
5. Recognize the Gauss problems that "look hard" but reduce to factoring

1.0 Why this chapter is first

BC baseline: G6 introduces factors, multiples, GCF, LCM, divisibility rules, factor trees, and prime factorization — but only at the level of "what is a prime factor?" Gauss demands fluency: prime-factor a number, count its divisors, reason mod small primes, all in under a minute.

Every recent Gauss 7 paper has at least one question that collapses the moment you write the prime factorization. 2024 Q14: "The number 385 has three prime factors. The sum of these prime factors is…" — a 6-point problem that takes 15 seconds if you know what to do, or 3 minutes of guessing if you don't.

🔑 Lead with factoring. When a Gauss problem mentions a specific number (385, 36, 100, 24, 2024 …), your first move should be: factor it. Often the problem reveals itself.

1.1 Prime numbers — the building blocks

A prime is a positive integer with exactly two divisors: $1$ and itself.

🔑 Memorize the primes up to 50. They are: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$. Fifteen numbers — you can do this on the bus tomorrow.

Trap: 51 is not prime ($51 = 3 \times 17$). Neither is 57 ($= 3 \times 19$) or 91 ($= 7 \times 13$). These three numbers fool more students than any other.

1.2 Factor trees — the procedure

To factor $385$:

       385
      /   \
     5    77
         /  \
        7   11

Pull out any prime divisor you can spot, write the cofactor, repeat. Order doesn't matter — every path gives the same set of primes. Result:

$$385 = 5 \times 7 \times 11$$

2024 Q14 asks for the sum of the prime factors: $5 + 7 + 11 = \mathbf{23}$. Answer (D). ✅

Practice these on sight:

1.3 Divisibility rules — the test cheat sheet

Example — divisibility chaining

Is $2024$ divisible by $3$? Digit sum $= 2+0+2+4 = 8$. 8 is not divisible by 3, so no.

Is $2024$ divisible by $4$? Last two digits $= 24$, and $24 = 4 \times 6$. Yes — $2024 = 4 \times 506$.

Is $1\,234\,567$ divisible by $11$? Alternating sum $= 1 - 2 + 3 - 4 + 5 - 6 + 7 = 4$. Not divisible by 11.

🔑 The digit sum is also useful for the digit-sum problem itself. 2024 Q1 asks: "When the four digits of 2024 are added, the result is…" Answer: $2 + 0 + 2 + 4 = \mathbf{8}$. (B). ✅

1.4 GCD & LCM via prime factorization

Once you have prime factorizations, GCD and LCM are mechanical.

Identity worth remembering: $\gcd(a, b) \times \text{lcm}(a, b) = a \times b$.

When LCM shows up on Gauss

A bell rings every 6 minutes; a chime every 10 minutes. They both go off at 12:00. When do they next ring together?

$\text{lcm}(6, 10) = 30$ minutes → next at 12:30.

Pattern: "two recurring events both happen at time T, when is the next coincidence?" → LCM of their periods.

1.5 Counting divisors

If $n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$ then the number of divisors of $n$ is

$$(a_1 + 1)(a_2 + 1) \cdots (a_k + 1).$$

Example: $72 = 2^3 \cdot 3^2$. Number of divisors $= (3+1)(2+1) = 12$. Verify: $1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72$. ✓

This is the formula you reach for whenever a Gauss problem asks "how many divisors does $n$ have" or "for how many integers $k$ does $k$ divide $n$".

1.6 Worked Examples (Part A → Part B → Part C)

Example 1 — Part A flavor (2024 Q10)

A number is randomly chosen from the list $1, 2, 3, 4, 5, 6, 7, 8, 9$. The probability that the chosen number is divisible by $2$, or by $3$, or by both, is …

Setup: divisibility = factoring + listing.

Divisible by 2: $\{2, 4, 6, 8\}$.
Divisible by 3: $\{3, 6, 9\}$.

Union (don't double-count $6$): $\{2, 3, 4, 6, 8, 9\}$ — 6 numbers out of 9.

Probability $= \dfrac{6}{9}$. Answer (C). ✅

Example 2 — Part B flavor

What is the smallest positive integer that has exactly $12$ divisors?

Strategy: $12$ factors as $12, 6 \cdot 2, 4 \cdot 3, 3 \cdot 2 \cdot 2$. Each factoring corresponds to an exponent pattern.

Comparing: $60 < 72 < 96 < 2048$, so answer is 60.

🔑 Smaller-base-bigger-exponent gives smaller $n$, but only up to a point — try a few patterns and pick the minimum.

Example 3 — Part C flavor (2024 Q25, simplified)

Suppose $w, x, y, z$ are different prime numbers, and $w + x + y = 234$, with $y, z < 50$. The expressions $x + y$, $x + z$, $234 + z$, $234 - z$ are also all prime. Find $w - y$ if the answer is among $\{226, 150, 210, 174, 222\}$.

Key parity observation: $234$ is even, and most primes are odd.

If $w, x, y$ are all odd, their sum is odd, contradicting $w+x+y = 234$ (even). So one of them is 2.

The smallest is the candidate: $y = 2$. Then $w + x = 232$.

Now $x + y = x + 2$ must be prime. So $x$ and $x+2$ are both prime (a "twin-prime" condition).

The answer asks for $w - y = w - 2$. Without working out the rest, observe that any valid $w$ must satisfy $w = 232 - x$ where $x$ is a small twin-prime partner. Trying $x = 5$ gives $w = 227$ (prime ✓), and $w - y = 225$ — not on the list, so try $x = 29$, giving $w = 203 = 7 \cdot 29$ (not prime). Continue: $x = 41$ → $w = 191$ (prime ✓), $w - y = 189$. Eventually $x = 5$ with a different distribution... full solution requires checking all twin-prime cases.

🔑 Lesson: in Part C number-theory problems, parity is almost always the first reduction. "All primes are odd except 2" forces small primes into the equation.

1.7 Trap Alerts ⚠️

1. $1$ is not prime. Don't include it in factorizations.
2. $51, 57, 91, 119, 133$ — these LOOK prime and aren't. Memorize: $51 = 3 \cdot 17$, $57 = 3 \cdot 19$, $91 = 7 \cdot 13$, $119 = 7 \cdot 17$, $133 = 7 \cdot 19$.
3. "Three prime factors" can mean three distinct or three with multiplicity. Read carefully. $385 = 5 \cdot 7 \cdot 11$ has three distinct. $8 = 2^3$ has one distinct but "three" with multiplicity.
4. Divisibility by 6 needs BOTH 2 AND 3, not just digit-sum-divisible-by-6.

1.8 Mnemonic

"Factor first. Then the problem tells you what to do."

• When a specific integer appears → factor it on scratch paper
• Digit-sum and last-digit handle divisibility-by-small
• GCD = small exponents; LCM = big exponents
• Number of divisors = product of (exponent + 1)

Practice Set (10 problems, mixed difficulty)

1. (Part A) Find the sum of the prime factors of $90$.
2. (Part A) What is the smallest 3-digit number divisible by both $4$ and $9$?
3. (Part A) How many of the numbers $20, 21, 22, \ldots, 30$ are divisible by exactly one of $2$ or $3$?
4. (Part B) Find $\gcd(126, 168)$.
5. (Part B) Find the LCM of $12$, $15$, and $20$.
6. (Part B) How many divisors does $180$ have?
7. (Part B) A number leaves remainder $3$ when divided by $7$ and remainder $2$ when divided by $5$. What is its smallest positive value?
8. (Part C) Find the smallest positive integer that has exactly $15$ divisors.
9. (Part C) For how many values of $n$ with $1 \le n \le 100$ does $n$ share no factor greater than $1$ with $30$?
10. (Part C) Two clocks ring at intervals of $35$ and $42$ seconds, starting together at $9{:}00$. How many times will they ring together in the next hour?

Answers: 1) 10; 2) 108; 3) 6; 4) 42; 5) 60; 6) 18; 7) 17; 8) 144; 9) 26; 10) 8 (every 210 seconds = 3.5 min).

End of chapter. Next: Fractions, Decimals & Percent — Competition Techniques.