--- handout: B topic: nt-divisibility-counting domain: Number Theory level: mid–hard focus_area: true # one of Daisy's 9 --- # Handout B — Counting Multiples & Divisibility **When you see it:** *"How many numbers from 1 to N are divisible by …"* … *"How many days did she get **no** call?"* … *"…leaves a remainder of 1 when divided by 4, 5, and 6."* The counting is mechanical once you know three tools: **floor-counting**, **inclusion–exclusion**, and **LCM**. --- ## The three tools **Tool 1 — Count multiples with a floor.** The number of multiples of $k$ in $1,2,\dots,N$ is $$\left\lfloor \frac{N}{k}\right\rfloor \quad(\text{"round down"}).$$ E.g. multiples of $3$ up to $100$: $\lfloor 100/3\rfloor = 33$. **Tool 2 — "A or B" needs inclusion–exclusion.** You can't just add — the overlap gets counted twice, so subtract it back: $$|A\cup B| = |A| + |B| - |A\cap B|,$$ $$|A\cup B\cup C| = |A|+|B|+|C| \;-\;|A\cap B|-|A\cap C|-|B\cap C|\;+\;|A\cap B\cap C|.$$ (Add singles, **subtract** pairs, **add** the triple.) **Tool 3 — "divisible by both $a$ and $b$" means divisible by $\operatorname{lcm}(a,b)$.** So the overlaps in Tool 2 are counted with LCMs: $|A\cap B| = \big\lfloor N/\operatorname{lcm}(a,b)\big\rfloor$. > **Warm-up (pure method).** How many integers $1$–$100$ are divisible by $3$ **or** $5$? > $\lfloor100/3\rfloor + \lfloor100/5\rfloor - \lfloor100/15\rfloor = 33 + 20 - 6 = 47.$ --- ## Worked example 1 (mid) — 2017 AMC 8 #12 *(the LCM move)* **The smallest integer $>1$ that leaves a remainder of $1$ when divided by $4$, $5$, and $6$ lies between which pair?** $\;\textbf{(A) }2\text{–}19\ \textbf{(B) }20\text{–}39\ \textbf{(C) }40\text{–}59\ \textbf{(D) }60\text{–}79\ \textbf{(E) }80\text{–}124$ "Remainder $1$ when divided by $4,5,6$" means $N-1$ is a common multiple of $4,5,6$. The **smallest** such $N-1$ (past $0$) is $$\operatorname{lcm}(4,5,6) = 2^2\cdot 3\cdot 5 = 60,$$ so $N = 60+1 = 61$, which is in $\boxed{60\text{–}79}$. **(D)** *Key idea:* "same remainder $r$ for several divisors" ⟹ shift by $r$ and it becomes a **common multiple** ⟹ use LCM. Don't build LCM by multiplying $4\cdot5\cdot6=120$ — that double-counts the shared factor $2$. --- ## Worked example 2 (hard) — 2017 AMC 8 #24 *(3-set inclusion–exclusion + "count the opposite")* **Three grandchildren call every $3$, $4$, and $5$ days; all called on Dec 31, 2016. During the next year (365 days) on how many days did she get NO call?** $\;\textbf{(A) }78\ \textbf{(B) }80\ \textbf{(C) }144\ \textbf{(D) }146\ \textbf{(E) }152$ Days $1$–$365$. A call happens on multiples of $3$, $4$, or $5$. Count the days **with** a call, then subtract from $365$. **Singles:** $\lfloor365/3\rfloor=121,\quad \lfloor365/4\rfloor=91,\quad \lfloor365/5\rfloor=73.$ **Pairs (use LCMs $12,15,20$):** $\lfloor365/12\rfloor=30,\quad \lfloor365/15\rfloor=24,\quad \lfloor365/20\rfloor=18.$ **Triple (LCM $60$):** $\lfloor365/60\rfloor=6.$ $$\text{days with a call} = (121+91+73) - (30+24+18) + 6 = 285 - 72 + 6 = 219.$$ $$\text{no-call days} = 365 - 219 = \boxed{146}.\quad\textbf{(D)}$$ *Two traps:* (1) forgetting to **subtract** the pairs (you'd get $285$ and panic); (2) answering $219$ — the question asks for the **opposite** set, so finish with $365-219$. --- ## Worked example 3 (hard) — 2018 AMC 8 #21 *(simultaneous remainders — combine two at a time)* **How many three-digit integers leave remainder $2$ mod $6$, remainder $5$ mod $9$, and remainder $7$ mod $11$?** $\;\textbf{(A) }1\ \textbf{(B) }2\ \textbf{(C) }3\ \textbf{(D) }4\ \textbf{(E) }5$ When the remainders aren't $0$, LCM alone isn't enough — but you can still **merge two conditions at a time**. **Merge mod 6 and mod 9.** Their LCM is $18$, so the combined pattern repeats every $18$. List $n\equiv 5\ (\mathrm{mod}\ 9)$: $5,14,23,\dots$ — which is $\equiv 2\ (\mathrm{mod}\ 6)$? $14\bmod 6 = 2$ ✓. So $$n \equiv 14 \pmod{18}.$$ **Merge in mod 11.** Now the pattern repeats every $\operatorname{lcm}(18,11)=198$. Write $n = 18k+14$ and force $18k+14 \equiv 7 \pmod{11}$. Since $18\equiv 7$ and $14\equiv 3$: $\;7k + 3 \equiv 7 \Rightarrow 7k \equiv 4 \pmod{11}$. The inverse of $7$ is $8$ (because $7\cdot 8 = 56 \equiv 1$), so $k \equiv 4\cdot 8 = 32 \equiv 10 \pmod{11}$. Take $k=10$: $\;n = 18\cdot 10 + 14 = 194$. So $$n \equiv 194 \pmod{198}.$$ **Count the three-digit ones:** $194,\;392,\;590,\;788,\;986$ (next is $1184$, too big) → $\boxed{5}$. **(E)** *Check $194$:* $194\bmod 6=2$, $194\bmod 9=5$, $194\bmod 11=7$. ✓ *Idea:* solve simultaneous remainders by **collapsing two congruences into one** (mod their LCM), then repeat. Never brute-force all 900 numbers. --- ## Common mistakes (check yourself) 1. **Adding instead of inclusion–exclusion** for "A or B" — you double-count the overlap. 2. **Multiplying the divisors** to get a common period. Use $\operatorname{lcm}$, not the product ($\operatorname{lcm}(4,6)=12$, not $24$). 3. **Answering the count you built, not the one asked** — "no-call days" = total − "call days." 4. **Floor errors:** $\lfloor 365/4\rfloor = 91$ (since $4\cdot 91=364$), not $92$. --- ## Practice — do these, then check the key **P1.** The 5-digit number $\underline{2}\,\underline{0}\,\underline{1}\,\underline{8}\,\underline{U}$ is divisible by $9$. What is the remainder when this number is divided by $8$? **(A)** 1 **(B)** 3 **(C)** 5 **(D)** 6 **(E)** 7 **P2.** A number is called *flippy* if its digits alternate between two distinct digits. For example, $2020$ and $37373$ are flippy, but $3883$ and $123123$ are not. How many five-digit flippy numbers are divisible by $15$? **(A)** 3 **(B)** 4 **(C)** 5 **(D)** 6 **(E)** 8 **P3.** Isabella has $6$ coupons for free ice cream cones. She redeems one every $10$ days until they are all used. Pete's is closed on Sundays, and none of her $6$ redemption dates falls on a Sunday. On what day of the week does Isabella redeem her *first* coupon? **(A)** Monday **(B)** Tuesday **(C)** Wednesday **(D)** Thursday **(E)** Friday **P4.** *(hard)* Minh enters the numbers $1$ through $81$ into the cells of a $9 \times 9$ grid in some order. She computes the product of the numbers in each row and column. What is the least number of rows and columns that could have a product divisible by $3$? **(A)** 8 **(B)** 9 **(C)** 10 **(D)** 11 **(E)** 12 Log which ones she missed (by problem number) — those tell us what to drill next.
Answer key — with solutions - **P1 = (B) 3.** Digit sum $2+0+1+8+U = 11+U$ is divisible by $9$ ⟹ $U=7$, so the number is $20187$. $20187 = 8\cdot 2523 + 3$ ⟹ remainder $\mathbf{3}$. - **P2 = (B) 4.** $\div 15 \Leftrightarrow \div 5$ **and** $\div 3$. A flippy 5-digit number is $\overline{ababa}$; the last digit $a$ must be $0$ or $5$, but the leading digit $a\ne 0$, so $a=5$: $\overline{5b5b5}$. Digit sum $15+2b$ divisible by $3$ ⟹ $b\in\{0,3,6,9\}$ → **4** numbers. - **P3 = (C) Wednesday.** Redemption offsets are $0,10,20,30,40,50$ days. Mod $7$ these are $0,3,6,2,5,1$ — six distinct residues, missing only $4$. For none to land on Sunday, Sunday must *be* that missing residue $4$, which forces the first coupon (offset $0$) onto **Wednesday**. - **P4 = (D) 11.** A line's product is divisible by $3$ ⟺ it contains a multiple of $3$. There are $27$ multiples of $3$ in $1$–$81$. Confine them to an $r\times c$ block (needs $r\cdot c \ge 27$); then exactly those $r$ rows and $c$ columns are divisible by $3$. Minimize $r+c$ with $rc\ge 27$: $4\times 7=28$ gives $r+c=\mathbf{11}$, and $r+c=10$ caps at $5\times5=25<27$, so $11$ is best.
*Companion: Handout A — Counting Divisors (`nt-divisor-counting.md`).*