Difference between revisions of "2005 USAMO Problems/Problem 2"
(→Solution 2) |
(→Solution 2) |
||
Line 76: | Line 76: | ||
We can now see that <math>|x| \ge 2</math>. Furthermore, notice that if | We can now see that <math>|x| \ge 2</math>. Furthermore, notice that if | ||
− | <math>x+1 = | + | <math>x+1 = \pm3^k7^j</math> |
for a pair of positive integers <math>(j,k)</math> means that | for a pair of positive integers <math>(j,k)</math> means that | ||
− | <math>x^2-x+1 \le 3</math> | + | <math>|x^2-x+1| \le 3</math> |
which cannot be true. We now know that | which cannot be true. We now know that | ||
− | <math>x+1 = | + | <math>x+1 = \pm3^k, \pm7^k \rightarrow x^2-x+1 = 3*7^m, 3^m</math>. |
Suppose that | Suppose that | ||
− | <math>x+1 = | + | <math>x+1 = \pm7^k \rightarrow (x+1)^2-3(x+1)+3 = 3^m \rightarrow 7^{2k}\pm3*7^k+3 = 3^m \rightarrow 7^{2k} \equiv 0\pmod{3}</math> |
which is a contradiction. Now suppose that | which is a contradiction. Now suppose that | ||
− | <math>x+1 = | + | <math>x+1 = \pm3^k \rightarrow (x+1)^2-3(x+1)+3 = 3*7^m \rightarrow 3^{2k}\pm3^{k+1}+3 = 3*7^m \rightarrow 3^{2k-1}\pm3^{k}+1 = 7^m \rightarrow 3^k(3^{k-1}\pm1) = 7^m-1</math>. |
We now apply the lifting the exponent lemma to examine the power of 3 that divides each side of the equation when <math>m > 0</math> to obtain | We now apply the lifting the exponent lemma to examine the power of 3 that divides each side of the equation when <math>m > 0</math> to obtain | ||
− | <math>k | + | <math>k \le 2+v_3(m) \le 2+log_3(m) \rightarrow 7^m-1 = 3^k(3^{k-1}\pm1)\le 3^{2+log_3(m)}(3^{1+log_3(m)}\pm1) = 9m(3m\pm1)</math>. |
− | For <math>m > | + | For <math>m > 2</math> we can see that |
− | <math>7^m-1 > 3m | + | <math>7^m-1 > 9m(3m\pm1)</math> |
which is a contradiction. Therefore there only possible solution is when | which is a contradiction. Therefore there only possible solution is when | ||
− | <math>m = 0 \rightarrow x = 2</math>. | + | <math>m = 0 \rightarrow k = 1 \rightarrow x = 2, m = 1 \rightarrow k = 1 \rightarrow x = -4, m = 2 \rightarrow</math> no integer solutions for k. |
Plugging this back into (1) and (2) yields | Plugging this back into (1) and (2) yields | ||
− | (4) <math> | + | (4) <math>3^{155} | (x^3+y) \rightarrow 3^{155}| (157^{49}-z^3)(157^{98}+157^{49}z^3+z^6)</math>. |
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. | 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. |
Revision as of 13:15, 24 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.
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.
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 |