Difference between revisions of "2005 USAMO Problems/Problem 2"
(→Solution 2) |
(→Solution 2) |
||
Line 50: | Line 50: | ||
<math>x^2 \ge 2x</math> when <math>|x| \ge 2 \rightarrow x^2-x+1 \ge x+1</math> | <math>x^2 \ge 2x</math> when <math>|x| \ge 2 \rightarrow x^2-x+1 \ge x+1</math> | ||
− | when <math>|x| \ge 2</math>. If <math>x = 1</math> or <math>x = -1</math> then examining (1) would yield <math>147^{157} \equiv 0 \pmod{2}</math> which is a contradiction. If <math>x = 0</math> then from (1) we can see that <math>y+1 = 147^{157}</math>, plugging this into 2 yields <math>(147^{157}-1)(147^{157}) = (157^{49}-z^3)(157^{98}+157^{49}z^3+z^6)</math>. We can now see that <math>|x| \ge 2</math>. Furthermore, notice that | + | when <math>|x| \ge 2</math>. If <math>x = 1</math> or <math>x = -1</math> then examining (1) would yield <math>147^{157} \equiv 0 \pmod{2}</math> which is a contradiction. If <math>x = 0</math> then from (1) we can see that <math>y+1 = 147^{157}</math>, plugging this into 2 yields |
+ | |||
+ | (3) <math>(147^{157}-1)(147^{157}) = (157^{49}-z^3)(157^{98}+157^{49}z^3+z^6)</math>, <math>146 | (147^{157}-1)</math>, <math>146 = 2*73</math>. | ||
+ | |||
+ | 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. | ||
+ | |||
+ | <math>73 | (157^{49}-z^3) \rightarrow z^3 \equiv 11^{49} \pmod{73} \rightarrow (11^{49})^24 \ equiv 1 \pmod{73}</math>. | ||
+ | |||
+ | However | ||
+ | |||
+ | <math>(11^{49})^24 \ equiv 8 \pmod{73}</math> | ||
+ | |||
+ | Thus we can see that 73 cannot divide the first factor in the right hand side of (3). Let us consider the next case. | ||
+ | |||
+ | <math>73 | (157^{98}+157^{49}z^3+z^6) \ rightarrow 11^{98}+11^{49}z^3+z^6 \ equiv 0 \pmod{73}</math>. | ||
+ | |||
+ | However | ||
+ | |||
+ | <math>11^{98}+11^{49}z^3+z^6 \equiv z^6+47z^3+19 \equiv z^6-26z^3+19 \equiv (z^3-13)^2-150 \equiv (z^3-13)^2-4 \equiv (z^3-11)(z^3-15) \pmod{73}</math>. | ||
+ | |||
+ | It can be seen that 11 and 15 are not perfect cubes <math>\pmod{73}</math> from the following. | ||
+ | |||
+ | <math>15^{24} \equiv 11^{24} \equiv 8 \nequiv 1 \pmod{73}</math> | ||
+ | |||
+ | We can now see that <math>|x| \ge 2</math>. Furthermore, notice that | ||
<math>x+1 = 3^k7^j</math> | <math>x+1 = 3^k7^j</math> |
Revision as of 21:39, 23 March 2012
Contents
[hide]Problem
(Răzvan Gelca) Prove that the system has no solutions in integers , , and .
Solution
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, then 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.
$15^{24} \equiv 11^{24} \equiv 8 \nequiv 1 \pmod{73}$ (Error compiling LaTeX. Unknown error_msg)
We can now see that . Furthermore, notice that
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 to obtain
.
For we can see that which is a contradiction. Therefore there are no solutions to the given system of diophantine equations.
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 |