Difference between revisions of "2018 AMC 10A Problems/Problem 22"

Revision as of 12:41, 31 January 2021

Problem

Let $a, b, c,$ and $d$ be positive integers such that $\gcd(a, b)=24$ , $\gcd(b, c)=36$ , $\gcd(c, d)=54$ , and $70<\gcd(d, a)<100$ . Which of the following must be a divisor of $a$ ?

$\textbf{(A)} \text{ 5} \qquad \textbf{(B)} \text{ 7} \qquad \textbf{(C)} \text{ 11} \qquad \textbf{(D)} \text{ 13} \qquad \textbf{(E)} \text{ 17}$

Solution 1

The GCD information tells us that $24$ divides $a$ , both $24$ and $36$ divide $b$ , both $36$ and $54$ divide $c$ , and $54$ divides $d$ . Note that we have the prime factorizations: $\begin{align*} 24 &= 2^3\cdot 3,\\ 36 &= 2^2\cdot 3^2,\\ 54 &= 2\cdot 3^3. \end{align*}$

Hence we have $\begin{align*} a &= 2^3\cdot 3\cdot w\\ b &= 2^3\cdot 3^2\cdot x\\ c &= 2^2\cdot 3^3\cdot y\\ d &= 2\cdot 3^3\cdot z \end{align*}$ for some positive integers $w,x,y,z$ . Now if $3$ divides $w$ , then $\gcd(a,b)$ would be at least $2^3\cdot 3^2$ which is too large, hence $3$ does not divide $w$ . Similarly, if $2$ divides $z$ , then $\gcd(c,d)$ would be at least $2^2\cdot 3^3$ which is too large, so $2$ does not divide $z$ . Therefore, $\gcd(a,d)=2\cdot 3\cdot \gcd(w,z)$ where neither $2$ nor $3$ divide $\gcd(w,z)$ . In other words, $\gcd(w,z)$ is divisible only by primes that are at least $5$ . The only possible value of $\gcd(a,d)$ between $70$ and $100$ and which fits this criterion is $78=2\cdot3\cdot13$ , so the answer is $\boxed{\textbf{(D) }13}$ .

Solution 2

We can say that $a$ and $b$ 'have' $2^3 * 3$ , that $b$ and $c$ have $2^2 * 3^2$ , and that $c$ and $d$ have $3^3 * 2$ . Combining $1$ and $2$ yields $b$ has (at a minimum) $2^3 * 3^2$ , and thus $a$ has $2^3 * 3$ (and no more powers of $3$ because otherwise $gcd(a,b)$ would be different). In addition, $c$ has $3^3 * 2^2$ , and thus $d$ has $3^3 * 2$ (similar to $a$ , we see that $d$ cannot have any other powers of $2$ ). We now assume the simplest scenario, where $a = 2^3 * 3$ and $d = 3^3 * 2$ . According to this base case, we have $gcd(a, d) = 2 * 3 = 6$ . We want an extra factor between the two such that this number is between $70$ and $100$ , and this new factor cannot be divisible by $2$ or $3$ . Checking through, we see that $6 * 13$ is the only one that works. Therefore the answer is $\boxed{\textbf{(D) } 13}$

Solution by JohnHankock

Solution 2.1 (updated with better notation)

Do casework on $v_2$ and $v_3.$ Notice that we must have $v_3(a) = 1$ and $v_2(d)=1$ and the values of $b,d$ does not matter. Therefore, $\gcd(d,a) = 6k,$ where $k$ is not divisible by $2$ or $3.$ We see that $13$ is the only possible answer.

-Williamgolly

Solution 3 (Better notation)

First off, note that $24$ , $36$ , and $54$ are all of the form $2^x\times3^y$ . The prime factorizations are $2^3\times 3^1$ , $2^2\times 3^2$ and $2^1\times 3^3$ , respectively. Now, let $a_2$ and $a_3$ be the number of times $2$ and $3$ go into $a$ ,respectively. Define $b_2$ , $b_3$ , $c_2$ , and $c_3$ similiarly. Now, translate the $lcm$ s into the following: $\min(a_2,b_2)=3$ $\min(a_3,b_3)=1$ $\min(b_2,c_2)=2$ $\min(b_3,c_3)=2$ $\min(a_2,c_2)=1$ $\min(a_3,c_3)=3$ .

(Unfinished) ~Rowechen Zhong

Solution 4 (Fastest)

Notice that $gcd (a,b,c,d)=gcd(gcd(a,b),gcd(b,c),gcd(c,d))=gcd(24,36,54)=6$ , so $gcd(d,a)$ must be a multiple of $6$ . The only answer choice that gives a value between $70$ and $100$ when multiplied by 6 is $\boxed{\textbf{(D) } 13}$ . - mathleticguyyy + einstein

In the case where there can be 2 possible answers, we can do casework on gcd(d,a) ~Williamgolly

Video Solution by Richard Rusczyk

https://artofproblemsolving.com/videos/amc/2018amc10a/467

~ dolphin7

Video Solution

https://youtu.be/yjrqINsQP5c

~savannahsolver

Video Solution (Meta-Solving Technique)

https://youtu.be/GmUWIXXf_uk?t=1003

~ pi_is_3.14

@@ Line 31: / Line 31: @@
 Solution by JohnHankock
-== Solution 2.1 ==
+== Solution 2.1 (updated with better notation)==
-Elaborating on to what Solution 1 stated, we are not able to add any extra factor of 2 or 3 to <math>gcd(a, d)</math> because doing so would later the <math>gcd</math> of <math>(a, b)</math> and <math>(c, d)</math>. This is why:
+Do casework on <math>v_2</math> and <math>v_3.</math>  Notice that we must have <math>v_3(a) = 1</math> and <math>v_2(d)=1</math> and the values of <math>b,d</math> does not matter.  Therefore, <math>\gcd(d,a) = 6k,</math> where <math>k</math> is not divisible by <math>2</math> or <math>3.</math>  We see that <math>13</math> is the only possible answer.
-The <math>gcd(a, b)</math> is <math>2^3 * 3</math> and the <math>gcd</math> of <math>(c, d)</math> is <math>2 * 3^3</math>. However, the <math>gcd</math> of <math>(b, c) = 2^2 * 3^2</math> (meaning both are divisible by 36). Therefore, <math>a</math> is only divisible by <math>3^1</math> (and no higher power of 3), while <math>d</math> is divisible by only <math>2^1</math> (and no higher power of 2).
+-Williamgolly
-Thus, the <math>gcd</math> of <math>(a, d)</math> can be expressed in the form <math>2 * 3 * k</math> for which <math>k</math> is a number not divisible by <math>2</math> or <math>3</math>. The only answer choice that satisfies this (and the other condition) is <math>\boxed{\textbf{(D) } 13}</math>.
 ==Solution 3 (Better notation)==

2018 AMC 10A (Problems • Answer Key • Resources)
Preceded by Problem 21	Followed by Problem 23
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

Page

Toolbox

Search