Difference between revisions of "2023 AMC 10B Problems/Problem 18"
Technodoggo (talk | contribs) |
|||
Line 13: | Line 13: | ||
== Solution 1 (Guess and check + Contrapositive)== | == Solution 1 (Guess and check + Contrapositive)== | ||
− | + | [[being revised]] | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
~Technodoggo | ~Technodoggo | ||
Revision as of 19:06, 15 November 2023
Problem
Suppose 𝑎, 𝑏, and 𝑐 are positive integers such that .
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 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)