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 "2018 AMC 10B Problems/Problem 21"
(→‎Solution 5 (Answer Choices))
 
(33 intermediate revisions by 8 users not shown)
Line 2: Line 2:
  
 
==Problem==
 
==Problem==
−
Mary chose an even <math>4</math>-digit number <math>n</math>. She wrote down all the divisors of <math>n</math> in increasing order from left to right: <math>1,2,...,\dfrac{n}{2},n</math>. At some moment Mary wrote <math>323</math> as a divisor of <math>n</math>. What is the smallest possible value of the next divisor written to the right of <math>323</math>?
+
Mary chose an even <math>4</math>-digit number <math>n</math>. She wrote down all the divisors of <math>n</math> in increasing order from left to right: <math>1,2,\ldots,\dfrac{n}{2},n</math>. At some moment Mary wrote <math>323</math> as a divisor of <math>n</math>. What is the smallest possible value of the next divisor written to the right of <math>323</math>?
  
 
<math>\textbf{(A) } 324 \qquad \textbf{(B) } 330 \qquad \textbf{(C) } 340 \qquad \textbf{(D) } 361 \qquad \textbf{(E) } 646</math>
 
<math>\textbf{(A) } 324 \qquad \textbf{(B) } 330 \qquad \textbf{(C) } 340 \qquad \textbf{(D) } 361 \qquad \textbf{(E) } 646</math>
  
−
==Solution 1==
+
==Solution 1 (Inequalities)==
  
−
Since prime factorizing <math>323</math> gives you <math>17 \cdot 19</math>, the desired answer needs to be a multiple of <math>17</math> or <math>19</math>, this is because if it is not a multiple of <math>17</math> or <math>19</math>, <math>n</math> will be more than a <math>4</math> digit number. For example, if the answer were to instead be <math>324</math>, <math>n</math> would have to be a multiple of <math>2^2 * 3^4 * 17 * 19</math> for both <math>323</math> and <math>324</math> to be a valid factor, meaning <math>n</math> would have to be at least <math>104652</math>, which is too big. Looking at the answer choices, <math>\text{(A) }324</math> and <math>\text{(B) }330</math> are both not a multiple of neither 17 nor 19, <math>\text{(C) }340</math> is divisible by <math>17</math>. <math>\text{(D) }361</math> is divisible by <math>19</math>, and <math>\text{(E) }646</math> is divisible by both <math>17</math> and <math>19</math>. Since <math>\boxed{\text{(C) }340}</math> is the smallest number divisible by either <math>17</math> or <math>19</math> it is the answer. Checking, we can see that <math>n</math> would be <math>6460</math>, a four-digit number. Note that <math>n</math> is also divisible by <math>2</math>, one of the listed divisors of <math>n</math>. (If <math>n</math> was not divisible by <math>2</math>, we would need to look for a different divisor)
+
Let <math>d</math> be the next divisor written to the right of <math>323.</math>
 +
 
 +
If <math>\gcd(323,d)=1,</math> then <cmath>n\geq323d>323^2>100^2=10000,</cmath> which contradicts the precondition that <math>n</math> is a <math>4</math>-digit number.
 +
 
 +
It follows that <math>\gcd(323,d)>1.</math> Since <math>323=17\cdot19,</math> the smallest possible value of <math>d</math> is <math>17\cdot20=\boxed{\textbf{(C) } 340},</math> from which <cmath>n=\operatorname{lcm}(323,d)=17\cdot19\cdot20=6460.</cmath>
 +
~MRENTHUSIASM ~tdeng
 +
 
 +
==Solution 2 (Inequalities)==
 +
 
 +
Let <math>d</math> be the next divisor written to the right of <math>323.</math>
 +
 
 +
Since <math>n</math> is even and <math>323=17\cdot19,</math> we have <math>n=2\cdot17\cdot19\cdot k=646k</math> for some positive integer <math>k.</math> Moreover, since <math>1000\leq n\leq9998,</math> we get <math>2\leq k\leq15.</math> As <math>d>323,</math> it is clear that <math>d</math> must be divisible by <math>17</math> or <math>19</math> or both.
 +
 
 +
Therefore, the smallest possible value of <math>d</math> is <math>17\cdot20=\boxed{\textbf{(C) } 340},</math> from which <cmath>n=\operatorname{lcm}(323,d)=17\cdot19\cdot20=6460.</cmath>
 +
~MRENTHUSIASM ~bjhhar
 +
 
 +
==Solution 3 (Quick)==
 +
The prime factorization of <math>323</math> is <math>17 \cdot 19</math>. Our answer must be a multiple of either <math>17</math> or <math>19</math> or both. Since <math>17 < 19</math>, the next smallest divisor that is divisble by <math>17</math> would be <math>323 + 17 = \boxed{\textbf{(C) } 340}</math>
 +
 
 +
