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 1)
 
(25 intermediate revisions by 5 users not shown)
Line 7: Line 7:
 
has no solutions in integers <math>x</math>, <math>y</math>, and <math>z</math>.
 
has no solutions in integers <math>x</math>, <math>y</math>, and <math>z</math>.
  
−
== Solution ==
+
== Solutions ==
 +
=== Solution 1 ===
 
It suffices to show that there are no solutions to this system in the integers mod 19.  We note that <math>152 = 8 \cdot 19</math>, so <math>157 \equiv -147 \equiv 5 \pmod{19}</math>.  For reference, we construct a table of powers of five:
 
It suffices to show that there are no solutions to this system in the integers mod 19.  We note that <math>152 = 8 \cdot 19</math>, so <math>157 \equiv -147 \equiv 5 \pmod{19}</math>.  For reference, we construct a table of powers of five:
 
<cmath> \begin{array}{c|c||c|c}
 
<cmath> \begin{array}{c|c||c|c}
Line 17: Line 18:
 
5 & 9 &&
 
5 & 9 &&
 
\end{array} </cmath>
 
\end{array} </cmath>
−
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.
+
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 <math>147^{157} \equiv (-5)^{13} \equiv -5^4 \equiv 2</math>, and <math>157^{147} \equiv 5^3 \equiv -8</math>.  Thus we rewrite our system thus:
 
It follows that <math>147^{157} \equiv (-5)^{13} \equiv -5^4 \equiv 2</math>, and <math>157^{147} \equiv 5^3 \equiv -8</math>.  Thus we rewrite our system thus:
Line 25: Line 26:
 
\end{align*} </cmath>
 
\end{align*} </cmath>
 
Adding these, we have
 
Adding these, we have
−
<cmath> (x^3+y+1)^2 - 1 + z^9 &\equiv -6, </cmath>
+
<cmath> (x^3+y+1)^2 - 1 + z^9 \equiv -6, </cmath>
 
or
 
or
 
<cmath> (x^3+y+1)^2 \equiv -z^9 - 5 . </cmath>
 
<cmath> (x^3+y+1)^2 \equiv -z^9 - 5 . </cmath>
 
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 ==  
+
=== Solution 2 ===
  
 
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
  
−
<math>x^2-x+1 = (x+1)^2-3(x+1)+3 \rightarrow gcd(x+1, x^2-x+1) \le 3</math>.
+
<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  
 
Now we notice  
  
 
<math>x^3+1 = 3^a7^b</math>
 
<math>x^3+1 = 3^a7^b</math>
 +
 
for some pair of non-negative integers <math>(a,b)</math>. We also note that  
 
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>  
 
<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. If <math>x = 0</math> then from (1) we can see that <math>y+1 = 147^{157}</math>, plugging this into 2 yields
 +
 
 +
(3) <math>(147^{157}-1)(147^{157}) = (157^{49}-z^3)(157^{98}+157^{49}z^3+z^6)</math>, <math>146 | (147^{157}-1)</math>, <math>146 = 2*73</math>.
 +
 
 +
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.
 +
 
 +
<math>73 | (157^{49}-z^3) \rightarrow z^3 \equiv 11^{49} \pmod{73} \rightarrow (11^{49})^{24} \equiv 1 \pmod{73}</math>.
 +
 
 +
However
 +
 
 +
<math>(11^{49})^{24} \equiv 8 \pmod{73}</math>
 +
 
 +
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>x+1 = 3^k7^j</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>.
  
−
for a pair of positive integers <math>(j,k)</math> means that
+
However
  
−
<math>x^2-x+1 \ge 3</math>
+
<math>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}</math>.
  
−
which cannot be true. We now know that
+
It can be seen that 11 and 15 are not perfect cubes <math>\pmod{73}</math> from the following.
  
−
<math>x+1 = 3^k, 7^k \rightarrow x^2-x+1 = 7^m, 3^m</math>.
+
<math>15^{24} \equiv 11^{24} \equiv 8 \not\equiv 1 \pmod{73}</math>
  
−
Suppose that  
+
We can now see that <math>|x| \ge 2</math>. Furthermore, notice that if
  
−
<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>  
+
<math>x+1 = \pm3^k7^j</math>
 +
 
 +
for a pair of positive integers <math>(j,k)</math> means that
 +
 
 +
<math>|x^2-x+1| \le 3</math>
 +
 
 +
which cannot be true. We now know that
 +
 
 +
<math>x+1 = \pm3^k, \pm7^k \rightarrow x^2-x+1 = 3*7^m, 3^m</math>.
 +
 
 +
Suppose that
 +
 
 +
<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 = 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>.
+
<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
 +
 
 +
<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 > 2</math> we can see that
 +
 
 +
