2023 AMC 10B Problems/Problem 18

Problem

Suppose 𝑎, 𝑏, and 𝑐 are positive integers such that $\dfrac{a}{14}+\dfrac{b}{15}=\dfrac{c}{210}$ .

Which of the following statements are necessarily true?

I. If gcd(𝑎, 14) = 1 or gcd(𝑏, 15) = 1 or both, then gcd(𝑐, 210) = 1.

II. If gcd(𝑐, 210) = 1, then gcd(𝑎, 14) = 1 or gcd(𝑏, 15) = 1 or both.

III. gcd(𝑐, 210) = 1 if and only if gcd(𝑎, 14) = gcd(𝑏, 15) = 1.

Solution (Guess and check + Contrapositive)

$I.$ Try $a=3,b=5 => c = 17\cdot15$ which makes $\textbf{I}$ false. At this point, we can rule out answer A,B,C.

$II.$ A => B or C. equiv. ~B AND ~C => ~A. Let a = 14, b=15 (statisfying ~B and ~C). => C = 2*210. which is ~A.

$II$ is true.

So the answer is E. $\boxed{\textbf{(E) } II \text{ and } III \text{only}.}$ ~Technodoggo

Solution

The equation given in the problem can be written as $15 a + 14 b = c. \hspace{1cm} (1)$

\textbf{First, we prove that Statement I is not correct.}

A counter example is $a = 1$ and $b = 3$ . Thus, ${\rm gcd} (c, 210) = 3 \neq 1$ .

\textbf{Second, we prove that Statement III is correct.}

First, we prove the ``if part.

Suppose ${\rm gcd}(a , 14) = 1$ and ${\rm gcd}(b, 15) = 1$ . However, ${\rm gcd} (c, 210) \neq 1$ .

Thus, $c$ must be divisible by at least one factor of 210. W.L.O.G, we assume $c$ is divisible by 2.

Modulo 2 on Equation (1), we get that $2 | a$ . This is a contradiction with the condition that ${\rm gcd}(a , 14) = 1$ . Therefore, the ``if part in Statement III is correct.

Second, we prove the ``only if part.

Suppose ${\rm gcd} (c, 210) \neq 1$ . Because $210 = 14 \cdot 15$ , there must be one factor of 14 or 15 that divides $c$ . W.L.O.G, we assume there is a factor $q > 1$ of 14 that divides $c$ . Because ${\rm gcd} (14, 15) = 1$ , we have ${\rm gcd} (q, 15) = 1$ . Modulo $q$ on Equation (1), we have $q | a$ .