Difference between revisions of "1989 AIME Problems/Problem 9"
PI-Dimension (talk | contribs) m (→Solution) |
m (→Solution 6) |
||
(36 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == 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 < | + | 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 == | + | == Solution 1 (FLT, CRT, Inequalities) == |
− | + | Taking the given equation modulo <math>2,3,</math> and <math>5,</math> respectively, we have | |
− | < | + | <cmath>\begin{align*} |
− | < | + | 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> | ||
− | + | 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 | |
− | < | + | <cmath>\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*}</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. | + | 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 == | ||
+ | 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*} | ||
+ | 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> | ||
+ | |||
+ | ~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 | ||
+ | |||
+ | ==Solution 6 (Brute Force)== | ||
+ | |||
+ | 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 == | ||
Line 17: | Line 108: | ||
[[Category:Intermediate Number Theory Problems]] | [[Category:Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 15:50, 20 January 2024
Contents
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 Find the value of
.
Solution 1 (FLT, CRT, Inequalities)
Taking the given equation modulo and
respectively, we have
By either Fermat's Little Theorem (FLT) or inspection, we get
By either the Chinese Remainder Theorem (CRT) or inspection, we get
It is clear that so the possible values for
are
Note that
from which
If then
which arrives at a contradiction. Therefore, we conclude that
~MRENTHUSIASM
Solution 2
Note that is even, since the LHS consists of two odd and two even numbers. By Fermat's Little Theorem, we know
Hence,
Continuing, we examine the equation modulo
Thus,
is divisible by three and leaves a remainder of four when divided by
It is obvious that
so the only possibilities are
or
It quickly becomes apparent that
is much too large, so
must be
~Azjps (Solution)
~MRENTHUSIASM (Reformatting)
Solution 3
We can cheat a little bit and approximate, since we are dealing with such large numbers. As above, and it is easy to see that
Therefore,
so the last digit of
is
We notice that and
are all very close or equal to multiples of
We can rewrite
as approximately equal to
This means
must be close to
Note that will obviously be too small, so we try
and get
Bashing through the division, we find that
which is very close to
It is clear that
will not give any closer of an answer, given the rate that fifth powers grow, so we can safely assume that
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 are
respectively, so the units digit of
is
This tells us
is even. Since we are dealing with enormous numbers,
should not be that far from
Note that
's units digit is
or
When to the power of
they each give
and
as the units digits. This further clues us that
ends in
Clearly, so we start with
Now we need a way of distinguishing between numbers with units digit
We can do this by finding the last three digits for each of
and
which is not that difficult. For
we have
By the same reasoning, we get
Note that
By observations,
is obviously an overestimate. So, the answer is
~jackshi2006 (Solution)
~MRENTHUSIASM (Revisions and Adjustments)
Solution 5
First, we take mod on both sides to get
. Mod
gives
. Also, mod
gives
(by FLT). Finally, note that mod
gives
. Thus,
By CRT,
, so
is one of
. However,
, so
. Thus,
.
~brainfertilzer
Solution 6 (Brute Force)
We have for which
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.