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 "1989 AIME Problems/Problem 9"

(→‎Problem: Centered the equation.)
m (→‎Solution 6)
 
(30 intermediate revisions by 5 users not shown)
Line 2: Line 2:
 
One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that <cmath>133^5+110^5+84^5+27^5=n^{5}.</cmath> Find the value of <math>n</math>.
 
One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that <cmath>133^5+110^5+84^5+27^5=n^{5}.</cmath> Find the value of <math>n</math>.
  
−
== Solution 1 ==
+
== Solution 1 (FLT, CRT, Inequalities) ==
−
Note that <math>n</math> is even, since the <math>LHS</math> consists of two odd and two even numbers. By [[Fermat's Little Theorem]], we know <math>{n^{5}}</math> is congruent to <math>n</math> [[modulo]] 5.  Hence,
+
Taking the given equation modulo <math>2,3,</math> and <math>5,</math> respectively, we have
−
<center><math>3 + 0 + 4 + 2 \equiv n\pmod{5}</math></center>
+
<cmath>\begin{align*}
−
<center><math>4 \equiv n\pmod{5}</math></center>
+
n^5&\equiv0\pmod{2}, \\
 +
n^5&\equiv0\pmod{3}, \\
 +
n^5&\equiv4\pmod{5}.
 +
\end{align*}</cmath>
 +
By either <b>Fermat's Little Theorem (FLT)</b> or inspection, we get
 +
<cmath>\begin{align*}
 +
n&\equiv0\pmod{2}, \\
 +
n&\equiv0\pmod{3}, \\
 +
n&\equiv4\pmod{5}.
 +
\end{align*}</cmath>
 +
By either the <b>Chinese Remainder Theorem (CRT)</b> or inspection, we get <math>n\equiv24\pmod{30}.</math>
  
−
Continuing, we examine the equation modulo 3,
+
It is clear that <math>n>133,</math> so the possible values for <math>n</math> are <math>144,174,204,\ldots.</math> Note that
−
<center><math>1 - 1 + 0 + 0 \equiv n\pmod{3}</math></center>
+
<cmath>\begin{align*}
−
<center><math>0 \equiv n\pmod{3}</math></center>
+
n^5&=133^5+110^5+84^5+27^5 \\
 +
&<133^5+110^5+(84+27)^5 \\
 +
&=133^5+110^5+111^5 \\
 +
&<3\cdot133^5,
 +
\end{align*}</cmath>
 +
from which <math>\left(\frac{n}{133}\right)^5<3.</math>
  
−
Thus, <math>n</math> is divisible by three and leaves a remainder of four when divided by 5.  It's obvious that <math>n>133</math>, so the only possibilities are <math>n = 144</math> or <math>n \geq 174</math>. It quickly becomes apparent that 174 is much too large, so <math>n</math> must be <math>\boxed{144}</math>.
+
If <math>n\geq174,</math> then
 +
<cmath>\begin{align*}
 +
\left(\frac{n}{133}\right)^5&>1.3^5 \\
 +
&=1.3^2\cdot1.3^2\cdot1.3 \\
 +
&>1.6\cdot1.6\cdot1.3 \\
 +
&=2.56\cdot1.3 \\
 +
&>2.5\cdot1.2 \\
 +
&=3,
 +
\end{align*}</cmath>
 +
which arrives at a contradiction. Therefore, we conclude that <math>n=\boxed{144}.</math>
 +
 
 +
~MRENTHUSIASM
  
 
== Solution 2 ==
 
== Solution 2 ==
−
We can cheat a little bit and approximate, since we are dealing with such large numbers. As above, <math>n^5\equiv n\pmod{5}</math>, and it is easy to see that <math>n^5\equiv n\pmod 2</math>. Therefore, <math>133^5+110^5+84^5+27^5\equiv 3+0+4+7\equiv 4\pmod{10}</math>, so the last digit of <math>n</math> is 4.
+
Note that <math>n</math> is even, since the LHS consists of two odd and two even numbers. By Fermat's Little Theorem, we know <math>n^5\equiv n\pmod{5}.</math> Hence, <cmath>n\equiv3+0+4+2\equiv4\pmod{5}.</cmath>
 +
Continuing, we examine the equation modulo <math>3,</math> <cmath>n\equiv1-1+0+0\equiv0\pmod{3}.</cmath>
 +
Thus, <math>n</math> is divisible by three and leaves a remainder of four when divided by <math>5.</math> It is obvious that <math>n>133,</math> so the only possibilities are <math>n = 144</math> or <math>n \geq 174.</math> It quickly becomes apparent that <math>174</math> is much too large, so <math>n</math> must be <math>\boxed{144}.</math>
 +
 
 +
~Azjps (Solution)
 +
 
 +
~MRENTHUSIASM (Reformatting)
 +
 
 +
== Solution 3 ==
 +
We can cheat a little bit and approximate, since we are dealing with such large numbers. As above, <math>n^5\equiv n\pmod{5},</math> and it is easy to see that <math>n^5\equiv n\pmod 2.</math> Therefore, <math>133^5+110^5+84^5+27^5\equiv 3+0+4+7\equiv 4\pmod{10},</math> so the last digit of <math>n</math> is <math>4.</math>
 +
 
 +
We notice that <math>133,110,84,</math> and <math>27</math> are all very close or equal to multiples of <math>27.</math> We can rewrite <math>n^5</math> as approximately equal to <math>27^5(5^5+4^5+3^5+1^5) = 27^5(4393).</math> This means <math>\frac{n^5}{27^5}</math> must be close to <math>4393.</math>
 +
 
 +
Note that <math>134</math> will obviously be too small, so we try <math>144</math> and get <math>\left(\frac{144}{27}\right)^5=\left(\frac{16}{3}\right)^5.</math> Bashing through the division, we find that <math>\frac{1048576}{243}\approx 4315,</math> which is very close to <math>4393.</math> It is clear that <math>154</math> will not give any closer of an answer, given the rate that fifth powers grow, so we can safely assume that <math>\boxed{144}</math> is the answer.
 +
 
 +
==Solution 4==
 +
In this solution we take advantage of the large numbers and utilize parity properties to give us a very good guess at the answer. The units digits of <math>133^5, 110^5, 84^5, 27^5</math> are <math>3, 0, 4, 7,</math> respectively, so the units digit of <math>n^5</math> is <math>4.</math> This tells us <math>n</math> is even. Since we are dealing with enormous numbers, <math>n</math> should not be that far from <math>133.</math> Note that <math>n</math>'s units digit is <math>0, 2, 4, 6,</math> or <math>8.</math> When to the power of <math>5,</math> they each give <math>0, 2, 4, 6,</math> and <math>8</math> as the units digits. This further clues us that <math>n</math> ends in <math>4.</math>
  
−
We notice that <math>133,110,84,</math> and <math>27</math> are all very close or equal to multiples of 27. We can rewrite <math>n^5</math> as approximately equal to <math>27^5(5^5+4^5+3^5+1^5) = 27^5(4393)</math>. This means <math>\frac{n}{27}</math> must be close to <math>4393</math>.
+
Clearly, <math>n>133,</math> so we start with <math>134.</math> Now we need a way of distinguishing between numbers with units digit <math>4.</math> We can do this by finding the last three digits for each of <math>133^5, 110^5, 84^5,</math> and <math>27^5,</math> which is not that difficult. For <math>133^5,</math> we have
 +
<cmath>\begin{align*}
 +
133^5&=133^2\cdot133^2\cdot133 \\
 +
&\equiv689\cdot689\cdot133 \\
 +
&\equiv721\cdot133 \\
 +
&\equiv893\pmod{1000}.
 +
\end{align*}</cmath>
 +
By the same reasoning, we get
 +
<cmath>\begin{align*}
 +
n^5&=133^5+110^5+84^5+27^5 \\
 +
&\equiv893+0+424+907 \\
 +
&\equiv224\pmod{1000}.
 +
\end{align*}</cmath>
 +
Note that
 +
<cmath>\begin{align*}
 +
134^5&\equiv424\pmod{1000}, \\
 +
144^5&\equiv224\pmod{1000}, \\
 +
154^5&\equiv024\pmod{1000}, \\
 +
164^5&\equiv824\pmod{1000}, \\
 +
174^5&\equiv624\pmod{1000}, \\
 +
184^5&\equiv424\pmod{1000}, \\
 +
194^5&\equiv224\pmod{1000}.
 +
\end{align*}</cmath>
 +
By observations, <math>n=194</math> is obviously an overestimate. So, the answer is <math>n=\boxed{144}.</math>
  
−
134 will obviously be too small, so we try 144. <math>\left(\frac{144}{27}\right)^5=\left(\frac{16}{3}\right)^5</math>. Bashing through the division, we find that <math>\frac{1048576}{243}\approx 4315</math>, which is very close to <math>4393</math>. It is clear that 154 will not give any closer of an answer, given the rate that fifth powers grow, so we can safely assume that <math>\boxed{144}</math> is the answer.
+
~jackshi2006 (Solution)
  
 +
~MRENTHUSIASM (Revisions and <math>\LaTeX</math> Adjustments)
  
−
==Solution 3==
+
==Solution 5==
−
In this solution we take advantage of the large numbers and utilize parity properties to give us a very good guess at the answer. The units digit of each of the four numbers is 3, 0, 4, and 7, respectively. This means the units digit of <math>n^5</math> is 4. This tells us <math>n</math> is even. Since we are dealing with enormous numbers, <math>n</math> should not be that far from 133. <math>n</math>'s unit digit is 0, 2, 4, 6, or 8. When to the power of 5 they each give 0, 2, 4, 6, and 8 as unit digits. This further clues us that <math>n</math> ends in 4.
 
  
−
<math>n</math> is obviously larger than 133, so we start with 134. Now we need a way of distinguishing between numbers with unit digit 4. This can be done by simply solving up to the hundreds digit of <math>133^5</math>, <math>110^5</math>, <math>84^5</math>, and <math>27^5</math>, which isn't that difficult. For 133, all that has to be done is square it and take the last three digits, 689, and raise them to the power of 2 again, 721, then multiply this by 133. This gives us 893. Doing this for each tells us <math>n^5</math> ends in 224. Testing 134 the same way we did with 133 gives us 424, 144 gives us 224, 154 gives us 024, 164 gives us 824, 624, 424, and finally 194 also gives 224.
+
First, we take mod <math>2</math> on both sides to get <math>n^5\equiv 0\pmod{2}\implies n\equiv 0\pmod{2}</math>. Mod <math>3</math> gives <math>n^5\equiv 0\pmod{3}\implies n\equiv 0\pmod{3}</math>. Also, mod <math>5</math> gives <math>n^5\equiv -1\pmod{5}\implies n\equiv -1\pmod{5}</math> (by FLT). Finally, note that mod <math>7</math> gives <math>n^5\equiv 2\pmod{7}\implies n^{-1}\equiv 2\pmod{7}\implies n\equiv 4\pmod{7}</math>. Thus,
 +
<cmath>\begin{align*}
 +
n&\equiv 0\pmod{2}, \\
 +
n&\equiv 0\pmod{3}, \\
 +
n&\equiv -1\pmod{5}, \\
 +
n&\equiv 4\pmod{7}.
 +
\end{align*}</cmath>
 +
By CRT, <math>n\equiv 144\pmod{210}</math>, so <math>n</math> is one of <math>144, 354, ...</math>. However, <math>133^5 + 110^5 + 84^5 + 27^5 < 4\cdot 133^5 < (2\cdot 133)^5 < 354^5</math>, so <math>n < 354</math>. Thus, <math>n = \boxed{144}</math>.
  
−
By simply using our judgement it's hard to imagine the sum of those powers of 5 to be <math>194^5</math>. The answer is <math>\boxed{144}</math>.
+
~brainfertilzer
  
 +
==Solution 6 (Brute Force)==
  
−
-jackshi2006
+
We have <cmath>n^5 = 133^5 + 110^5 + 84^5 +27^5 = 61917364224,</cmath> for which <math>n = \sqrt [5]{61917364224} = \boxed{144}.</math>
  
 
== See also ==
 
== See also ==

Latest revision as of 14:50, 20 January 2024

Problem

One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that \[133^5+110^5+84^5+27^5=n^{5}.\] Find the value of $n$.

Solution 1 (FLT, CRT, Inequalities)

Taking the given equation modulo $2,3,$ and $5,$ respectively, we have \begin{align*} n^5&\equiv0\pmod{2}, \\ n^5&\equiv0\pmod{3}, \\ n^5&\equiv4\pmod{5}. \end{align*} By either Fermat's Little Theorem (FLT) or inspection, we get \begin{align*} n&\equiv0\pmod{2}, \\ n&\equiv0\pmod{3}, \\ n&\equiv4\pmod{5}. \end{align*} By either the Chinese Remainder Theorem (CRT) or inspection, we get $n\equiv24\pmod{30}.$

It is clear that $n>133,$ so the possible values for $n$ are $144,174,204,\ldots.$ Note that \begin{align*} n^5&=133^5+110^5+84^5+27^5 \\ &<133^5+110^5+(84+27)^5 \\ &=133^5+110^5+111^5 \\ &<3\cdot133^5, \end{align*} from which $\left(\frac{n}{133}\right)^5<3.$

If $n\geq174,$ then \begin{align*} \left(\frac{n}{133}\right)^5&>1.3^5 \\ &=1.3^2\cdot1.3^2\cdot1.3 \\ &>1.6\cdot1.6\cdot1.3 \\ &=2.56\cdot1.3 \\ &>2.5\cdot1.2 \\ &=3, \end{align*} which arrives at a contradiction. Therefore, we conclude that $n=\boxed{144}.$

~MRENTHUSIASM

Solution 2

Note that $n$ is even, since the LHS consists of two odd and two even numbers. By Fermat's Little Theorem, we know $n^5\equiv n\pmod{5}.$ Hence, \[n\equiv3+0+4+2\equiv4\pmod{5}.\] Continuing, we examine the equation modulo $3,$ \[n\equiv1-1+0+0\equiv0\pmod{3}.\] Thus, $n$ is divisible by three and leaves a remainder of four when divided by $5.$ It is obvious that $n>133,$ so the only possibilities are $n = 144$ or $n \geq 174.$ It quickly becomes apparent that $174$ is much too large, so $n$ must be $\boxed{144}.$

~Azjps (Solution)

~MRENTHUSIASM (Reformatting)

Solution 3

We can cheat a little bit and approximate, since we are dealing with such large numbers. As above, $n^5\equiv n\pmod{5},$ and it is easy to see that $n^5\equiv n\pmod 2.$ Therefore, $133^5+110^5+84^5+27^5\equiv 3+0+4+7\equiv 4\pmod{10},$ so the last digit of $n$ is $4.$

We notice that $133,110,84,$ and $27$ are all very close or equal to multiples of $27.$ We can rewrite $n^5$ as approximately equal to $27^5(5^5+4^5+3^5+1^5) = 27^5(4393).$ This means $\frac{n^5}{27^5}$ must be close to $4393.$

Note that $134$ will obviously be too small, so we try $144$ and get $\left(\frac{144}{27}\right)^5=\left(\frac{16}{3}\right)^5.$ Bashing through the division, we find that $\frac{1048576}{243}\approx 4315,$ which is very close to $4393.$ It is clear that $154$ will not give any closer of an answer, given the rate that fifth powers grow, so we can safely assume that $\boxed{144}$ is the answer.

Solution 4

In this solution we take advantage of the large numbers and utilize parity properties to give us a very good guess at the answer. The units digits of $133^5, 110^5, 84^5, 27^5$ are $3, 0, 4, 7,$ respectively, so the units digit of $n^5$ is $4.$ This tells us $n$ is even. Since we are dealing with enormous numbers, $n$ should not be that far from $133.$ Note that $n$'s units digit is $0, 2, 4, 6,$ or $8.$ When to the power of $5,$ they each give $0, 2, 4, 6,$ and $8$ as the units digits. This further clues us that $n$ ends in $4.$

Clearly, $n>133,$ so we start with $134.$ Now we need a way of distinguishing between numbers with units digit $4.$ We can do this by finding the last three digits for each of $133^5, 110^5, 84^5,$ and $27^5,$ which is not that difficult. For $133^5,$ we have \begin{align*} 133^5&=133^2\cdot133^2\cdot133 \\ &\equiv689\cdot689\cdot133 \\ &\equiv721\cdot133 \\ &\equiv893\pmod{1000}. \end{align*} By the same reasoning, we get \begin{align*} n^5&=133^5+110^5+84^5+27^5 \\ &\equiv893+0+424+907 \\ &\equiv224\pmod{1000}. \end{align*} Note that \begin{align*} 134^5&\equiv424\pmod{1000}, \\ 144^5&\equiv224\pmod{1000}, \\ 154^5&\equiv024\pmod{1000}, \\ 164^5&\equiv824\pmod{1000}, \\ 174^5&\equiv624\pmod{1000}, \\ 184^5&\equiv424\pmod{1000}, \\ 194^5&\equiv224\pmod{1000}. \end{align*} By observations, $n=194$ is obviously an overestimate. So, the answer is $n=\boxed{144}.$

~jackshi2006 (Solution)

~MRENTHUSIASM (Revisions and $\LaTeX$ Adjustments)

Solution 5

First, we take mod $2$ on both sides to get $n^5\equiv 0\pmod{2}\implies n\equiv 0\pmod{2}$. Mod $3$ gives $n^5\equiv 0\pmod{3}\implies n\equiv 0\pmod{3}$. Also, mod $5$ gives $n^5\equiv -1\pmod{5}\implies n\equiv -1\pmod{5}$ (by FLT). Finally, note that mod $7$ gives $n^5\equiv 2\pmod{7}\implies n^{-1}\equiv 2\pmod{7}\implies n\equiv 4\pmod{7}$. Thus, \begin{align*} n&\equiv 0\pmod{2}, \\ n&\equiv 0\pmod{3}, \\ n&\equiv -1\pmod{5}, \\ n&\equiv 4\pmod{7}. \end{align*} By CRT, $n\equiv 144\pmod{210}$, so $n$ is one of $144, 354, ...$. However, $133^5 + 110^5 + 84^5 + 27^5 < 4\cdot 133^5 < (2\cdot 133)^5 < 354^5$, so $n < 354$. Thus, $n = \boxed{144}$.

~brainfertilzer

Solution 6 (Brute Force)

We have \[n^5 = 133^5 + 110^5 + 84^5 +27^5 = 61917364224,\] for which $n = \sqrt [5]{61917364224} = \boxed{144}.$

See also

1989 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=1989_AIME_Problems/Problem_9&oldid=211535"