Difference between revisions of "2023 AMC 10B Problems/Problem 18"
Technodoggo (talk | contribs) |
m (→Problem) |
||
Line 1: | Line 1: | ||
− | == Problem == | + | ==Problem 18== |
Suppose 𝑎, 𝑏, and 𝑐 are positive integers such that | Suppose 𝑎, 𝑏, and 𝑐 are positive integers such that | ||
Line 6: | Line 6: | ||
Which of the following statements are necessarily true? | Which of the following statements are necessarily true? | ||
− | I. If gcd( | + | I. If <math>\gcd(a,14)=1</math> or <math>\gcd(b,15)=1</math> or both, then <math>\gcd(c,210)=1</math>. |
− | II. If gcd( | + | II. If <math>\gcd(c,210)=1</math>, then <math>\gcd(a,14)=1</math> or <math>\gcd(b,15)=1</math> or both. |
− | III. gcd( | + | III. <math>\gcd(c,210)=1</math> if and only if <math>\gcd(a,14)=\gcd(b,15)=1</math>. |
== Solution 1 (Guess and check + Contrapositive)== | == Solution 1 (Guess and check + Contrapositive)== |
Revision as of 19:45, 15 November 2023
Problem 18
Suppose 𝑎, 𝑏, and 𝑐 are positive integers such that
.
Which of the following statements are necessarily true?
I. If or
or both, then
.
II. If , then
or
or both.
III. if and only if
.
Solution 1 (Guess and check + Contrapositive)
being revised ~Technodoggo
Solution 2
The equation given in the problem can be written as
A counter example is and
.
Thus,
.
First, we prove the ``if part.
Suppose and
. However,
.
Thus, must be divisible by at least one factor of 210. W.L.O.G, we assume
is divisible by 2.
Modulo 2 on Equation (1), we get that .
This is a contradiction with the condition that
.
Therefore, the ``if part in Statement III is correct.
Second, we prove the ``only if part.
Suppose . Because
, there must be one factor of 14 or 15 that divides
.
W.L.O.G, we assume there is a factor
of 14 that divides
.
Because
, we have
.
Modulo
on Equation (1), we have
.
Because , we have
.
Analogously, we can prove that .
This is simply a special case of the ``only if part of Statement III. So we omit the proof.
All analysis above imply
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)