Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2005 USAMO Problems/Problem 2"

(→‎Solution 2)
(→‎Solution 2)
Line 34: Line 34:
 
Note that the given can be rewritten as  
 
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>,
+
(1) <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>.
+
(2) <math>(x^3+y)(y+1)+z^9 = 157^{147} \rightarrow (x^3+y)(y+1) = (157^{49}-z^3)(157^{98}+157^{49}z^3+z^6)</math>.
  
 
We can also see that
 
We can also see that
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>. 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. We can now see that <math>|x| \ge 2</math> or <math>x = 0</math>. Furthermore, notice that  
  
 
<math>x+1 = 3^k7^j</math>
 
<math>x+1 = 3^k7^j</math>
Line 74: Line 74:
 
<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>.
 
<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 this does not hold for m = 1. For <math>m \ge 2</math> we can see that <math>7^m-1 > 3m(m-1)</math> which is a contradiction. Therefore there are no solutions to the given system of diophantine equations.
+
For <math>m \ge 0</math> we can see that <math>7^m-1 > 3m(m-1)</math> which is a contradiction. Therefore there are no solutions to the given system of diophantine equations.
  
 
== See also ==
 
== See also ==

Revision as of 21:04, 23 March 2012

Problem

(Răzvan Gelca) Prove that the system \begin{align*}x^6 + x^3 + x^3y + y &= 147^{157} \\ x^3 + x^3y + y^2 + y + z^9 &= 157^{147}\end{align*} has no solutions in integers $x$, $y$, and $z$.

Solution

It suffices to show that there are no solutions to this system in the integers mod 19. We note that $152 = 8 \cdot 19$, so $157 \equiv -147 \equiv 5 \pmod{19}$. For reference, we construct a table of powers of five: \[\begin{array}{c|c||c|c} n& 5^n &n & 5^n \\\hline 1 & 5 & 6 & 7 \\ 2 & 6 & 7 & -3 \\ 3 & -8 & 8 & 4 \\ 4 & -2 & 9 & 1 \\ 5 & 9 && \end{array}\] 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 $147^{157} \equiv (-5)^{13} \equiv -5^4 \equiv 2$, and $157^{147} \equiv 5^3 \equiv -8$. Thus we rewrite our system thus: \begin{align*} (x^3+y)(x^3+1) &\equiv 2 \\ (x^3+y)(y+1) + z^9 &\equiv -8 . \end{align*} Adding these, we have 

\[(x^3+y+1)^2 - 1 + z^9 &\equiv -6,\] (Error compiling LaTeX. Unknown error_msg)

or \[(x^3+y+1)^2 \equiv -z^9 - 5 .\] By Fermat's Little Theorem, the only possible values of $z^9$ are $\pm 1$ and 0, so the only possible values of $(x^3+y+1)^2$ are $-4,-5$, and $-6$. 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. $\blacksquare$

Solution 2

Note that the given can be rewritten as

(1) $(x^3+y)(x^3+1) = (x^3+y)(x+1)(x^2-x+1) = 147^{157} = 7^{314}3^{152}$,

(2) $(x^3+y)(y+1)+z^9 = 157^{147} \rightarrow (x^3+y)(y+1) = (157^{49}-z^3)(157^{98}+157^{49}z^3+z^6)$.

We can also see that

$x^2-x+1 = (x+1)^2-3(x+1)+3 \rightarrow gcd(x+1, x^2-x+1) \le 3$.

Now we notice

$x^3+1 = 3^a7^b$

for some pair of non-negative integers $(a,b)$. We also note that

$x^2 \ge 2x$ when $|x| \ge 2 \rightarrow x^2-x+1 \ge x+1$

when $|x| \ge 2$. If $x = 1$ or $x = -1$ then examining (1) would yield $147^{157} \equiv 0 \pmod{2}$ which is a contradiction. We can now see that $|x| \ge 2$ or $x = 0$. Furthermore, notice that

$x+1 = 3^k7^j$ 

for a pair of positive integers $(j,k)$ means that

$x^2-x+1 \le 3$ 

which cannot be true. We now know that

$x+1 = 3^k, 7^k \rightarrow x^2-x+1 = 7^m, 3^m$. 

Suppose that

$x+1 = 7^k \rightarrow (x+1)^2-3(x+1)+3 = 3^m \rightarrow 7^{2k}-3*7^k+3 = 3^m \rightarrow 7^{2k} \equiv 0 \pmod{3}$

which is a contradiction. Now suppose that

$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$.

We now apply the lifting the exponent lemma to examine the power of 3 that divides each side of the equation to obtain

$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)$.

For $m \ge 0$ we can see that $7^m-1 > 3m(m-1)$ 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_USAMO_Problems/Problem_2&oldid=45715"