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"

(New page: == Problem == (''Răzvan Gelca'') Prove that the system <cmath> \begin{align*} x^6 + x^3 + x^3y + y &= 147^{157} \\ x^3 + x^3y + y^2 + y + z^9 &= 157^{147} \end{align*} </cmath> has no so...)
 
m
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
 
+
(''Răzvan Gelca'') Prove that the system
−
(''Răzvan Gelca'')
+
<cmath>
−
Prove that the system
+
\begin{align*}x^6 + x^3 + x^3y + y &= 147^{157} \\
−
<cmath> \begin{align*}
+
x^3 + x^3y + y^2 + y + z^9 &= 157^{147}\end{align*}
−
x^6 + x^3 + x^3y + y &= 147^{157} \\
+
</cmath>
−
x^3 + x^3y + y^2 + y + z^9 &= 157^{147}
 
−
\end{align*} </cmath>
 
 
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 ==
 
== Solution ==
−
 
 
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 32: Line 29:
 
<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>
−
 
  
 
{{alternate solutions}}
 
{{alternate solutions}}
  
−
== Resources ==
+
== See also ==
 +
* <url>Forum/viewtopic.php?p=213009#213009 Discussion on AoPS/MathLinks</url>
  
 
{{USAMO newbox|year=2005|num-b=1|num-a=3}}
 
{{USAMO newbox|year=2005|num-b=1|num-a=3}}
−
 
−
* <url>Forum/viewtopic.php?p=213009#213009 Discussion on AoPS/MathLinks</url>
 
−
 
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Revision as of 13:05, 3 May 2008

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$

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_USAMO_Problems/Problem_2&oldid=25809"