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"
(→‎Solution 5 (Rigorous))
 
(13 intermediate revisions by 7 users not shown)
Line 12: Line 12:
  
 
<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>
 
<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>
−
==Video Solution by MegaMath==
 
−
 
−
https://www.youtube.com/watch?v=le0KSx3Cy-g&t=28s
 
−
 
 
== Solution 1 (Guess and check + Contrapositive)==
 
== Solution 1 (Guess and check + Contrapositive)==
 
We examine each of the conditions.  
 
We examine each of the conditions.  
  
−
The first condition is false. A simple counterexample is <math>a=3</math> and <math>b=5</math>. The corresponding value of <math>c</math> is <math>17\cdot15=255</math>. Clearly, <math>\gcd(3,14)=1</math> and <math>\gcd(5,15)=5</math>, so condition <math>I</math> would imply that <math>\gcd(c,210)=1.</math> However, <math>\gcd(255,210)</math> is clearly not <math>1</math> (they share a common factor of <math>15</math>). Obviously, condition <math>I</math> is false, so we can rule out choices <math>A,B,</math> and <math>C</math>.  
+
The first condition is false. A simple counterexample is <math>a=3</math> and <math>b=5</math>. The corresponding value of <math>c</math> is <math>115</math>. Since <math>\gcd(3,14)=1</math>, condition <math>I</math> would imply that <math>\gcd(c,210)=1.</math> However, <math>\gcd(115,210)</math> is clearly not <math>1</math> (they share a common factor of <math>5</math>). Condition <math>I</math> is false so that we can rule out choices <math>A,B,</math> and <math>C</math>.  
  
−
We are now deciding between the two answer choices <math>D</math> and <math>E</math>. What differs between them is the validity of condition <math>II</math>, so it suffices to simply check <math>II</math>.  
+
We now decide between the two answer choices <math>D</math> and <math>E</math>. What differs between them is the validity of condition <math>II</math>, so it suffices to check <math>II</math> simply.  
  
