Divisibility & Factors

What you need to know

• Fundamental Theorem of Arithmetic. Every whole number $n > 1$ is a product of primes in exactly one way (apart from order). We write $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, where the $p_i$ are different primes and the $a_i$ are their exponents. Example: $360 = 2^3\cdot3^2\cdot5$, and no other primes multiply to $360$.
• Counting divisors. Write $d(n)$ for the number of positive divisors of $n$. Then $d(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$, because a divisor uses anywhere from $0$ to $a_i$ copies of each prime $p_i$: that is $a_i+1$ choices. Example: $72 = 2^3\cdot3^2$ has $4\cdot3 = 12$ divisors.
• Adding divisors. Write $\sigma(n)$ (Greek "sigma") for the sum of the positive divisors. Multiply one sum per prime: $\sigma(n) = (1+p_1+\dots+p_1^{a_1})\cdots(1+p_k+\dots+p_k^{a_k})$. Example: $\sigma(72) = (1+2+4+8)(1+3+9) = 15\cdot13 = 195$.
• Divisors come in pairs $d$ and $\frac{n}{d}$. So $n$ has an odd number of divisors exactly when $n$ is a perfect square, since only then does one divisor, $\sqrt n$, pair with itself. Example: $36$ pairs up as $1\cdot36$, $2\cdot18$, $3\cdot12$, $4\cdot9$, $6\cdot6$, giving $9$ divisors.
• Divisibility rules. Last digit for $2$, $5$, $10$; last two digits for $4$, $25$; last three digits for $8$; digit sum for $3$, $9$; alternating digit sum (add and subtract the digits in turn) for $11$. Example: $7425$ is divisible by $25$ (ends in $25$), by $9$ ($7+4+2+5 = 18$), and by $11$ ($7-4+2-5 = 0$).
• Counting multiples. From $1$ to $N$ there are $\lfloor N/k \rfloor$ multiples of $k$, where $\lfloor\ \rfloor$ (the floor) means round down. Example: $\lfloor 100/7 \rfloor = 14$ multiples of $7$ up to $100$, the last being $98$.
• Combining. If $a$ divides both $b$ and $c$, then $a$ divides $bx+cy$ for any integers $x$ and $y$. Example: $7$ divides $21$ and $35$, so it divides $3\cdot21+2\cdot35 = 133$.

How AMC 10 tests it

• Early problems (1–8) factor the contest year and ask for a sum or a digit fact about its factors.
• Middle problems (10–18) ask "how many positive divisors of $N$ are …" (even, perfect squares, multiples of $6$). That is $d(n)$ with limits on the exponents.
• "How many integers up to $N$ are divisible by $a$ or $b$ but not $c$?" combines floor counting with the Principle of Inclusion-Exclusion (PIE).
• Products of consecutive integers: which number must divide $n(n+1)(n+2)$? One counterexample rules a choice out.
• Late problems go backwards: given $d(n)$ or $\sigma(n)$, find the smallest such $n$ or count the possibilities.

Standard approaches

1. Prime factorize right away; almost every divisor question becomes a question about exponents.
2. To count divisors with a property, list the allowed exponents for each prime and multiply. Example: an even divisor of $2^3\cdot3^2$ has $1$ to $3$ twos and $0$ to $2$ threes: $3\cdot3 = 9$.
3. For the smallest $n$ with a given number of divisors, write that number as a product $(a_1+1)(a_2+1)\cdots$, give the largest exponents to the smallest primes, and compare every such product.
4. Count multiples with floors, and handle overlaps with the lcm: numbers divisible by both $a$ and $b$ are the multiples of $\text{lcm}(a,b)$.
5. For a "must divide" claim, test one small example such as $5\cdot6\cdot7$.

Worked example

Let $N$ be the smallest positive integer with exactly $20$ positive divisors. What is the sum of the digits of $N$?

(A) $4$ (B) $6$ (C) $8$ (D) $9$ (E) $12$

Step 1: the shapes. The divisor count is a product of (exponent $+1$) factors. So write $20$ as a product of factors that are each at least $2$, largest first: $20$, $10\cdot2$, $5\cdot4$, $5\cdot2\cdot2$.

Step 2: smallest number for each shape. Subtract $1$ from each factor to get the exponents, and give the biggest exponent to $2$, the next to $3$, then $5$:

• $20$ gives $2^{19} = 524288$.
• $10\cdot2$ gives $2^9\cdot3 = 1536$.
• $5\cdot4$ gives $2^4\cdot3^3 = 432$.
• $5\cdot2\cdot2$ gives $2^4\cdot3\cdot5 = 240$.

Step 3: pick the smallest. $N = 240$, and its digit sum is $2+4+0 = 6$.

The answer is $\boxed{\textbf{(B)}\ 6}$.

Pitfalls

• Forgetting the $+1$: $2^4\cdot3^3$ has $5\cdot4 = 20$ divisors, not $4\cdot3 = 12$.
• Counting $1$ and $n$ inconsistently. "Proper divisors" leaves out $n$ itself, so check the wording. Example: $12$ has $6$ divisors but $5$ proper divisors.
• Assuming the shape with the most factors always gives the smallest $n$; compare them all. Example: for $8$ divisors, $2\cdot2\cdot2$ gives $2\cdot3\cdot5 = 30$, but $4\cdot2$ gives $2^3\cdot3 = 24$.
• Using $ab$ instead of $\text{lcm}(a,b)$ in PIE when $a$ and $b$ share a factor. Example: up to $100$, the numbers divisible by both $4$ and $6$ are the $8$ multiples of $12$, not the $4$ multiples of $24$.

Traps that recur

• Counting only the 15 primes as failures (answer 35) and missing that n = 4 also fails, or forgetting that n = 1 works. (2019 AMC 10A #25)
• Counting only the n with d(n) = 6 (eight of them) and missing 36 and 48, whose f_1 values 18 and 20 also feed into the fixed point 12. (2021 AMC Fall 10A #23)
• Trying to compute C(52,10) exactly, or using divisibility by 11 (which every choice satisfies) and getting nowhere. (2020 AMC 10B #19)
• Answering 121 by forgetting the word 'distinct', or subtracting only the two obvious cases 1 and 10^10 to get 119. (2019 AMC 10B #19)