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 "1988 AIME Problems/Problem 9"
(→‎Solution 6 (A bit of brute force using basic knowledge.))
 
(13 intermediate revisions by 4 users not shown)
Line 2: Line 2:
 
Find the smallest positive integer whose [[perfect cube|cube]] ends in <math>888</math>.
 
Find the smallest positive integer whose [[perfect cube|cube]] ends in <math>888</math>.
  
−
== Solution ==
+
==Solution 1==
−
===Solution 1===
 
 
A little bit of checking tells us that the units digit must be 2. Now our cube must be in the form of <math>(10k + 2)^3</math>; using the [[binomial theorem]] gives us <math>1000k^3 + 600k^2 + 120k + 8</math>. Since we are looking for the tens digit, <math>\mod{100}</math> we get <math>20k + 8 \equiv 88 \pmod{100}</math>. This is true if the tens digit is either <math>4</math> or <math>9</math>. Casework:
 
A little bit of checking tells us that the units digit must be 2. Now our cube must be in the form of <math>(10k + 2)^3</math>; using the [[binomial theorem]] gives us <math>1000k^3 + 600k^2 + 120k + 8</math>. Since we are looking for the tens digit, <math>\mod{100}</math> we get <math>20k + 8 \equiv 88 \pmod{100}</math>. This is true if the tens digit is either <math>4</math> or <math>9</math>. Casework:
 
*<math>4</math>: Then our cube must be in the form of <math>(100k + 42)^3 \equiv 3(100k)(42)^2 + 42^3 \equiv 200k + 88 \pmod{1000}</math>. Hence the lowest possible value for the hundreds digit is <math>4</math>, and so <math>442</math> is a valid solution.  
 
*<math>4</math>: Then our cube must be in the form of <math>(100k + 42)^3 \equiv 3(100k)(42)^2 + 42^3 \equiv 200k + 88 \pmod{1000}</math>. Hence the lowest possible value for the hundreds digit is <math>4</math>, and so <math>442</math> is a valid solution.  
 
*<math>9</math>: Then our cube is <math>(100k + 92)^3 \equiv 3(100k)(92)^2 + 92^3 \equiv 200k + 688 \pmod{1000}</math>. The lowest possible value for the hundreds digit is <math>1</math>, and we get <math>192</math>. Hence, since <math>192 < 442</math>, the answer is <math>\fbox{192}</math>
 
*<math>9</math>: Then our cube is <math>(100k + 92)^3 \equiv 3(100k)(92)^2 + 92^3 \equiv 200k + 688 \pmod{1000}</math>. The lowest possible value for the hundreds digit is <math>1</math>, and we get <math>192</math>. Hence, since <math>192 < 442</math>, the answer is <math>\fbox{192}</math>
  
−
===Solution 2===
+
==Solution 2==
 
<math>n^3 \equiv 888 \pmod{1000} \implies n^3 \equiv 0 \pmod 8</math> and <math>n^3 \equiv 13 \pmod{125}</math>.
 
<math>n^3 \equiv 888 \pmod{1000} \implies n^3 \equiv 0 \pmod 8</math> and <math>n^3 \equiv 13 \pmod{125}</math>.
 
<math>n \equiv 2 \pmod 5</math> due to the last digit of <math>n^3</math>. Let <math>n = 5a + 2</math>. By expanding, <math>125a^3 + 150a^2 + 60a + 8 \equiv 13 \pmod{125} \implies 5a^2 + 12a \equiv 1 \pmod{25}</math>.  
 
<math>n \equiv 2 \pmod 5</math> due to the last digit of <math>n^3</math>. Let <math>n = 5a + 2</math>. By expanding, <math>125a^3 + 150a^2 + 60a + 8 \equiv 13 \pmod{125} \implies 5a^2 + 12a \equiv 1 \pmod{25}</math>.  
Line 16: Line 15:
 
