# system of equations

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

-
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

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

-
definitely the best way to solve it by far. – Eugene Bulkin Oct 17 '10 at 3:27
@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
@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
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
@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 where I stressed the key role played by the orbit decomposition of the shift map when solving recurrences in rational function fields. – Bill Dubuque Oct 18 '10 at 3:21

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.

-
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

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.

-
"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

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.

-

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.

-