2023 AMC 12B Problem 15

Problem 15 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

Multiplying by

210

gives

c=15a+14b.

Since

15\equiv 1\pmod{14},

we get

c\equiv a\pmod{14},

\gcd(c,14)=1

iff

\gcd(a,14)=1.

Since

14\equiv -1\pmod{15},

we get

c\equiv -b\pmod{15},

\gcd(c,15)=1

iff

\gcd(b,15)=1.

210=14\cdot 15

with

\gcd(14,15)=1,

statement III follows:

\gcd(c,210)=1

iff both hold. Statement II is the forward implication of III, hence true. Statement I is false: if

\gcd(a,14)=1

but

\gcd(b,15)\ne 1,

then

\gcd(c,15)\ne 1,

\gcd(c,210)\ne 1.

Only II and III are true. Thus, the correct answer is E.