−
We look at statement <math>II</math>'s contrapositive to prove it. The contrapositive states that if <math>\gcd(a,14)\neq1</math> and <math>\gcd(b,15)\neq1</math>, then <math>\gcd(c,210)\neq1.</math> In other words, if <math>a</math> shares some common factor that is not <math>1</math> with <math>14</math> and <math>b</math> shares some common factor that is not <math>1</math> with <math>15</math>, then <math>c</math> also shares a common factor with <math>210</math>. Let's say that <math>a=a'\cdot n</math>, where <math>a'</math> is a factor of <math>14</math> not equal to <math>1</math>. (So <math>a'</math> is the common factor.)  
+
We look at statement <math>II</math>'s contrapositive to prove it. The contrapositive states that if <math>\gcd(a,14)\neq1</math> and <math>\gcd(b,15)\neq1</math>, then <math>\gcd(c,210)\neq1.</math> In other words, if <math>a</math> shares some common factor that is not <math>1</math> with <math>14</math> and <math>b</math> shares some common factor that is not <math>1</math> with <math>15</math>, then <math>c</math> also shares a common factor that is not <math>1</math> with <math>210</math>. Let's say that <math>a=a'\cdot n</math>, where <math>a'</math> is a factor of <math>14</math> not equal to <math>1</math>. (So <math>a'</math> is the common factor.)  
  
 
We can rewrite the given equation as <math>15a+14b=c\implies15(a'n)+14b=c.</math> We can express <math>14</math> as <math>a'\cdot n'</math>, for some positive integer <math>n'</math> (this <math>n'</math> can be <math>1</math>). We can factor <math>a'</math> out to get <math>a'(15n+14n')=c.</math>  
 
We can rewrite the given equation as <math>15a+14b=c\implies15(a'n)+14b=c.</math> We can express <math>14</math> as <math>a'\cdot n'</math>, for some positive integer <math>n'</math> (this <math>n'</math> can be <math>1</math>). We can factor <math>a'</math> out to get <math>a'(15n+14n')=c.</math>  
  
−
We know that all values in this equation are integers, so <math>c</math> must be divisible by <math>a'</math>. Since <math>a'</math> is a factor of <math>14</math>, <math>a'</math> must also be a factor of <math>210</math>, a multiple of <math>14</math>. Therefore, we know that <math>c</math> shares a common factor with <math>210</math> (which is <math>a'</math>), so <math>\gcd(c,210)\neq1</math>. This is what <math>II</math> states, so therefore <math>II</math> is true.  
+
Since all values in this equation are integers, <math>c</math> must be divisible by <math>a'</math>. Since <math>a'</math> is a factor of <math>14</math>, <math>a'</math> must also be a factor of <math>210</math>, a multiple of <math>14</math>. Therefore, we know that <math>c</math> shares a common factor with <math>210</math> (which is <math>a'</math>), so <math>\gcd(c,210)\neq1</math>. This is what <math>II</math> states, so therefore <math>II</math> is true.  
  
 
Thus, our answer is <math>\boxed{\textbf{(E) }\text{II and III only}}.</math>  
 
Thus, our answer is <math>\boxed{\textbf{(E) }\text{II and III only}}.</math>  
 
~Technodoggo
 
~Technodoggo
 +
~AVM2023 (Minor Edits - Fixes in the first paragraph and grammar edits)
  
 
==Solution 2==
 
==Solution 2==
Line 79: Line 76:
  
 
==Solution 3 (Answer Choices)==
 
==Solution 3 (Answer Choices)==
−
It can easily be shown that statement I is false (a counterexample would be <math>a=1, b=5, c=85</math>), 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 (or it's contrapositive, to be precise). Therefore the answer is  
+
It can easily be shown that statement I is false (a counterexample would be <math>a=1, b=5, c=85</math>), 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 (or its contrapositive, to be precise). Therefore the answer is  
 
<math>\boxed{\textbf{(E) II and III only}}.</math>
 
<math>\boxed{\textbf{(E) II and III only}}.</math>
  
Line 89: Line 86:
  
  
−
Now, we will focus on statement III. It's pretty easy to realize that if either <math>a</math> is relatively prime to <math>14</math> or <math>b</math> is relatively prime to <math>15</math>, it will always share factors with <math>210</math> because <math>c = 15a + 14b</math> (think <math>15 \cdot 14 + 14). Therefore, statement III must be true.  
+
Now, we will focus on statement III. It's pretty easy to realize that if either <math>a</math> isn't relatively prime to <math>14</math> or <math>b</math> isn't relatively prime to <math>15</math>, it will always share factors with <math>210</math> because <math>c = 15a + 14b</math> (think <math>15 \cdot 14 + 14</math>). Therefore, statement III must be true.  
  
  
−
Since statement III is a stricter case of statement II, the last two statements are true, hence choose </math>\boxed{\textbf{(E) II and III only}}.$
+
Since statement III is a stricter case of statement II, the last two statements are true, hence choose <math>\boxed{\textbf{(E) }\text{II and III only}}.</math>
  
 
~xHypotenuse
 
~xHypotenuse
  
 +
==Solution 5 (Rigorous)==
 +
 +
The condition in the problem is equivalent to
 +
\begin{align*}
 +
15 a + 14 b = c. \hspace{1cm}
 +
\end{align*}
 +
 +
From here we can use the properties of the greatest common divisor to get
 +
 +
<cmath>\gcd(c, 14)=\gcd(15a+14b, 14)=\gcd(15a, 14)=\gcd(a, 14)</cmath>
 +
 +
and
 +
 +
<cmath>\gcd(c, 15)=\gcd(15a+14b, 15)=\gcd(14b, 15)=\gcd(b, 15)</cmath>
 +
 +
From here it's not hard to get
 +
 +
<cmath>\gcd(c, 210)=\gcd(c, 15)*\gcd(c, 14)=\gcd(a, 14)*\gcd(b, 15)</cmath>
 +
 +
Hence <math>\gcd(c, 210)=1</math> is equivalent to <math>\gcd(a, 14)=1</math> and <math>\gcd(b, 15)=1</math>. This means the answer must be <math>\boxed{\textbf{(E) }\text{II and III only}}.</math>
 +
 +
~tsun26
  
 
==Video Solution==
 
==Video Solution==

Latest revision as of 06:20, 21 October 2024

The following problem is from both the 2023 AMC 10B #18 and 2023 AMC 12B #15, so both problems redirect to this page.

Problem

Suppose $a$, $b$, and $c$ are positive integers such that\[\frac{a}{14}+\frac{b}{15}=\frac{c}{210}.\]Which of the following statements are necessarily true?

I. If $\gcd(a,14)=1$ or $\gcd(b,15)=1$ or both, then $\gcd(c,210)=1$.

II. If $\gcd(c,210)=1$, then $\gcd(a,14)=1$ or $\gcd(b,15)=1$ or both.

III. $\gcd(c,210)=1$ if and only if $\gcd(a,14)=\gcd(b,15)=1$.

$\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}$

Solution 1 (Guess and check + Contrapositive)

We examine each of the conditions.

The first condition is false. A simple counterexample is $a=3$ and $b=5$. The corresponding value of $c$ is $115$. Since $\gcd(3,14)=1$, condition $I$ would imply that $\gcd(c,210)=1.$ However, $\gcd(115,210)$ is clearly not $1$ (they share a common factor of $5$). Condition $I$ is false so that we can rule out choices $A,B,$ and $C$.

We now decide between the two answer choices $D$ and $E$. What differs between them is the validity of condition $II$, so it suffices to check $II$ simply.

We look at statement $II$'s contrapositive to prove it. The contrapositive states that if $\gcd(a,14)\neq1$ and $\gcd(b,15)\neq1$, then $\gcd(c,210)\neq1.$ In other words, if $a$ shares some common factor that is not $1$ with $14$ and $b$ shares some common factor that is not $1$ with $15$, then $c$ also shares a common factor that is not $1$ with $210$. Let's say that $a=a'\cdot n$, where $a'$ is a factor of $14$ not equal to $1$. (So $a'$ is the common factor.)

We can rewrite the given equation as $15a+14b=c\implies15(a'n)+14b=c.$ We can express $14$ as $a'\cdot n'$, for some positive integer $n'$ (this $n'$ can be $1$). We can factor $a'$ out to get $a'(15n+14n')=c.$

Since all values in this equation are integers, $c$ must be divisible by $a'$. Since $a'$ is a factor of $14$, $a'$ must also be a factor of $210$, a multiple of $14$. Therefore, we know that $c$ shares a common factor with $210$ (which is $a'$), so $\gcd(c,210)\neq1$. This is what $II$ states, so therefore $II$ is true.

Thus, our answer is $\boxed{\textbf{(E) }\text{II and III only}}.$ ~Technodoggo ~AVM2023 (Minor Edits - Fixes in the first paragraph and grammar edits)

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 (Answer Choices)

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 (or its contrapositive, to be precise). Therefore the answer is $\boxed{\textbf{(E) II and III only}}.$

~SpencerD. ~edited by A_MatheMagician

Solution 4

First, we will show that statement I is false. A simple counterexample is $a=2$ and $b=2$. Then, $c$ is even, and it is not relatively prime with $210$.


Now, we will focus on statement III. It's pretty easy to realize that if either $a$ isn't relatively prime to $14$ or $b$ isn't relatively prime to $15$, it will always share factors with $210$ because $c = 15a + 14b$ (think $15 \cdot 14 + 14$). Therefore, statement III must be true.


Since statement III is a stricter case of statement II, the last two statements are true, hence choose $\boxed{\textbf{(E) }\text{II and III only}}.$

~xHypotenuse

Solution 5 (Rigorous)

The condition in the problem is equivalent to \begin{align*} 15 a + 14 b = c. \hspace{1cm} \end{align*}

From here we can use the properties of the greatest common divisor to get

\[\gcd(c, 14)=\gcd(15a+14b, 14)=\gcd(15a, 14)=\gcd(a, 14)\]

and

\[\gcd(c, 15)=\gcd(15a+14b, 15)=\gcd(14b, 15)=\gcd(b, 15)\]

From here it's not hard to get

\[\gcd(c, 210)=\gcd(c, 15)*\gcd(c, 14)=\gcd(a, 14)*\gcd(b, 15)\]

Hence $\gcd(c, 210)=1$ is equivalent to $\gcd(a, 14)=1$ and $\gcd(b, 15)=1$. This means the answer must be $\boxed{\textbf{(E) }\text{II and III only}}.$

~tsun26

Video Solution

https://youtu.be/pg1pyRa6C24?si=bOM1mQkWzkYZzfv_

~MathProblemSolvingSkills.com


Video Solution 2 by OmegaLearn

https://youtu.be/kky_f4JK7y8

Video Solution

https://youtu.be/HxP-1TrwDdM


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

See Also

2023 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 17 		Followed by
Problem 19
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions
2023 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Problem 16
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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