<math>7^m-1 > 9m(3m\pm1)</math>
 +
 
 +
which is a contradiction. Therefore there only possible solution is when
 +
 
 +
<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
 +
 
 +
(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.
 +
 
 +
<math>9 | 157^{49}-z^3 \rightarrow 157^{49}-z^3 \equiv 0 \pmod{9}</math>.
 +
 
 +
However,
 +
 
 +
<math>z^3 \equiv 0, 1, 8\pmod{9}, 157^{49}-z^3 \equiv 4-z^3 \not\equiv 0 \pmod{9}</math>.
 +
 
 +
We now consider the second case.
 +
 
 +
<math>9 | (z^6+157^{49}z^3+157^{98}) \rightarrow 157^{98}+157^{49}z^3+z^6\equiv 0\pmod{9}</math>.
 +
 
 +
However
 +
 
 +
<math>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}</math>
 +
 
 +
Therefore there are no solutions to the given system of diophantine equations. <math>\blacksquare</math>
  
−
We now apply the lifting the exponent lemma to examine the power of 3 that divides each side of the equation to obtain
+
=== Solution 3 ===
 +
We will show there is no solution to the system modulo 13. Add the two equations and add 1 to obtain
 +
<cmath>(x^3 + y + 1)^2 + z^9 = 147^{157} + 157^{147} + 1.</cmath>
 +
By Fermat's Theorem, <math>a^{12}\equiv 1\pmod{13}</math> when <math>a</math> is not a multiple of 13. Hence we compute <math>147^{157}\equiv 4^1\equiv 4\pmod{13}</math> and <math>157^{147}\equiv 1^3\equiv 1\pmod{13}</math>. Thus
 +
<cmath>(x^3 + y + 1)^2 + z^9\equiv 6\pmod{13}.</cmath>
 +
The cubes mod 13 are <math>0</math>, <math>\pm 1</math>, and <math>\pm 5</math>. Writing the first equation as
 +
<cmath>(x^3 + 1)(x^3 + y)\equiv 4\pmod{13},</cmath>
 +
we see that there is no solution in case <math>x^3\equiv -1\pmod{13}</math> and for <math>x^3</math> congruent to <math>0, 1, 5, -5\pmod{13}</math>, correspondingly <math>x^3 + y</math> must be congruent to <math>4, 2, 5, -1</math>. Hence
 +
<cmath>(x^3 + y + 1)^2\equiv \text{12, 9, 10, or 0}\pmod{13}.</cmath>
 +
Also <math>z^9</math> is a cube, hence <math>z^9</math> must be <math>\text{0, 1, 5, 8, or 12}\pmod{13}</math>. It is easy to check that <math>6\pmod{13}</math> is not obtained by adding one of <math>0, 9, 10, 12</math> to one of <math>0, 1, 5, 8, 12</math>. Hence the system has no solutions in integers.
  
−
<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>.
+
''Note'': This argument shows there is no solution even if <math>z^9</math> is replaced by <math>z^3</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.
+
{{alternate solutions}}
  
 
== See also ==
 
== See also ==
Line 81: Line 150:
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 09:38, 12 August 2015

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

Solutions

Solution 1

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,\] 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$

Solution 3

We will show there is no solution to the system modulo 13. Add the two equations and add 1 to obtain \[(x^3 + y + 1)^2 + z^9 = 147^{157} + 157^{147} + 1.\] By Fermat's Theorem, $a^{12}\equiv 1\pmod{13}$ when $a$ is not a multiple of 13. Hence we compute $147^{157}\equiv 4^1\equiv 4\pmod{13}$ and $157^{147}\equiv 1^3\equiv 1\pmod{13}$. Thus \[(x^3 + y + 1)^2 + z^9\equiv 6\pmod{13}.\] The cubes mod 13 are $0$, $\pm 1$, and $\pm 5$. Writing the first equation as \[(x^3 + 1)(x^3 + y)\equiv 4\pmod{13},\] we see that there is no solution in case $x^3\equiv -1\pmod{13}$ and for $x^3$ congruent to $0, 1, 5, -5\pmod{13}$, correspondingly $x^3 + y$ must be congruent to $4, 2, 5, -1$. Hence \[(x^3 + y + 1)^2\equiv \text{12, 9, 10, or 0}\pmod{13}.\] Also $z^9$ is a cube, hence $z^9$ must be $\text{0, 1, 5, 8, or 12}\pmod{13}$. It is easy to check that $6\pmod{13}$ is not obtained by adding one of $0, 9, 10, 12$ to one of $0, 1, 5, 8, 12$. Hence the system has no solutions in integers.

Note: This argument shows there is no solution even if $z^9$ is replaced by $z^3$.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_USAMO_Problems/Problem_2&oldid=71525"