Difference between revisions of "2005 USAMO Problems/Problem 2"
(→Solution) |
5849206328x (talk | contribs) m |
||
Line 7: | Line 7: | ||
has no solutions in integers <math>x</math>, <math>y</math>, and <math>z</math>. | has no solutions in integers <math>x</math>, <math>y</math>, and <math>z</math>. | ||
− | |||
Consider solving the problem by taking both equations '''mod 19'''. | Consider solving the problem by taking both equations '''mod 19'''. | ||
− | + | == Solutions == | |
− | + | === Solution 1 === | |
− | |||
− | == Solution == | ||
It suffices to show that there are no solutions to this system in the integers mod 19. We note that <math>152 = 8 \cdot 19</math>, so <math>157 \equiv -147 \equiv 5 \pmod{19}</math>. For reference, we construct a table of powers of five: | It suffices to show that there are no solutions to this system in the integers mod 19. We note that <math>152 = 8 \cdot 19</math>, so <math>157 \equiv -147 \equiv 5 \pmod{19}</math>. For reference, we construct a table of powers of five: | ||
<cmath> \begin{array}{c|c||c|c} | <cmath> \begin{array}{c|c||c|c} | ||
Line 36: | Line 33: | ||
By [[Fermat's Little Theorem]], the only possible values of <math>z^9</math> are <math>\pm 1</math> and 0, so the only possible values of <math>(x^3+y+1)^2</math> are <math>-4,-5</math>, and <math>-6</math>. But none of these are squares mod 19, a contradiction. Therefore the system has no solutions in the integers mod 19. Therefore the solution has no equation in the integers. <math>\blacksquare</math> | By [[Fermat's Little Theorem]], the only possible values of <math>z^9</math> are <math>\pm 1</math> and 0, so the only possible values of <math>(x^3+y+1)^2</math> are <math>-4,-5</math>, and <math>-6</math>. But none of these are squares mod 19, a contradiction. Therefore the system has no solutions in the integers mod 19. Therefore the solution has no equation in the integers. <math>\blacksquare</math> | ||
− | == Solution 2 == | + | === Solution 2 === |
Note that the given can be rewritten as | Note that the given can be rewritten as | ||
Line 133: | Line 130: | ||
Therefore there are no solutions to the given system of diophantine equations. <math>\blacksquare</math> | Therefore there are no solutions to the given system of diophantine equations. <math>\blacksquare</math> | ||
+ | |||
+ | {{alternate solutions}} | ||
== See also == | == See also == |
Revision as of 16:13, 19 July 2014
Contents
[hide]Problem
(Răzvan Gelca) Prove that the system has no solutions in integers , , and .
Consider solving the problem by taking both equations mod 19.
Solutions
Solution 1
It suffices to show that there are no solutions to this system in the integers mod 19. We note that , so . For reference, we construct a table of powers of five: Evidently, the order of 5 is 9. Hence 5 is the square of a multiplicative generator of the nonzero integers mod 19, so this table shows all nonzero squares mod 19, as well.
It follows that , and . Thus we rewrite our system thus: Adding these, we have
\[(x^3+y+1)^2 - 1 + z^9 &\equiv -6,\] (Error compiling LaTeX. Unknown error_msg)
or By Fermat's Little Theorem, the only possible values of are and 0, so the only possible values of are , and . But none of these are squares mod 19, a contradiction. Therefore the system has no solutions in the integers mod 19. Therefore the solution has no equation in the integers.
Solution 2
Note that the given can be rewritten as
(1) ,
(2) .
We can also see that
.
Now we notice
for some pair of non-negative integers . We also note that
when
when . If or then examining (1) would yield which is a contradiction. If then from (1) we can see that , plugging this into 2 yields
(3) , , .
Noting that 73 is a prime number we see that it must divide at least 1 of the 2 factors on the right hand side of 3. Let us consider both cases.
.
However
Thus we can see that 73 cannot divide the first factor in the right hand side of (3). Let us consider the next case.
.
However
.
It can be seen that 11 and 15 are not perfect cubes from the following.
We can now see that . Furthermore, notice that if
for a pair of positive integers means that
which cannot be true. We now know that
.
Suppose that
which is a contradiction. Now suppose that
.
We now apply the lifting the exponent lemma to examine the power of 3 that divides each side of the equation when to obtain
.
For we can see that
which is a contradiction. Therefore there only possible solution is when
no integer solutions for k.
Plugging this back into (1) and (2) yields
(4) .
In order for (4) to be true we must have 9 dividing at least 1 of the factors on the right hand side of the equation. Let us consider both cases.
.
However,
.
We now consider the second case.
.
However
Therefore there are no solutions to the given system of diophantine equations.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See also
- <url>Forum/viewtopic.php?p=213009#213009 Discussion on AoPS/MathLinks</url>
2005 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.