2023 AMC 10B Problem 18

Problem 18 of 25IntermediateNumber Theory

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

\gcd(b, 15) = 1

or both, then

\gcd(c, 210) = 1.

II. If

\gcd(c, 210) = 1,

then

\gcd(a, 14) = 1

\gcd(b, 15) = 1

or both. III.

\gcd(c, 210) = 1

if and only if

\gcd(a, 14) = \gcd(b, 15) = 1.

Show solution

Solution

Clear denominators to get

c = 15a + 14b.

Reduce modulo the primes of

210 = 2 \cdot 3 \cdot 5 \cdot 7:

c \equiv a \pmod 2,

c \equiv 2b \pmod 3,

c \equiv 4b \pmod 5,

and

c \equiv a \pmod 7.

\gcd(c, 210) = 1

iff

a

is divisible by neither

2

nor

7

and

b

is divisible by neither

3

nor

5,

which is exactly

\gcd(a, 14) = 1

and

\gcd(b, 15) = 1.

That settles III, and it makes II true since the “and” implies the “or.” Statement I fails, though: take

a = 1, b = 3.

Then

\gcd(a, 14) = 1,

yet

c = 57

is divisible by

3.

So only II and III hold. Therefore, the answer is E.