Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 AMC 12B Problems/Problem 15"

(→‎Problem)
(→‎Problem)
Line 1: Line 1:
−
==Problem==
+
== Problem ==
−
Suppose that <math>a,b,</math> and <math>c</math> are positive integers such that
+
 
−
<cmath>\frac{a}{14}+\frac{b}{15}=\frac{c}{210}</cmath>
+
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?
 
Which of the following statements are necessarily true?
  
−
<math>\textbf{(A) }\text{I, II, and III}\qquad\textbf{(B) }\text{I only}\qquad\textbf{(C) }\text{I and II only}\qquad\textbf{(D) }\text{III only}\qquad\textbf{(E) }\text{II and III only}</math>
+
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)==
 +
<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 2==
 +
 
 +
The equation given in the problem can be written as
 +
<cmath>
 +
\[
 +
15 a + 14 b = c. \hspace{1cm} (1)
 +
\]
 +
</cmath>
 +
 
 +
<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>.
 +
Thus, <math>{\rm gcd} (c, 210) = 3 \neq 1</math>.
 +
 
 +
<math>\textbf{Second, we prove that Statement III is correct.}</math>
 +
 
 +
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>.
 +
 
 +
<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.
 +
 
 +
All analyses above imply
 +
<math>\boxed{\textbf{(E) II and III only}}.</math>
 +
 
 +
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Revision as of 20:04, 15 November 2023

Problem

Suppose 𝑎, 𝑏, and 𝑐 are positive integers such that $\dfrac{a}{14}+\dfrac{b}{15}=\dfrac{c}{210}$.

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)

$I.$ Try $a=3,b=5 => c = 17\cdot15$ which makes $\textbf{I}$ false. At this point, we can rule out answer A,B,C.

$II.$ A => B or C. equiv. ~B AND ~C => ~A. Let a = 14, b=15 (statisfying ~B and ~C). => C = 2*210. which is ~A.

$II$ is true.

So the answer is E. $\boxed{\textbf{(E) } II \text{ and } III \text{only}.}$ ~Technodoggo

Solution 2

The equation given in the problem can be written as \[ 15 a + 14 b = c. \hspace{1cm} (1) \]

$\textbf{First, we prove that Statement I is not correct.}$

A counter example is $a = 1$ and $b = 3$. Thus, ${\rm gcd} (c, 210) = 3 \neq 1$.

$\textbf{Second, we prove that Statement III is correct.}$

First, we prove the ``if part.

Suppose ${\rm gcd}(a , 14) = 1$ and ${\rm gcd}(b, 15) = 1$. However, ${\rm gcd} (c, 210) \neq 1$.

Thus, $c$ must be divisible by at least one factor of 210. W.L.O.G, we assume $c$ is divisible by 2.

Modulo 2 on Equation (1), we get that $2 | a$. This is a contradiction with the condition that ${\rm gcd}(a , 14) = 1$. Therefore, the ``if part in Statement III is correct.

Second, we prove the ``only if part.

Suppose ${\rm gcd} (c, 210) \neq 1$. Because $210 = 14 \cdot 15$, there must be one factor of 14 or 15 that divides $c$. W.L.O.G, we assume there is a factor $q > 1$ of 14 that divides $c$. Because ${\rm gcd} (14, 15) = 1$, we have ${\rm gcd} (q, 15) = 1$. Modulo $q$ on Equation (1), we have $q | a$.

Because $q | 14$, we have ${\rm gcd}(a , 14) \geq q > 1$.

Analogously, we can prove that ${\rm gcd}(b , 15) > 1$.

$\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 analyses above imply $\boxed{\textbf{(E) II and III only}}.$

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AMC_12B_Problems/Problem_15&oldid=203486"