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 64: Line 64:
 
Thus we can see that 73 cannot divide the first factor in the right hand side of (3). Let us consider the next case.
 
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>.
+
<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
 
However

Revision as of 22:41, 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. If $x = 0$ then from (1) we can see that $y+1 = 147^{157}$, plugging this into 2 yields

(3) $(147^{157}-1)(147^{157}) = (157^{49}-z^3)(157^{98}+157^{49}z^3+z^6)$, $146 | (147^{157}-1)$, $146 = 2*73$.

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.

$73 | (157^{49}-z^3) \rightarrow z^3 \equiv 11^{49} \pmod{73} \rightarrow (11^{49})^{24} \equiv 1 \pmod{73}$.

However

$(11^{49})^{24} \equiv 8 \pmod{73}$

Thus we can see that 73 cannot divide the first factor in the right hand side of (3). Let us consider the next case.

$73 | (157^{98}+157^{49}z^3+z^6) \rightarrow 11^{98}+11^{49}z^3+z^6 \ equiv 0 \pmod{73}$.

However

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

It can be seen that 11 and 15 are not perfect cubes $\pmod{73}$ 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 $|x| \ge 2$. 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=45721"