Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$u + v = 2$$ $$ux + vy = 1$$ $$ux^2 + vy^2 = - 1$$ $$ux^3 + vy^3 = -5$$

Can anyone give me a hint for solving this ? I'm kinda stuck.

share|improve this question
    
Start by letting u=2-v and then substitute that into ux+vy=1. Continue isolating variables and making substitutions. If I did my algebra correctly, you should find 2 sets of integer solutions. You may also want to look at Chapter 2 of Cox, Little, O'Shea's book for a discussion of Grobner basis which give a more general method of solving these types of problems. –  WWright Oct 16 '10 at 18:41
    
ok i'll try again, i must have miscalculated –  andrei Oct 16 '10 at 18:42
add comment

4 Answers

up vote 8 down vote accepted

HINT $\ \ $ Exploit the innate symmetry:

$\rm\quad\quad\quad\quad u x^2 + v y^2\ =\ (x+y)\ (ux\ +\ vy)\ -\ xy\ (u+v)$

$\rm\quad\quad\quad\quad u x^3 + v y^3\ =\ (x+y)\ (ux^2+vy^2) -\: xy\ (ux+vy)$

yields $\rm\quad\quad\quad\quad\:\ \ -1 \ =\ \ x+y\ -\ 2\ xy $

$\rm\quad\quad\quad\quad\quad\quad\quad\quad\quad\ 5\ =\ \ x+y\ \:\ +\:\ \ xy$

Solving yields $\rm\quad\quad\ \ x+y = 3,\ \ \ xy = 2\ \ \Rightarrow\ \ \{x,\:y\}\ =\ \{1,\:2\}$

REMARK $\ $ Readers familiar with the theory of Lucas-Lehmer sequences may recognize this recursion as one of many useful identities satisfied by sums of powers. Such identities arise in many diverse contexts. Here is another example: Capdegelle's work on FLT (Fermat's Last Theorem) employed the recursion $\rm\ F_{n+3} + S_2\: F_{n+2} + S_1\: F_{n+1} + S_0\: F_n = 0\ $ where $\rm\ F_n = X^n + Y^n - Z^n\ $ is the Fermat polynomial and the polynomials $\rm\ S_k\ $ are the elementary symmetric polynomials $\rm\ S_0 = -XYZ,$ $\rm\ S_1 = XY + XZ + YZ,\ $ $\rm S_2 = -(X+Y+Z)\:.\ $

share|improve this answer
    
definitely the best way to solve it by far. –  Eugene Bulkin Oct 17 '10 at 3:27
2  
@Eugene, it requires thinking. I prefer methods that do not demand so much of myself! –  Mariano Suárez-Alvarez Oct 17 '10 at 6:30
1  
@Mariano Suárez-Alvarez: Hopefully you jest. Surely the problem was designed precisely to encourage students to think - to see the pretty innate symmetry - not to appeal to brute-force techniques such as Grobner bases. –  Bill Dubuque Oct 17 '10 at 15:34
    
@Eugene: I really don't see how this is different from my answer. The $a,b$ in my answer satisfy $a = -(x+y)$ and $b= xy$ and the equations are exactly the same. In fact that answer makes it easy to see these identities and can easily be generalized. –  Aryabhata Oct 17 '10 at 21:34
    
well, for me, it's only easier because it shows clear symmetry, while yours doesn't suggest it immediately; I feel like people would more likely move to symmetry than to making x and y roots of some other polynomial. –  Eugene Bulkin Oct 18 '10 at 2:44
show 5 more comments

One way to do this is using Groebner basis (which is implemented in most serious computer algebra systems, and which you can learn to do by hand in many places, like the amazing book by Cox et al. called Ideals, Varieties and Algorithms). For example, using Mathematica you can compute:

In[1]:= GroebnerBasis[{
  u + v - 2,
  u x + v y - 1,
  u x^2 + v y^2 + 1,
  u x^3 + v y^3 + 5
  }, {u, v, x, y}
 ]                                                
                     2
Out[1]= {2 - 3 y + y , -3 + x + y, -7 + v + 4 y, 5 + u - 4 y}

The result is an equivalent system of equations. You'll notice that the first equation depends only on $y$, and that the other three allow you to determine $x$, $v$ and $u$, respectively, in terms of $y$.

The book I mentioned explains why this works.

Alternatively, you can use the (freely available, great) Macaulay2:

Macaulay2, version 1.3.1
with packages: ConwayPolynomials, Elimination, IntegralClosure, LLLBases, PrimaryDecomposition,
               ReesAlgebra, SchurRings, TangentCone

i1 : R = QQ[u,v,x,y,z];

i2 : I = ideal (u + v - 2, u*x + v*y-1, u*x^2+v*y^2+1, u*x^3+v*y^3+5);

o2 : Ideal of R

i3 : gens gb I

o3 = | x+y-3 v+4y-7 u-4y+5 y2-3y+2 |

             1       4
o3 : Matrix R  <--- R

The polynomials listed in the o3 line are a Groebner basis, i.e., an equivalent system of equations, and it allows you to solve it at once.

share|improve this answer
1  
i found the book and i;ll try to understand but the math in that book is way above my level. –  andrei Oct 16 '10 at 19:02
add comment

An elementary way would be:

Suppose $\displaystyle x$ and $\displaystyle y$ are roots of $\displaystyle z^2 + az + b = 0$.

Thus we have that $\displaystyle x^2 + ax + b = 0$ and $\displaystyle y^2 + ay + b= 0$.

Multiply the first by $\displaystyle u$, the second by $\displaystyle v$ and adding we get

$$-1 +a + 2b = 0$$

Mutiplying the first $ux$ and second by $vy$ and adding we get

$$-5 - a + b = 0$$

We can easily find $\displaystyle a$ and $\displaystyle b$ now and so can find the possibilities for $\displaystyle x$ and $\displaystyle y$.

It should be easy to solve the whole system now.

share|improve this answer
    
"Multiply the first by .. " which one ? –  andrei Oct 16 '10 at 19:11
    
@andrei: The first one? –  Mariano Suárez-Alvarez Oct 16 '10 at 19:14
    
@andrei: x^2+ax+b=0 is the first one and y^2+ay+b=0 is the second one. –  Aryabhata Oct 16 '10 at 19:14
add comment

Looking for linear terms suggests we write the system as

$$\begin{pmatrix} 1 & 1 \cr x & y \cr x^2 & y^2 \cr x^3 & y^3\end{pmatrix} \begin{pmatrix} u \cr v\end{pmatrix} =\begin{pmatrix} 2 \cr 1 \cr -1 \cr -5 \end{pmatrix}.$$

Row-reduction has to give two entirely zero rows of coefficients,yielding two equations for $x$ and $y$, one of which is linear in $y$. (It will help to recognize that $x-y$ is a factor of $x^2 - y^2$ and of $x^3 - y^3$.) That makes it straightforward to find $x$, from which you obtain $y$. With $x$ and $y$ in hand the coefficients are completely determined, allowing you to solve for $(u, v)$ in the usual ways.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.