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)
Line 70: Line 70:
  
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 +
 +
==Solution 3==
 +
It can easily be shown that statement I is false (a counterexample would be a=1, b=5, c=85), meaning the only viable answer choices are D and E. Since both of these answer choices include statement III, this means III is true. Since III is true, this actually implies that statement II is true, as III is just a stronger version of statement II. Therefore the answer is <math>\boxed{\textbf{(E) II and III only}}.</math>

Revision as of 19:22, 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)

Solution 3

It can easily be shown that statement I is false (a counterexample would be a=1, b=5, c=85), meaning the only viable answer choices are D and E. Since both of these answer choices include statement III, this means III is true. Since III is true, this actually implies that statement II is true, as III is just a stronger version of statement II. Therefore the answer is $\boxed{\textbf{(E) II and III only}}.$

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