Therefore, <math>n = 2 + 5(3+ 5(2+5a_2)) = 125a_2 + 67</math>. <math>n^3</math> must also be a multiple of <math>8</math>, so <math>n</math> must be even. <math>125a_2 + 67 \equiv 0 \pmod 2 \implies a_2 \equiv 1 \pmod 2</math>. Therefore, <math>a_2 = 2a_3 + 1</math>, where <math>a_3</math> is any non-negative integer. The number <math>n</math> has form <math>125(2a_3+1)+67 = 250a_3+192</math>. So the minimum <math>n = \boxed{192}</math>.
 
Therefore, <math>n = 2 + 5(3+ 5(2+5a_2)) = 125a_2 + 67</math>. <math>n^3</math> must also be a multiple of <math>8</math>, so <math>n</math> must be even. <math>125a_2 + 67 \equiv 0 \pmod 2 \implies a_2 \equiv 1 \pmod 2</math>. Therefore, <math>a_2 = 2a_3 + 1</math>, where <math>a_3</math> is any non-negative integer. The number <math>n</math> has form <math>125(2a_3+1)+67 = 250a_3+192</math>. So the minimum <math>n = \boxed{192}</math>.
  
−
=== Solution 3 ===
+
== Solution 3 ==
 
Let <math>x^3 = 1000a + 888</math>. We factor an <math>8</math> out of the right hand side, and we note that <math>x</math> must be of the form <math>x = 2y</math>, where <math>y</math> is a positive integer. Then, this becomes <math>y^3 = 125a + 111</math>. Taking mod <math>5</math>, <math>25</math>, and <math>125</math>, we get <math>y^3 \equiv 1\pmod 5</math>, <math>y^3 \equiv 11\pmod{25}</math>, and <math>y^3 \equiv 111\pmod{125}</math>.  
 
Let <math>x^3 = 1000a + 888</math>. We factor an <math>8</math> out of the right hand side, and we note that <math>x</math> must be of the form <math>x = 2y</math>, where <math>y</math> is a positive integer. Then, this becomes <math>y^3 = 125a + 111</math>. Taking mod <math>5</math>, <math>25</math>, and <math>125</math>, we get <math>y^3 \equiv 1\pmod 5</math>, <math>y^3 \equiv 11\pmod{25}</math>, and <math>y^3 \equiv 111\pmod{125}</math>.  
  
 
We can work our way up, and find that <math>y\equiv 1\pmod 5</math>, <math>y\equiv 21\pmod{25}</math>, and finally <math>y\equiv 96\pmod{125}</math>. This gives us our smallest value, <math>y = 96</math>, so <math>x = \boxed{192}</math>, as desired. - Spacesam
 
We can work our way up, and find that <math>y\equiv 1\pmod 5</math>, <math>y\equiv 21\pmod{25}</math>, and finally <math>y\equiv 96\pmod{125}</math>. This gives us our smallest value, <math>y = 96</math>, so <math>x = \boxed{192}</math>, as desired. - Spacesam
  
