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

Revision as of 10:26, 19 April 2014

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

Hint

Consider solving the problem by taking both equations mod 19.

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, 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 \not\equiv 1 \pmod{73}$

We can now see that $|x| \ge 2$ . Furthermore, notice that if

$x+1 = \pm3^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 = \pm3^k, \pm7^k \rightarrow x^2-x+1 = 3*7^m, 3^m$ .

Suppose that

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

which is a contradiction. Now suppose that

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

We now apply the lifting the exponent lemma to examine the power of 3 that divides each side of the equation when $m > 0$ to obtain

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

For $m > 2$ we can see that

$7^m-1 > 9m(3m\pm1)$

which is a contradiction. Therefore there only possible solution is when

$m = 0 \rightarrow k = 1 \rightarrow x = 2, m = 1 \rightarrow k = 1 \rightarrow x = -4, m = 2 \rightarrow$ no integer solutions for k.

Plugging this back into (1) and (2) yields

(4) $3^{155} | (x^3+y) \rightarrow 3^{155}| (157^{49}-z^3)(157^{98}+157^{49}z^3+z^6)$ .

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.

$9 | 157^{49}-z^3 \rightarrow 157^{49}-z^3 \equiv 0 \pmod{9}$ .

However,

$z^3 \equiv 0, 1, 8\pmod{9}, 157^{49}-z^3 \equiv 4-z^3 \not\equiv 0 \pmod{9}$ .

We now consider the second case.

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

However

$z^6+157^{49}z^3+157^{98} \equiv z^6+4z^3+7 \equiv (z^3+2)^2+3 \not\equiv 0\pmod{9}$

Therefore there are no solutions to the given system of diophantine equations. $\blacksquare$

@@ Line 6: / Line 6: @@
 </cmath>
 has no solutions in integers <math>x</math>, <math>y</math>, and <math>z</math>.
+==Hint==
+Consider solving the problem by taking both equations '''mod 19'''.
 == Solution ==

2005 USAMO (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

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

Revision as of 10:26, 19 April 2014

Contents

Problem

Hint

Solution

Solution 2

See also