AMC 10 · 2023 · #18

Grade 8 number-theory

gcdprime-factorizationdivisibility-ruleslogical-deduction caseworkconvert-to-algebralogical-deduction ↑ Prerequisites: gcdprime-factorization

📏 Long solution 💡 3 insights

Problem

Suppose $a$ , $b$ , and $c$ are positive integers such that $\frac{a}{14}+\frac{b}{15}=\frac{c}{210}.$ Which of the following statements are necessarily true?

I. If $\gcd(a,14)=1$ or $\gcd(b,15)=1$ or both, then $\gcd(c,210)=1$ .

II. If $\gcd(c,210)=1$ , then $\gcd(a,14)=1$ or $\gcd(b,15)=1$ or both.

III. $\gcd(c,210)=1$ if and only if $\gcd(a,14)=\gcd(b,15)=1$ .

Pick an answer.

(A)

$~\text{I, II, and III}$

(B)

$~\text{I only}$

(C)

$~\text{I and II only}$

(D)

$~\text{III only}$

(E)

$~\text{II and III only}$

View mode:

Toolkit + CCSS Solution

Understand

Restated: Positive integers $a, b, c$ satisfy $\dfrac{a}{14} + \dfrac{b}{15} = \dfrac{c}{210}$. Decide which of the three statements I, II, III about $\gcd(a,14), \gcd(b,15), \gcd(c,210)$ are necessarily true, and pick the choice naming exactly that set.

Givens: $\dfrac{a}{14} + \dfrac{b}{15} = \dfrac{c}{210}$ with $a, b, c \in \mathbb{Z}_{>0}$; $210 = 2 \cdot 3 \cdot 5 \cdot 7,\ 14 = 2 \cdot 7,\ 15 = 3 \cdot 5$; Statement I: $\gcd(a,14)=1$ or $\gcd(b,15)=1$ $\Rightarrow$ $\gcd(c,210)=1$; Statement II: $\gcd(c,210)=1$ $\Rightarrow$ $\gcd(a,14)=1$ or $\gcd(b,15)=1$; Statement III: $\gcd(c,210)=1$ iff $\gcd(a,14)=\gcd(b,15)=1$; Answer choices: (A) I, II, III; (B) I only; (C) I and II; (D) III only; (E) II and III only

Unknowns: Which subset of $\{$I, II, III$\}$ consists of statements that are necessarily true

Understand

Plan

Primary tool: #7 Identify Subproblems

Secondary: #3 Eliminate Possibilities, #13 Convert to Algebra

Three independent yes/no questions live in one problem — perfect setup for Tool #7 (Identify Subproblems). Clear denominators first: multiplying by $210$ gives $c = 15a + 14b$. Then test each statement separately. Tool #3 (Eliminate Possibilities) supplies a single counterexample to kill Statement I. Tool #13 (Convert to Algebra) — specifically modular reduction mod $2, 3, 5, 7$ — settles Statement III, and Statement II follows immediately because "and" implies "or".

Execute — Answer: E

#13 Convert to Algebra 6.NS.B.4 Step 1

Clear denominators.
The least common multiple of $14, 15, 210$ is $210$.
Multiplying every term by $210$ turns the fractional equation into a clean integer linear relation among $a, b, c$.

$$210\cdot\dfrac{a}{14} + 210\cdot\dfrac{b}{15} = 210\cdot\dfrac{c}{210} \;\Longrightarrow\; c = 15a + 14b$$

💡 Working with $c = 15a + 14b$ is much easier than fractions — and the coprime split $15 = 3\cdot 5$, $14 = 2\cdot 7$ already hints that the primes will separate cleanly.

#3 Eliminate Possibilities 6.NS.B.4 Step 2

Test Statement I with the smallest counterexample.
Pick $a = 1$ so $\gcd(a, 14) = 1$ (hypothesis satisfied).
Pick $b = 3$, giving $c = 15(1) + 14(3) = 57 = 3 \cdot 19$.
Now $\gcd(c, 210) = \gcd(57, 210) = 3 \ne 1$ — conclusion fails.
So Statement I is FALSE.

$$a=1,\ b=3 \Rightarrow c=57,\ \gcd(57,210)=3$$

💡 One counterexample is enough to kill a universal claim — choose $a$ to satisfy the hypothesis, then $b$ to sneak a forbidden prime into $c$.

#7 Identify Subproblems 8.EE.C.7 Step 3

Prove the forward direction of Statement III: if $\gcd(a, 14) = 1$ and $\gcd(b, 15) = 1$, then $c = 15a + 14b$ avoids each prime in $\{2, 3, 5, 7\}$.
Mod $2$: $c \equiv a \pmod 2$ and $\gcd(a,14)=1$ forces $a$ odd.
Mod $7$: $c \equiv a \pmod 7$ and $\gcd(a,14)=1$ forces $7\nmid a$.
Mod $3$: $c \equiv 2b \pmod 3$ and $\gcd(b,15)=1$ forces $3\nmid b$.
Mod $5$: $c \equiv 4b \pmod 5$ and $\gcd(b,15)=1$ forces $5\nmid b$.