~[https://artofproblemsolving.com/wiki/index.php/User:South South]
 +
 
 +
==Solution 4 (Answer Choices)==
 +
 
 +
Since prime factorizing <math>323</math> gives you <math>17 \cdot 19</math>, the desired answer needs to be a multiple of <math>17</math> or <math>19</math>, this is because if it is not a multiple of <math>17</math> or <math>19</math>, <math>n</math> will be more than a <math>4</math> digit number. For example, if the answer were to instead be <math>324</math>, <math>n</math> would have to be a multiple of <math>2^2\cdot3^4\cdot17\cdot19</math> for both <math>323</math> and <math>324</math> to be a valid factor, meaning <math>n</math> would have to be at least <math>104652</math>, which is too big. Looking at the answer choices, <math>\textbf{(A)}</math> and <math>\textbf{(B)}</math> are both not a multiple of neither <math>17</math> nor <math>19</math>, <math>\textbf{(C)}</math> is divisible by <math>17</math>. <math>\textbf{(D)}</math> is divisible by <math>19</math>, and <math>\textbf{(E)}</math> is divisible by both <math>17</math> and <math>19</math>. Since <math>\boxed{\textbf{(C) } 340}</math> is the smallest number divisible by either <math>17</math> or <math>19</math> it is the answer. Checking, we can see that <math>n</math> would be <math>6460</math>, a <math>4</math>-digit number. Note that <math>n</math> is also divisible by <math>2</math>, one of the listed divisors of <math>n</math>. (If <math>n</math> was not divisible by <math>2</math>, we would need to look for a different divisor.)
  
 
-Edited by Mathandski
 
-Edited by Mathandski
  
−
==Solution 2==
+
==Solution 5 (Answer Choices)==
−
Let the next largest divisor be <math>k</math>. Suppose <math>\gcd(k,323)=1</math>. Then, as <math>323|n, k|n</math>, therefore, <math>323\cdot k|n.</math> However, because <math>k>323</math>, <math>323k>323\cdot 324>9999</math>. Therefore, <math>\gcd(k,323)>1</math>. Note that <math>323=17\cdot 19</math>. Therefore, the smallest the GCD can be is <math>17</math> and our answer is <math>323+17=\boxed{\text{(C) }340}</math>.
+
Note that <math>323</math> multiplied by any of the answer choices results in a <math>5</math> or <math>6</math>-digit <math>n</math>. So, we need a choice that shares a factor(s) with <math>323</math>, such that the factors we'll need to add to the prime factorization of <math>n</math> (in result to adding the chosen divisor) won't cause our number to multiply to more than <math>4</math> digits.
 +
The prime factorization of <math>323</math> is <math>17\cdot19</math>, and since we know <math>n</math> is even, our answer needs to be  
 +
 
 +
* even
 +
 
 +
* has a factor of <math>17</math> or <math>19</math>
 +
 
 +
We see <math>340</math> achieves this and is the smallest to do so (<math>646</math> being the other). So, we get <math>\boxed{\textbf{(C) } 340}</math>.
 +
 
 +
~OGBooger (Solution)
 +
 
 +
~Pearl2008 (Minor Edits)
 +
 
 +
==Solution 6 (Very Rigorous)==
 +
This is not the fastest solution, but if i saw this question on an Olympiad/AIME, where there are no answer choices, and my work counted, this is what i would do (for the purpose of this question, a=323, b=answer, c=the four digit number);
 +
 
 +
<math>\newline</math>
 +
Note that for any <math>a,b,c \in \mathbb{Z}^+</math>, if <math>a|c</math> and <math>b|c</math> then lcm<math>(a,b)|c</math> (this is because if something divides a or b, it must divide c, and thus the max of all of the prime factors, ie: lcm, divides c) since <math>a=323,b > a</math>, if <math>gcd(a,b)=1</math> then <math>lcm(a,b)=ab</math> and thus <math>ab|c \implies c>a^2 \implies c>100^2 \implies</math> c is not a four digit number.
 +
<math>\newline</math> thus, <math>gcd(a,b)\neq1</math>. This implies that either <math>17|b</math>, or <math>19|b</math>, or both.
 +
 
 +
<math>\newline</math> Case 1: <math>17|b</math>, <math>19\not|b</math>. We let <math>b=17b'</math>, and by Euclid's Lemma, <math>19\not|b'</math>. Then, <math>lcm(323,b)|c \implies 17(lcm(19,b'))|c</math>. Since we already established that, <math>19\not|b</math> (and since 19 is prime, if it does not divide a number it is coprime to that number), <math>17*19*b'|c \implies 323b'|c</math>. Since <math>b=17b'>19*17</math>, <math>b' \geq 20</math>. A quick check shows <math>b'=20, b=340</math> suffices.
 +
