2
$\begingroup$

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

  • 0
    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.2010-10-16
  • 0
    ok i'll try again, i must have miscalculated2010-10-16

5 Answers 5

8

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

  • 0
    definitely the best way to solve it by far.2010-10-17
  • 2
    @Eugene, it requires *thinking*. I prefer methods that do not demand so much of myself!2010-10-17
  • 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.2010-10-17
  • 0
    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.2010-10-18
  • 0
    @Moron: Whenever there is innate symmetry it is essential to bring it to the surface since it may play a key role in the solution. E.g. recall our [prior discussion](http://math.stackexchange.com/questions/4150) where I stressed the key role played by the orbit decomposition of the shift map when solving recurrences in rational function fields.2010-10-18
  • 0
    @Moron: I can't say I've ever encountered a "little symmetry". Whenever they occur they usually play a significant role. When teaching I (over-) emphasize it on simple problems because they provide the best contexts to learn the paradigm. If one doesn't master the technique on simple problems then one will have no hope of picking it up on-the-fly in more complex contexts.2010-10-18
7

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.

  • 1
    i found the book and i;ll try to understand but the math in that book is way above my level.2010-10-16
5

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.

  • 0
    "Multiply the first by .. " which one ?2010-10-16
  • 0
    @andrei: The first one?2010-10-16
  • 0
    @andrei: x^2+ax+b=0 is the first one and y^2+ay+b=0 is the second one.2010-10-16
2

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.

0

Actually, this problem reminds me of linear recurrences that are based on the previous 2 terms (since that is how a linear recurrence is represented): in the form $ax^k+by^k$.

So basically the linear recurrence is in the form $a_n=pa_{n-1}+qa_{n-1}$ with set values at $a_0$ and $a_1$.

Here, $a_0=2$, $a_1=1$, $a_2=-1$, $a_3=-5$. $a_2=pa_1+qa_0 \rightarrow -1=p+2q$. $a_3=pa_2+qa_1=-5=-p+q$.$5=p-q$ Then solve them to get $q=-2$ and $p=3$.

Thus the recurrence is $a_n=3a_{n-1}-2a_{n-2}$.

but I'm not really sure if method will work.