$$c \not\equiv 0 \pmod{2,3,5,7} \;\Longrightarrow\; \gcd(c,210)=1$$

💡 Reducing $c = 15a + 14b$ mod each prime kills one of the two terms, so divisibility of $c$ by that prime is forced by just one variable — making each case a one-line check.

#7 Identify Subproblems 6.NS.B.4 Step 4

Prove the reverse direction of Statement III via the gcd identity $\gcd(x + ky, y) = \gcd(x, y)$.
Mod $14$: $\gcd(c, 14) = \gcd(15a + 14b, 14) = \gcd(15a, 14) = \gcd(a, 14)$ since $\gcd(15, 14) = 1$.
Mod $15$: $\gcd(c, 15) = \gcd(14b, 15) = \gcd(b, 15)$.
So $\gcd(c, 210) = 1$ forces $\gcd(c, 14) = \gcd(c, 15) = 1$, hence $\gcd(a, 14) = \gcd(b, 15) = 1$.

$$\gcd(c,14)=\gcd(a,14),\quad \gcd(c,15)=\gcd(b,15)$$

💡 Modding out the $14b$ piece leaves $15a$ mod $14$, and since $15 \equiv 1$ mod $14$ the gcd with $14$ is just $\gcd(a,14)$ — same trick the other way.

#3 Eliminate Possibilities 6.NS.B.4 Step 5

Wrap up Statement II.
Statement III's reverse direction says $\gcd(c,210)=1 \Rightarrow \gcd(a,14)=1$ AND $\gcd(b,15)=1$.
Since (P AND Q) implies (P OR Q), Statement II — which only asks for the weaker OR conclusion — is automatically true.
So II and III are the necessarily-true ones; I fails.

$$\text{(II AND III true,\ I false)} \;\Rightarrow\; \textbf{(E) }\text{II and III only}$$

💡 A logical "and" is stronger than "or" — once we proved the harder "and" claim of III, the weaker "or" claim of II rides along for free.

[1] #13 6.NS.B.4 Clear denominators. The least common multiple of $14, 15, 210$ is $210$. Multipl

[2] #3 6.NS.B.4 Test Statement I with the smallest counterexample. Pick $a = 1$ so $\gcd(a, 14)

[3] #7 8.EE.C.7 Prove the forward direction of Statement III: if $\gcd(a, 14) = 1$ and $\gcd(b,

[4] #7 6.NS.B.4 Prove the reverse direction of Statement III via the gcd identity $\gcd(x + ky,

[5] #3 6.NS.B.4 Wrap up Statement II. Statement III's reverse direction says $\gcd(c,210)=1 \Rig

Review

Reasonableness: Cross-check Statement III on a clean example: $a=1, b=1$ gives $c = 15 + 14 = 29$ — prime, so $\gcd(29, 210) = 1$, matching $\gcd(1, 14) = \gcd(1, 15) = 1$. Cross-check the reverse: any $c$ coprime to $210$ comes from $(a, b)$ where $a$ is coprime to $14$ and $b$ to $15$. Counterexample to I: $a=1, b=3$ gives $c = 57$, $\gcd(57, 210) = 3 \ne 1$ despite $\gcd(1, 14)=1$. So I is false, III is true (both directions), II is true (weaker than III's reverse). The right choice is (E) II and III only.

Alternative: Tool #5 (Look for a Pattern) by tabulating small $(a, b)$ pairs and computing $c$ and the four gcds. For instance, $(a, b) \in \{(1,1), (1,3), (2,1), (7,15)\}$ produces $c \in \{29, 57, 44, 315\}$ with gcd $(c, 210) \in \{1, 3, 2, 105\}$ — the pattern $\gcd(c,14) = \gcd(a, 14)$ and $\gcd(c, 15) = \gcd(b, 15)$ pops out empirically, leading to the same conclusion (E).

CCSS standards used (min grade 8)

6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Computing concrete gcds like $\gcd(57, 210) = 3$ in the counterexample to I and applying the identity $\gcd(x + ky, y) = \gcd(x, y)$ to bridge $\gcd(c, 14)$ and $\gcd(a, 14)$.)
8.EE.C.7 Solve linear equations in one variable (Reducing $c = 15a + 14b$ modulo each prime in $\{2, 3, 5, 7\}$ to a one-variable congruence (e.g. $c \equiv a \pmod 7$) and reading off divisibility.)

⭐ Multiplying through by $210$ turns the equation into $c = 15a + 14b$. Mod each prime in $\{2, 3, 5, 7\}$, one of the two terms vanishes, so $\gcd(c, 210) = 1$ is equivalent to $\gcd(a, 14) = \gcd(b, 15) = 1$ (Statement III). That "and" automatically implies the "or" in Statement II, but Statement I fails because $a = 1, b = 3$ gives $c = 57$ — divisible by $3$. Answer: $\textbf{(E) }$II and III only.