<math>\newline</math> Now, let us show that there are no such numbers less than 340.
 +
<math>\newline</math> Presume there exists such a number, <math>n \in \mathbb{Z}^+</math> is in the range <math>(323,340)</math>. By hypothesis, there is a <math>d>1</math> such that <math>d|323</math>, <math>d|n</math>. By properties of divisibility <math>d|n-323</math>. the maximum possible value of <math>n-323</math> is <math>17^-</math> (basically an arbitrary amount smaller than 17). But, since <math>d>1</math> and <math>d|323, d \in \{17,19,323\}</math>. Of which, the minimum value is d=17. but, <math>17>17^-</math> so there is no such d, and no such n.
 +
<math>\newline</math> Thus, our answer is just <math>\boxed{\textbf{(C) } 340}</math>.
 +
<math>\newline</math> ~Stereotypicalmathnerd
 +
 
 +
==Video Solution 1==
 +
 
 +
https://www.youtube.com/watch?v=qlHE_sAXiY8
 +
 
 +
https://www.youtube.com/watch?v=T94oxV8schA&ab_channel=Jay
 +
 
 +
~Coach J
  
−
==Solution 3==
+
==Video Solution 2==
−
Again, recognize <math>323=17 \cdot 19</math>. The 4-digit number is even, so its prime factorization must then be <math>17 \cdot 19 \cdot 2 \cdot n</math>. Also, <math>1000\leq 646n \leq 9998</math>, so <math>2 \leq n \leq 15</math>. Since <math>15 \cdot 2=30</math>, the prime factorization of the number after <math>323</math> needs to have either <math>17</math> or <math>19</math>. The next highest product after <math>17 \cdot 19</math> is <math>17 \cdot 2 \cdot 10 =340</math> or <math>19 \cdot 2  \cdot 9 =342</math> <math>\implies \boxed{\text{(C) }340}</math>.
 
  
 +
https://www.youtube.com/watch?v=KHaLXNAkDWE
  
−
You can also tell by inspection that <math>19\cdot18 > 20\cdot17</math>, because <math>19\cdot18</math> is closer to the side lengths of a square, which maximizes the product.
+
==Video Solution 3==
  
−
~bjhhar
+
https://www.youtube.com/watch?v=vc1FHO9YYKQ
  
−
==Videos==
+
~bunny1
−
https://youtu.be/gMSkM6PLDwk
 
  
 
==See Also==
 
==See Also==

Latest revision as of 19:27, 5 August 2025

The following problem is from both the 2018 AMC 12B #19 and 2018 AMC 10B #21, so both problems redirect to this page.

Problem

Mary chose an even $4$-digit number $n$. She wrote down all the divisors of $n$ in increasing order from left to right: $1,2,\ldots,\dfrac{n}{2},n$. At some moment Mary wrote $323$ as a divisor of $n$. What is the smallest possible value of the next divisor written to the right of $323$?

$\textbf{(A) } 324 \qquad \textbf{(B) } 330 \qquad \textbf{(C) } 340 \qquad \textbf{(D) } 361 \qquad \textbf{(E) } 646$

Solution 1 (Inequalities)

Let $d$ be the next divisor written to the right of $323.$

If $\gcd(323,d)=1,$ then \[n\geq323d>323^2>100^2=10000,\] which contradicts the precondition that $n$ is a $4$-digit number.

It follows that $\gcd(323,d)>1.$ Since $323=17\cdot19,$ the smallest possible value of $d$ is $17\cdot20=\boxed{\textbf{(C) } 340},$ from which \[n=\operatorname{lcm}(323,d)=17\cdot19\cdot20=6460.\] ~MRENTHUSIASM ~tdeng

Solution 2 (Inequalities)

Let $d$ be the next divisor written to the right of $323.$

Since $n$ is even and $323=17\cdot19,$ we have $n=2\cdot17\cdot19\cdot k=646k$ for some positive integer $k.$ Moreover, since $1000\leq n\leq9998,$ we get $2\leq k\leq15.$ As $d>323,$ it is clear that $d$ must be divisible by $17$ or $19$ or both.

Therefore, the smallest possible value of $d$ is $17\cdot20=\boxed{\textbf{(C) } 340},$ from which \[n=\operatorname{lcm}(323,d)=17\cdot19\cdot20=6460.\] ~MRENTHUSIASM ~bjhhar

Solution 3 (Quick)

