Difference between revisions of "1989 AIME Problems/Problem 9"

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

@@ Line 1: / Line 1: @@
 == 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 <math>133^5+110^5+84^5+27^5=n^{5}</math>. 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 ==
-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>
+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*}
+^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*}
+^5&\equiv424\pmod{1000}, \\
+^5&\equiv224\pmod{1000}, \\
+^5&\equiv024\pmod{1000}, \\
+^5&\equiv824\pmod{1000}, \\
+^5&\equiv624\pmod{1000}, \\
+^5&\equiv424\pmod{1000}, \\
+^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>
+~jackshi2006 (Solution)
+~MRENTHUSIASM (Revisions and <math>\LaTeX</math> Adjustments)
+==Solution 5==
+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>.
+~brainfertilzer
-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>.
+==Solution 6 (Brute Force)==
-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.
+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 ==

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

Page

Toolbox

Search