|
|
| (3 intermediate revisions by 3 users not shown) |
| Line 1: |
Line 1: |
| − | == Problem ==
| + | #redirect[[2023 AMC 12B Problems/Problem 15]] |
| − | | |
| − | Suppose 𝑎, 𝑏, and 𝑐 are positive integers such that
| |
| − | <math>\dfrac{a}{14}+\dfrac{b}{15}=\dfrac{c}{210}</math>.
| |
| − | | |
| − | 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 (Guess and check + Contrapositive)==
| |
| − | <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.
| |
| − | | |
| − | <math>II.</math> A => B or C. equiv. ~B AND ~C => ~A.
| |
| − | Let a = 14, b=15 (statisfying ~B and ~C). => C = 2*210. which is ~A.
| |
| − | | |
| − | <math>II</math> is true.
| |
| − | | |
| − | So the answer is E.
| |
| − | <math>\boxed{\textbf{(E) } II \text{ and } III \text{only}.}</math>
| |
| − | ~Technodoggo
| |
| − | | |
| − | ==Solution==
| |
| − | | |
| − | The equation given in the problem can be written as
| |
| − | <cmath>
| |
| − | \[
| |
| − | 15 a + 14 b = c. \hspace{1cm} (1)
| |
| − | \]
| |
| − | </cmath>
| |
| − | | |
| − | \textbf{First, we prove that Statement I is not correct.}
| |
| − | | |
| − | A counter example is <math>a = 1</math> and <math>b = 3</math>.
| |
| − | Thus, <math>{\rm gcd} (c, 210) = 3 \neq 1</math>.
| |
| − | | |
| − | \textbf{Second, we prove that Statement III is correct.}
| |
| − | | |
| − | First, we prove the ``if'' part.
| |
| − | | |
| − | Suppose <math>{\rm gcd}(a , 14) = 1</math> and <math>{\rm gcd}(b, 15) = 1</math>. However, <math>{\rm gcd} (c, 210) \neq 1</math>.
| |
| − | | |
| − | Thus, <math>c</math> must be divisible by at least one factor of 210. W.L.O.G, we assume <math>c</math> is divisible by 2.
| |
| − | | |
| − | Modulo 2 on Equation (1), we get that <math>2 | a</math>.
| |
| − | This is a contradiction with the condition that <math>{\rm gcd}(a , 14) = 1</math>.
| |
| − | Therefore, the ``if'' part in Statement III is correct.
| |
| − | | |
| − | Second, we prove the ``only if'' part.
| |
| − | | |
| − | Suppose <math>{\rm gcd} (c, 210) \neq 1</math>. Because <math>210 = 14 \cdot 15</math>, there must be one factor of 14 or 15 that divides <math>c</math>.
| |
| − | W.L.O.G, we assume there is a factor <math>q > 1</math> of 14 that divides <math>c</math>.
| |
| − | Because <math>{\rm gcd} (14, 15) = 1</math>, we have <math>{\rm gcd} (q, 15) = 1</math>.
| |
| − | Modulo <math>q</math> on Equation (1), we have <math>q | a</math>.
| |
| − | | |
| − | Because <math>q | 14</math>, we have <math>{\rm gcd}(a , 14) \geq q > 1</math>.
| |
| − | | |
| − | Analogously, we can prove that <math>{\rm gcd}(b , 15) > 1</math>.
| |
| − | | |
| − | \textbf{Third, we prove that Statement II is correct.}
| |
| − | | |
| − | This is simply a special case of the ``only if'' part of Statement III. So we omit the proof.
| |
| − | | |
| − | All analysis above imply
| |
| − | \boxed{\textbf{(E) II and III only}}.
| |
| − | | |
| − | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
| |