The prime factorization of $323$ is $17 \cdot 19$. Our answer must be a multiple of either $17$ or $19$ or both. Since $17 < 19$, the next smallest divisor that is divisble by $17$ would be $323 + 17 = \boxed{\textbf{(C) } 340}$

~South

Solution 4 (Answer Choices)

Since prime factorizing $323$ gives you $17 \cdot 19$, the desired answer needs to be a multiple of $17$ or $19$, this is because if it is not a multiple of $17$ or $19$, $n$ will be more than a $4$ digit number. For example, if the answer were to instead be $324$, $n$ would have to be a multiple of $2^2\cdot3^4\cdot17\cdot19$ for both $323$ and $324$ to be a valid factor, meaning $n$ would have to be at least $104652$, which is too big. Looking at the answer choices, $\textbf{(A)}$ and $\textbf{(B)}$ are both not a multiple of neither $17$ nor $19$, $\textbf{(C)}$ is divisible by $17$. $\textbf{(D)}$ is divisible by $19$, and $\textbf{(E)}$ is divisible by both $17$ and $19$. Since $\boxed{\textbf{(C) } 340}$ is the smallest number divisible by either $17$ or $19$ it is the answer. Checking, we can see that $n$ would be $6460$, a $4$-digit number. Note that $n$ is also divisible by $2$, one of the listed divisors of $n$. (If $n$ was not divisible by $2$, we would need to look for a different divisor.)

-Edited by Mathandski

Solution 5 (Answer Choices)

Note that $323$ multiplied by any of the answer choices results in a $5$ or $6$-digit $n$. So, we need a choice that shares a factor(s) with $323$, such that the factors we'll need to add to the prime factorization of $n$ (in result to adding the chosen divisor) won't cause our number to multiply to more than $4$ digits. The prime factorization of $323$ is $17\cdot19$, and since we know $n$ is even, our answer needs to be

  • even
  • has a factor of $17$ or $19$

We see $340$ achieves this and is the smallest to do so ($646$ being the other). So, we get $\boxed{\textbf{(C) } 340}$.

~OGBooger (Solution)

~Pearl2008 (Minor Edits)

Solution 6 (Very Rigorous)

This is not the fastest solution, but if i saw this question on an Olympiad/AIME, where there are no answer choices, and my work counted, this is what i would do (for the purpose of this question, a=323, b=answer, c=the four digit number);

$\newline$ Note that for any $a,b,c \in \mathbb{Z}^+$, if $a|c$ and $b|c$ then lcm$(a,b)|c$ (this is because if something divides a or b, it must divide c, and thus the max of all of the prime factors, ie: lcm, divides c) since $a=323,b > a$, if $gcd(a,b)=1$ then $lcm(a,b)=ab$ and thus $ab|c \implies c>a^2 \implies c>100^2 \implies$ c is not a four digit number. $\newline$ thus, $gcd(a,b)\neq1$. This implies that either $17|b$, or $19|b$, or both.

$\newline$ Case 1: $17|b$, $19\not|b$. We let $b=17b'$, and by Euclid's Lemma, $19\not|b'$. Then, $lcm(323,b)|c \implies 17(lcm(19,b'))|c$. Since we already established that, $19\not|b$ (and since 19 is prime, if it does not divide a number it is coprime to that number), $17*19*b'|c \implies 323b'|c$. Since $b=17b'>19*17$, $b' \geq 20$. A quick check shows $b'=20, b=340$ suffices. $\newline$ Now, let us show that there are no such numbers less than 340. $\newline$ Presume there exists such a number, $n \in \mathbb{Z}^+$ is in the range $(323,340)$. By hypothesis, there is a $d>1$ such that $d|323$, $d|n$. By properties of divisibility $d|n-323$. the maximum possible value of $n-323$ is $17^-$ (basically an arbitrary amount smaller than 17). But, since $d>1$ and $d|323, d \in \{17,19,323\}$. Of which, the minimum value is d=17. but, $17>17^-$ so there is no such d, and no such n. $\newline$ Thus, our answer is just $\boxed{\textbf{(C) } 340}$. $\newline$ ~Stereotypicalmathnerd

Video Solution 1

https://www.youtube.com/watch?v=qlHE_sAXiY8

https://www.youtube.com/watch?v=T94oxV8schA&ab_channel=Jay

~Coach J

Video Solution 2

https://www.youtube.com/watch?v=KHaLXNAkDWE

Video Solution 3

https://www.youtube.com/watch?v=vc1FHO9YYKQ

~bunny1

See Also

2018 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 20 		Followed by
Problem 22
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
2018 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 18 		Followed by
Problem 20
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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_10B_Problems/Problem_21&oldid=256626"