Difference between revisions of "2005 USAMO Problems/Problem 2"
I like pie (talk | contribs) m |
|||
Line 30: | Line 30: | ||
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 == |
+ | |||
+ | Note that the given can be rewritten as | ||
+ | |||
+ | <math>(x^3+y)(x^3+1) = (x^3+y)(x+1)(x^2-x+1) = 147^{157} = 7^{314}3^{152}</math>, | ||
+ | |||
+ | <math>(x^3+y)(y+1)+z^9 = 157^{147}</math>. | ||
+ | |||
+ | We can also see that | ||
+ | |||
+ | <math>x^2-x+1 = (x+1)^2-3(x+1)+3 \rightarrow gcd(x+1, x^2-x+1) \le 3</math>. | ||
+ | |||
+ | Now we notice | ||
+ | |||
+ | <math>x^3+1 = 3^a7^b</math> | ||
+ | for some pair of non-negative integers <math>(a,b)</math>. We also note that | ||
+ | |||
+ | <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>. Furthermore, notice that | ||
+ | |||
+ | <math>x+1 = 3^k7^j</math> | ||
+ | |||
+ | for a pair of positive integers <math>(j,k)</math> means that | ||
+ | |||
+ | <math>x^2-x+1 \ge 3</math> | ||
+ | |||
+ | which cannot be true. We now know that | ||
+ | |||
+ | <math>x+1 = 3^k, 7^k \rightarrow x^2-x+1 = 7^m, 3^m</math>. | ||
+ | |||
+ | Suppose that | ||
+ | |||
+ | <math>x+1 = 7^k \rightarrow (x+1)^2-3(x+1)+3 = 3^m \rightarrow 7^{2k}-37^k+3 = 3^m \rightarrow 7^2k \equiv 0 \pmod{3}</math> | ||
+ | |||
+ | which is a contradiction. Now suppose that | ||
+ | |||
+ | <math>x+1 = 3^k \rightarrow (x+1)^2-3(x+1)+3 = 3*7^m \rightarrow 3^{2k}-3^{k+1}+3 = 3*7^m \rightarrow 3^{2k-1}-x*3^{k}+1 = 7^m \rightarrow 3^k(3^{k-1}-1) = 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 to obtain | ||
+ | |||
+ | <math>k = 1+v_3(m) \le 1+log_3(m) \rightarrow 7^m-1 = 3^k(3^{k-1}-1)\le 3^{1+log_3(m)}(3^{log_3(m)}-1) = 3m(m-1)</math>. | ||
+ | |||
+ | We can see that 7 must divide m and m-1 which cannot be true as they are relatively prime leading us to conclude that there are no solutions to the given system of diophantine equations. | ||
== See also == | == See also == |
Revision as of 18:53, 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
,
.
We can also see that
.
Now we notice
for some pair of non-negative integers . We also note that
when
when . 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
.
We can see that 7 must divide m and m-1 which cannot be true as they are relatively prime leading us to conclude that 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 |