2004 AMC 10B Problem 21

The first progression is $3k + 1$ for $k = 0, 1, \dots, 2003$: the numbers $\equiv 1 \pmod 3$ from $1$ up to $3 \cdot 2003 + 1 = 6010$. The second is $7l + 9$ for $l = 0, \dots, 2003$: the numbers $\equiv 2 \pmod 7$ from $9$ up to $7 \cdot 2003 + 9 = 14030$.

The two lists contribute $2004 + 2004 = 4008$ terms, and $|S|$ is $4008$ minus the number of values appearing in both.

A common value must be $1 \pmod 3$ and $2 \pmod 7$. The smallest such number is $16$ ($16 = 15 + 1 = 14 + 2$), and the condition repeats with period $\operatorname{lcm}(3, 7) = 21$, so the common candidates are $16, 37, 58, \dots$, i.e. $16 + 21m$. They must also lie within both ranges: at least $9$ (automatic) and at most $6010$, the cap of the first progression, which is the binding one. From $16 + 21m \le 6010$ we get $m \le \frac{5994}{21} = 285.4\ldots$, so $m = 0, 1, \dots, 285$: $286$ common values.

Therefore
$$|S| = 4008 - 286 = 3722.$$

The answer is $\boxed{\textbf{(A)}\ 3722}$.

Two arithmetic progressions with coprime differences overlap in a single arithmetic progression whose difference is the product; a quick search finds its first term, and residues do the rest. The counting step is then inclusion-exclusion, and the only delicate point is the range: a shared value must satisfy both sequences' limits, so the shorter reach ($6010$) governs.

Count within the second progression: $7l + 9 \equiv l \pmod 3$, so $7l + 9 \equiv 1 \pmod 3$ exactly when $l \equiv 1 \pmod 3$; and $7l + 9 \le 6010$ means $l \le 857$. The values $l = 1, 4, \dots, 856$ number $\frac{856 - 1}{3} + 1 = 286$.

• Counting common terms over the second sequence's full range (up to 14030) instead of stopping at 6010, where the first sequence ends.
• Forgetting the overlap altogether ($4008$) or an off-by-one in the count of $16 + 21m$ (getting $285$ or $287$).