−
=== Solution 4 (Bash) ===
+
== Solution 4 (Bash) ==
  
 
Let this integer be <math>x.</math> Note that <cmath>x^3 \equiv 888 \pmod{1000} \implies x \equiv 0 \pmod {2}~~ \cap ~~ x \equiv 2 \pmod{5}.</cmath> We wish to find the residue of <math>x</math> mod <math>125.</math> Note that <cmath>x \equiv 2,7,12,17, \text{ or } 22 \pmod{25}</cmath> using our congruence in mod <math>5.</math> The residue that works must also satisfy <math>x^3 \equiv 13 \pmod{25}</math> from our original congruence. Noting that <math>17^3 \equiv (-8)^3 \equiv -512 \equiv 13 \pmod{25}</math> (and bashing out the other residues perhaps but they're not that hard), we find that <cmath>x \equiv 17 \pmod{25}.</cmath> Thus, <cmath>x \equiv 17,42,67,92,117 \pmod{125}.</cmath> The residue that works must also satisfy <math>x^3 \equiv 13 \pmod{125}</math> from our original congruence. It is easy to memorize that <cmath>17^3 \equiv \mathbf{4913} \equiv 38 \pmod{125}.</cmath> Also, <cmath>42^3 \equiv 42^2 \cdot 42 \equiv 1764 \cdot 42 \equiv 14 \cdot 42 \equiv 88 \pmod{125}.</cmath> Finally, <cmath>67^3 \equiv 67^2 \cdot 67 \equiv 4489 \cdot 67 \equiv (-11) \cdot 67 \equiv -737 \equiv 13 \pmod{125},</cmath> as desired. Thus, <math>x</math> must satisfy <cmath>x \equiv 0 \pmod{2}~~ \cap ~~x \equiv 67 \pmod{125} \implies x \equiv 192 \pmod{250} \implies x=\boxed{192}.</cmath> ~samrocksnature
 
Let this integer be <math>x.</math> Note that <cmath>x^3 \equiv 888 \pmod{1000} \implies x \equiv 0 \pmod {2}~~ \cap ~~ x \equiv 2 \pmod{5}.</cmath> We wish to find the residue of <math>x</math> mod <math>125.</math> Note that <cmath>x \equiv 2,7,12,17, \text{ or } 22 \pmod{25}</cmath> using our congruence in mod <math>5.</math> The residue that works must also satisfy <math>x^3 \equiv 13 \pmod{25}</math> from our original congruence. Noting that <math>17^3 \equiv (-8)^3 \equiv -512 \equiv 13 \pmod{25}</math> (and bashing out the other residues perhaps but they're not that hard), we find that <cmath>x \equiv 17 \pmod{25}.</cmath> Thus, <cmath>x \equiv 17,42,67,92,117 \pmod{125}.</cmath> The residue that works must also satisfy <math>x^3 \equiv 13 \pmod{125}</math> from our original congruence. It is easy to memorize that <cmath>17^3 \equiv \mathbf{4913} \equiv 38 \pmod{125}.</cmath> Also, <cmath>42^3 \equiv 42^2 \cdot 42 \equiv 1764 \cdot 42 \equiv 14 \cdot 42 \equiv 88 \pmod{125}.</cmath> Finally, <cmath>67^3 \equiv 67^2 \cdot 67 \equiv 4489 \cdot 67 \equiv (-11) \cdot 67 \equiv -737 \equiv 13 \pmod{125},</cmath> as desired. Thus, <math>x</math> must satisfy <cmath>x \equiv 0 \pmod{2}~~ \cap ~~x \equiv 67 \pmod{125} \implies x \equiv 192 \pmod{250} \implies x=\boxed{192}.</cmath> ~samrocksnature
Line 27: Line 26:
  
 
==solution 5==
 
==solution 5==
−
This number is in the form of <math>10k+2</math>, after binomial expansion, we only want <math>600k^2+120k\equiv 880( \mod 1000 )</math>. We realize that <math>600,120</math> are both multiples of <math>8</math>, we only need that <math>600k^2+120k \equiv 5(\mod 125 )</math>, so we write <math>600k^2+120k=125x+5; 120k^2+24k=25x+1, 24(5k^2+k)=25x+1, 5k^2+k\equiv -1(\mod 25)</math>
+
This number is in the form of <math>10k+2</math>, after binomial expansion, we only want <math>600k^2+120k\equiv 880 \pmod{1000}</math>. We realize that <math>600,120</math> are both multiples of <math>8</math>, we only need that <math>600k^2+120k \equiv 5\pmod{125}</math>, so we write <math>600k^2+120k=125x+5; 120k^2+24k=25x+1, 24(5k^2+k)=25x+1, 5k^2+k\equiv -1\pmod{25}</math>
  
−
Then, we write <math>5k^2+k=25m-1, 5k^2+k+1=25m</math> so <math>k+1</math> must be a multiple of <math>5</math> at least, so <math>k\equiv -1, -6, -11, -16, -21 \(\mod 25)</math> after checking, when <math>k=-6. 5k^2+k+1=175=25\cdot 7</math>. So <math>k\equiv -6 (\mod 25)</math>, smallest <math>k=19</math>, the number is <math>\boxed{192}</math>
+
Then, we write <math>5k^2+k=25m-1, 5k^2+k+1=25m</math> so <math>k+1</math> must be a multiple of <math>5</math> at least, so <math>k\equiv {-1, -6, -11, -16, -21} \pmod {25}</math> after checking, when <math>k=-6, 5k^2+k+1=175=25\cdot 7</math>. So <math>k\equiv -6 \pmod{25}</math>, smallest <math>k=19</math>, the number is <math>\boxed{192}</math>
  
 
~bluesoul
 
~bluesoul
 +
 +
==Solution 6 (A bit of brute force using basic knowledge.)==
 +
 +
We do know the unit digit has to be 2, So lets consider the number of the form of <math>x2</math>.
 +
 +
On cubing <math>x2</math>, we get a number of the form <math>x^3 \,6x^2 \,12x \,8</math> where the unit digit of <math>12x</math> must be 8, therefore x can be 4 or 9. But for this value of <math>x</math> the hundreds digit won't be 8.
 +
 +
Thus our number must be of the form <math>x42</math> / <math>x92</math>. Repeating the above process we get values of <math>x</math> as 4 and 1 respectively.
 +
 +
Therefore the smallest number is 192.~ Dubey619
  
 
== See also ==
 
== See also ==

Latest revision as of 07:15, 2 February 2023

Problem

Find the smallest positive integer whose cube ends in $888$.

Solution 1

A little bit of checking tells us that the units digit must be 2. Now our cube must be in the form of $(10k + 2)^3$; using the binomial theorem gives us $1000k^3 + 600k^2 + 120k + 8$. Since we are looking for the tens digit, $\mod{100}$ we get $20k + 8 \equiv 88 \pmod{100}$. This is true if the tens digit is either $4$ or $9$. Casework:

  • $4$: Then our cube must be in the form of $(100k + 42)^3 \equiv 3(100k)(42)^2 + 42^3 \equiv 200k + 88 \pmod{1000}$. Hence the lowest possible value for the hundreds digit is $4$, and so $442$ is a valid solution.
  • $9$: Then our cube is $(100k + 92)^3 \equiv 3(100k)(92)^2 + 92^3 \equiv 200k + 688 \pmod{1000}$. The lowest possible value for the hundreds digit is $1$, and we get $192$. Hence, since $192 < 442$, the answer is $\fbox{192}$

Solution 2

$n^3 \equiv 888 \pmod{1000} \implies n^3 \equiv 0 \pmod 8$ and $n^3 \equiv 13 \pmod{125}$. $n \equiv 2 \pmod 5$ due to the last digit of $n^3$. Let $n = 5a + 2$. By expanding, $125a^3 + 150a^2 + 60a + 8 \equiv 13 \pmod{125} \implies 5a^2 + 12a \equiv 1 \pmod{25}$.

By looking at the last digit again, we see $a \equiv 3 \pmod5$, so we let $a = 5a_1 + 3$ where $a_1 \in \mathbb{Z^+}$. Plugging this in to $5a^2 + 12a \equiv 1 \pmod{25}$ gives $10a_1 + 6 \equiv 1 \pmod{25}$. Obviously, $a_1 \equiv 2 \pmod 5$, so we let $a_1 = 5a_2 + 2$ where $a_2$ can be any non-negative integer.

Therefore, $n = 2 + 5(3+ 5(2+5a_2)) = 125a_2 + 67$. $n^3$ must also be a multiple of $8$, so $n$ must be even. $125a_2 + 67 \equiv 0 \pmod 2 \implies a_2 \equiv 1 \pmod 2$. Therefore, $a_2 = 2a_3 + 1$, where $a_3$ is any non-negative integer. The number $n$ has form $125(2a_3+1)+67 = 250a_3+192$. So the minimum $n = \boxed{192}$.

Solution 3

Let $x^3 = 1000a + 888$. We factor an $8$ out of the right hand side, and we note that $x$ must be of the form $x = 2y$, where $y$ is a positive integer. Then, this becomes $y^3 = 125a + 111$. Taking mod $5$, $25$, and $125$, we get $y^3 \equiv 1\pmod 5$, $y^3 \equiv 11\pmod{25}$, and $y^3 \equiv 111\pmod{125}$.

We can work our way up, and find that $y\equiv 1\pmod 5$, $y\equiv 21\pmod{25}$, and finally $y\equiv 96\pmod{125}$. This gives us our smallest value, $y = 96$, so $x = \boxed{192}$, as desired. - Spacesam

Solution 4 (Bash)

Let this integer be $x.$ Note that \[x^3 \equiv 888 \pmod{1000} \implies x \equiv 0 \pmod {2}~~ \cap ~~ x \equiv 2 \pmod{5}.\] We wish to find the residue of $x$ mod $125.$ Note that \[x \equiv 2,7,12,17, \text{ or } 22 \pmod{25}\] using our congruence in mod $5.$ The residue that works must also satisfy $x^3 \equiv 13 \pmod{25}$ from our original congruence. Noting that $17^3 \equiv (-8)^3 \equiv -512 \equiv 13 \pmod{25}$ (and bashing out the other residues perhaps but they're not that hard), we find that \[x \equiv 17 \pmod{25}.\] Thus, \[x \equiv 17,42,67,92,117 \pmod{125}.\] The residue that works must also satisfy $x^3 \equiv 13 \pmod{125}$ from our original congruence. It is easy to memorize that \[17^3 \equiv \mathbf{4913} \equiv 38 \pmod{125}.\] Also, \[42^3 \equiv 42^2 \cdot 42 \equiv 1764 \cdot 42 \equiv 14 \cdot 42 \equiv 88 \pmod{125}.\] Finally, \[67^3 \equiv 67^2 \cdot 67 \equiv 4489 \cdot 67 \equiv (-11) \cdot 67 \equiv -737 \equiv 13 \pmod{125},\] as desired. Thus, $x$ must satisfy \[x \equiv 0 \pmod{2}~~ \cap ~~x \equiv 67 \pmod{125} \implies x \equiv 192 \pmod{250} \implies x=\boxed{192}.\] ~samrocksnature


solution 5

This number is in the form of $10k+2$, after binomial expansion, we only want $600k^2+120k\equiv 880 \pmod{1000}$. We realize that $600,120$ are both multiples of $8$, we only need that $600k^2+120k \equiv 5\pmod{125}$, so we write $600k^2+120k=125x+5; 120k^2+24k=25x+1, 24(5k^2+k)=25x+1, 5k^2+k\equiv -1\pmod{25}$

Then, we write $5k^2+k=25m-1, 5k^2+k+1=25m$ so $k+1$ must be a multiple of $5$ at least, so $k\equiv {-1, -6, -11, -16, -21} \pmod {25}$ after checking, when $k=-6, 5k^2+k+1=175=25\cdot 7$. So $k\equiv -6 \pmod{25}$, smallest $k=19$, the number is $\boxed{192}$

~bluesoul

Solution 6 (A bit of brute force using basic knowledge.)

We do know the unit digit has to be 2, So lets consider the number of the form of $x2$.

On cubing $x2$, we get a number of the form $x^3 \,6x^2 \,12x \,8$ where the unit digit of $12x$ must be 8, therefore x can be 4 or 9. But for this value of $x$ the hundreds digit won't be 8.

Thus our number must be of the form $x42$ / $x92$. Repeating the above process we get values of $x$ as 4 and 1 respectively.

Therefore the smallest number is 192.~ Dubey619

See also

1988 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 8 		Followed by
Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME 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=1988_AIME_Problems/Problem_9&oldid=188510"