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 1)
 
(18 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  
Line 40: Line 41:
 
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  
Line 56: Line 57:
 
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.
 
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>.
+
<math>73 | (157^{49}-z^3) \rightarrow z^3 \equiv 11^{49} \pmod{73} \rightarrow (11^{49})^{24} \equiv 1 \pmod{73}</math>.
  
 
However
 
However
Line 64: Line 65:
 
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
Line 72: Line 73:
 
It can be seen that 11 and 15 are not perfect cubes <math>\pmod{73}</math> from the following.
 
It can be seen that 11 and 15 are not perfect cubes <math>\pmod{73}</math> from the following.
  
−
<math>15^{24} \equiv 11^{24} \equiv 8 \nequiv 1 \pmod{73}</math>
+
<math>15^{24} \equiv 11^{24} \equiv 8 \not\equiv 1 \pmod{73}</math>
  
−
We can now see that <math>|x| \ge 2</math>. Furthermore, notice that  
+
We can now see that <math>|x| \ge 2</math>. Furthermore, notice that if
  
−
<math>x+1 = 3^k7^j</math>
+
<math>x+1 = \pm3^k7^j</math>
  
 
for a pair of positive integers <math>(j,k)</math> means that  
 
for a pair of positive integers <math>(j,k)</math> means that  
  
−
<math>x^2-x+1 \le 3</math>
+
<math>|x^2-x+1| \le 3</math>
  
 
which cannot be true. We now know that  
 
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>.
+
<math>x+1 = \pm3^k, \pm7^k \rightarrow x^2-x+1 = 3*7^m, 3^m</math>.
  
 
Suppose that  
 
Suppose that  
  
−
<math>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}</math>  
+
<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 to obtain
+
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 = 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 \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 \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.
+
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>
 +
 
 +
=== 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.
 +
 
 +
''Note'': This argument shows there is no solution even if <math>z^9</math> is replaced by <math>z^3</math>.
 +
 
 +
{{alternate solutions}}
  
 
== See also ==
 
== See also ==
Line 106: 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"