--- handout: A topic: nt-divisor-counting domain: Number Theory level: mid–hard focus_area: true # one of Daisy's 9 --- # Handout A — Counting Divisors ("How many factors does N have?") **When you see it:** *"How many positive factors / divisors does N have?"* … *"How many divisors are even / odd / perfect squares?"* … *"How many factors of N have more than 3 factors?"* These almost never want you to list every divisor. They want the **prime factorization** and one short formula. --- ## The one method you must own **Step 1 — Prime-factorize.** Write $$N = p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}.$$ **Step 2 — Multiply the (exponent + 1)'s.** The number of positive divisors is $$d(N) = (a_1+1)(a_2+1)\cdots(a_k+1).$$ *Why it works:* to **build** a divisor you choose how many copies of each prime to include. For $p_1$ you may take $0,1,2,\dots,a_1$ copies — that's $a_1+1$ choices. The choices for different primes are independent, so you **multiply**. Every combination gives a different divisor, and every divisor comes from exactly one combination. **Memorize these three tiny facts** (they unlock the hard problems): | how many factors | which numbers | |---|---| | exactly **1** | just $1$ | | exactly **2** | the **primes** ($p$) | | exactly **3** | **squares of primes** ($p^2$) | Anything else has **4 or more** factors. --- ## Worked example 1 (mid) — 2018 AMC 8 #18 **How many positive factors does $23{,}232$ have?** $\;\textbf{(A) }9\ \textbf{(B) }12\ \textbf{(C) }28\ \textbf{(D) }36\ \textbf{(E) }42$ **Step 1 — factor.** Peel off 2's: $23232 \to 11616 \to 5808 \to 2904 \to 1452 \to 726 \to 363$. That's six halvings, so $2^6$. Now $363 = 3\cdot 121 = 3\cdot 11^2$. So $$23232 = 2^{6}\cdot 3^{1}\cdot 11^{2}.$$ **Step 2 — the formula.** $d(N) = (6+1)(1+1)(2+1) = 7\cdot 2\cdot 3 = \boxed{42}.$ **(E)** > **Same picture, harder question — even vs odd divisors.** How many of those 42 are **odd**? An odd divisor > uses **zero** 2's, so it's a divisor of $3\cdot 11^2$: that's $(1+1)(2+1)=6$ of them. The **even** ones are the > rest: $42-6 = 36$. (Trick: "odd divisors of $N$" = divisors of $N$ with all factors of 2 stripped out.) --- ## Worked example 2 (hard) — 2020 AMC 8 #17 **How many factors of $2020$ have more than $3$ factors?** $\;\textbf{(A) }6\ \textbf{(B) }7\ \textbf{(C) }8\ \textbf{(D) }9\ \textbf{(E) }10$ This is a "divisor **of** a divisor" problem — the tiny table above is the whole game. **Step 1 — factor 2020 and list its divisors.** $2020 = 2^2\cdot 5\cdot 101$, so it has $(2+1)(1+1)(1+1)=12$ divisors: $$1,\;2,\;4,\;5,\;10,\;20,\;101,\;202,\;404,\;505,\;1010,\;2020.$$ **Step 2 — flip the question (complementary counting).** "More than 3 factors" is hard to test one by one. Its **opposite** — *3 or fewer* factors — is exactly the table: **1**, a **prime**, or a **prime²**. Cross those out of the list: - $1$ → 1 factor ✗ - $2,\,5,\,101$ → prime, 2 factors ✗ - $4 = 2^2$ → prime², 3 factors ✗ That's **5** divisors with $\le 3$ factors. Everything else has more: $$12 - 5 = \boxed{7}.\quad\textbf{(B)}$$ (The survivors are $10,20,202,404,505,1010,2020$ — each is a product of at least two different primes, so each has $\ge 4$ factors. Good check: 7 of them. ✓) **The trap:** most students try to count the "more than 3" numbers **directly** and miss one, or forget that $4=2^2$ sneaks in with only 3 factors. Counting the *small, easy* group ($1$, primes, prime²) and subtracting is faster and safer. This "count the opposite" move is worth its own reflex. --- ## Common mistakes (check yourself) 1. **Adding instead of multiplying** the $(a_i+1)$'s. It's $(6+1)(1+1)(2+1)=42$, **not** $7+2+3$. 2. **Forgetting the "+1".** Each exponent contributes *exponent + 1* choices (you can take **zero** copies). 3. **Not fully factoring.** $23232 = 2^6\cdot 363$ isn't done — $363$ still splits into $3\cdot 11^2$. 4. **Missing that $p^2$ has 3 factors** (e.g. $4, 9, 25, 49$). That's the classic AMC 8 booby-trap. --- ## Practice — do these, then check the key **P1.** When three positive integers $a$, $b$, and $c$ are multiplied together, their product is $100$. Suppose $a < b < c$. In how many ways can the numbers be chosen? **(A)** 0 **(B)** 1 **(C)** 2 **(D)** 3 **(E)** 4 **P2.** Let $N$ be the greatest five-digit number whose digits have a product of $120$. What is the sum of the digits of $N$? **(A)** 15 **(B)** 16 **(C)** 17 **(D)** 18 **(E)** 20 **P3.** Let $Z$ be a 6-digit positive integer, such as $247247$, whose first three digits are the same as its last three digits taken in the same order. Which of the following numbers *must* also be a factor of $Z$? **(A)** 11 **(B)** 19 **(C)** 101 **(D)** 111 **(E)** 1111 **P4.** *(hard)* For any positive integer $M$, $M!$ denotes the product of the integers $1$ through $M$. What is the largest integer $n$ for which $5^n$ is a factor of the sum $98!+99!+100!$? **(A)** 23 **(B)** 24 **(C)** 25 **(D)** 26 **(E)** 27 Log which ones she missed (by problem number) — those tell us what to drill next.
Answer key — with solutions - **P1 = (E) 4.** $100=2^2\cdot5^2$. The triples $a *Companion: Handout B — Counting Multiples & Divisibility (`nt-divisibility-counting.md`).*