2023 AMC 12B Problem 15

Question

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.

\mathrm{I},

\mathrm{II},

and

\mathrm{III}

\mathrm{I}

only

\mathrm{I}

and

\mathrm{II}

only

\mathrm{III}

only

\mathrm{II}

and

\mathrm{III}

only

Answer: E

Concepts:greatest common divisor modular arithmetic logical deduction

Difficulty rating: 1800

Small hint:

Clearing denominators gives

c=15a+14b,

so

c\equiv a\pmod{14}

and

c\equiv -b\pmod{15}

Big hint:

Hence

2,7

divide

c

iff they divide

a,

and

3,5

divide

c

iff they divide

b

Solution:

Multiplying by

210

gives

c=15a+14b.

Since

15\equiv 1\pmod{14},

we get

c\equiv a\pmod{14},

so

\gcd(c,14)=1

iff

\gcd(a,14)=1.

Since

14\equiv -1\pmod{15},

we get

c\equiv -b\pmod{15},

so

\gcd(c,15)=1

iff

\gcd(b,15)=1.

As

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,

so

\gcd(c,210)\ne 1.

Only II and III are true.

Thus, the correct answer is E.

2023 AMC 12B Problem 15

Answer: E

Difficulty rating: 1800

Small hint:

Big hint:

Solution:

Problem 15 in other years