Difference between revisions of "2023 AMC 10B Problems/Problem 18"
| Line 12: | Line 12: | ||
III. gcd(𝑐, 210) = 1 if and only if gcd(𝑎, 14) = gcd(𝑏, 15) = 1. | III. gcd(𝑐, 210) = 1 if and only if gcd(𝑎, 14) = gcd(𝑏, 15) = 1. | ||
| − | == Solution (Guess and check + Contrapositive)== | + | == Solution 1 (Guess and check + Contrapositive)== |
<math>I.</math> Try <math>a=3,b=5 => c = 17\cdot15</math> which makes <math>\textbf{I}</math> false. | <math>I.</math> Try <math>a=3,b=5 => c = 17\cdot15</math> which makes <math>\textbf{I}</math> false. | ||
At this point, we can rule out answer A,B,C. | At this point, we can rule out answer A,B,C. | ||
| Line 25: | Line 25: | ||
~Technodoggo | ~Technodoggo | ||
| − | ==Solution== | + | ==Solution 2== |
The equation given in the problem can be written as | The equation given in the problem can be written as | ||
| Line 34: | Line 34: | ||
</cmath> | </cmath> | ||
| − | \textbf{First, we prove that Statement I is not correct.} | + | <math>\textbf{First, we prove that Statement I is not correct.}</math> |
A counter example is <math>a = 1</math> and <math>b = 3</math>. | A counter example is <math>a = 1</math> and <math>b = 3</math>. | ||
Thus, <math>{\rm gcd} (c, 210) = 3 \neq 1</math>. | Thus, <math>{\rm gcd} (c, 210) = 3 \neq 1</math>. | ||
| − | \textbf{Second, we prove that Statement III is correct.} | + | <math>\textbf{Second, we prove that Statement III is correct.}</math> |
First, we prove the ``if'' part. | First, we prove the ``if'' part. | ||
| Line 62: | Line 62: | ||
Analogously, we can prove that <math>{\rm gcd}(b , 15) > 1</math>. | Analogously, we can prove that <math>{\rm gcd}(b , 15) > 1</math>. | ||
| − | \textbf{Third, we prove that Statement II is correct.} | + | <math>\textbf{Third, we prove that Statement II is correct.}</math> |
This is simply a special case of the ``only if'' part of Statement III. So we omit the proof. | This is simply a special case of the ``only if'' part of Statement III. So we omit the proof. | ||
All analysis above imply | All analysis above imply | ||
| − | \boxed{\textbf{(E) II and III only}}. | + | <math>\boxed{\textbf{(E) II and III only}}.</math> |
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ||
Revision as of 18:24, 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)
Try 
which makes 
false.
At this point, we can rule out answer A,B,C.
A => B or C. equiv. ~B AND ~C => ~A.
Let a = 14, b=15 (statisfying ~B and ~C). => C = 2*210. which is ~A.
is true.
So the answer is E.
~Technodoggo
Solution 2
The equation given in the problem can be written as
![\[ 15 a + 14 b = c. \hspace{1cm} (1) \]](http://latex.artofproblemsolving.com/f/f/d/ffdcb0a1fc94edc33f2dbdc03114c7946577d48b.png)
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)
