# Thread: Diophantine Equation

1. ## Diophantine Equation

I need help solving this Diophantine Equation I have. Its X^2+Y^2+1=3XY
The answers must be integers and the only one I found was x=1, y=1.

2. Originally Posted by Liu997
I need help solving this Diophantine Equation I have. Its X^2+Y^2+1=3XY
The answers must be integers and the only one I found was x=1, y=1.
$\displaystyle x^2+y^2+1=3xy \implies y=\frac{3x\pm\sqrt{5x^2-4}}{2}$

This means $\displaystyle 5x^2-4$ must be square and $\displaystyle 3x\pm\sqrt{5x^2-4}$ must be even to have a solution.

So, $\displaystyle x=\pm 1, \pm 2, \pm 5$ are some solutions...

3. Originally Posted by chiph588@
$\displaystyle x^2+y^2+1=3xy \implies y=\frac{3x\pm\sqrt{5x^2-4}}{2}$

This means $\displaystyle 5x^2-4$ must be square and $\displaystyle 3x\pm\sqrt{5x^2-4}$ must be even to have a solution.

So, $\displaystyle x=\pm 1, \pm 2, \pm 5$ are some solutions...
But I need the x and y variables that work even though they are interchangeable in this equation. I found another one using excel x=5, y=2

I bow down to who can give me like a reason for this

4. Originally Posted by Liu997
But I need the x and y variables that work even though they are interchangeable in this equation. I found another one using excel x=5, y=2

I bow down to who can give me like a reason for this
I don't quite know what you just said here...

We can narrow down some possible solutions by looking modulo $\displaystyle n$.

Looking modulo $\displaystyle 3$:
$\displaystyle 3xy\equiv0\mod{3}\implies x^2+y^2+1\equiv0\mod{3}\implies x^2,y^2\equiv1\mod{3}\implies x$ and $\displaystyle y$ can't be multiples of $\displaystyle 3$.

I'll let you know of any more progress I make.

5. Originally Posted by chiph588@
$\displaystyle x^2+y^2+1=3xy \implies y=\frac{3x\pm\sqrt{5x^2-4}}{2}$

This means $\displaystyle 5x^2-4$ must be square and $\displaystyle 3x\pm\sqrt{5x^2-4}$ must be even to have a solution.

So, $\displaystyle x=\pm 1, \pm 2, \pm 5$ are some solutions...
I claim $\displaystyle 3x\pm\sqrt{5x^2-4}$ will always be even (can you see why?), so we don't need to worry about that.

So solving our equation is equivalent to solving $\displaystyle 5x^2-n^2=4$ (This almost looks like Pell's equation!).

6. Here's all the solutions for $\displaystyle |x| \leq 1000$:

$\displaystyle x= \pm610,\pm233,\pm89,\pm34,\pm13,\pm5,\pm2,\pm1$

7. Break through!

Let's just look at the solutions when $\displaystyle x$ is positive.

Let $\displaystyle \{x_1,x_2,\cdot\cdot\cdot,x_n,\cdot\cdot\cdot\}$ be all ordered $\displaystyle x$ solutions i.e. $\displaystyle x_1=1, x_2=2, x_3=5,...$

I claim the solutions for $\displaystyle y$ paired with $\displaystyle x_n$ is $\displaystyle y=x_{n-1},x_{n+1}$. (Can you see why?)

This is big because now we can find all solutions quite easily!

$\displaystyle x_{n+1} = \frac{3x_n+\sqrt{5x_n^2-4}}{2}$. Let's see if you can find the formula for $\displaystyle x_n$ now.

8. Originally Posted by chiph588@
Here's all the solutions for $\displaystyle |x| \leq 1000$:

$\displaystyle x= \pm610,\pm233,\pm89,\pm34,\pm13,\pm5,\pm2,\pm1$
Those are the even-labeled Fibonacci numbers!

9. Originally Posted by Bruno J.
Those are the even-labeled Fibonacci numbers!
Precisely! (Well almost: You mean odd-labeled Fibonacci numbers.)

Now I guess all that's left is to show the odd-labeled Fibonacci numbers satisfy $\displaystyle x_{n+1} = \frac{3x_n+\sqrt{5x_n^2-4}}{2}$.

I'm having a lot of trouble showing this though... what's your take on this?

10. Originally Posted by chiph588@
Precisely! (Well almost: You mean odd-labeled Fibonacci numbers.)
I count from zero!

Now I guess all that's left is to show the odd-labeled Fibonacci numbers satisfy $\displaystyle x_{n+1} = \frac{3x_n+\sqrt{5x_n^2-4}}{2}$.

I'm having a lot of trouble showing this though... what's your take on this?
I haven't tried yet; I've got too many things to do tonight! No good idea comes to mind though. I'll give it a shot tomorrow if I can.

11. Originally Posted by Bruno J.
I count from zero!

I haven't tried yet; I've got too many things to do tonight! No good idea comes to mind though. I'll give it a shot tomorrow if I can.
Yeah, I've been too busy to hit this head on too...

12. Originally Posted by chiph588@
Precisely! (Well almost: You mean odd-labeled Fibonacci numbers.)

Now I guess all that's left is to show the odd-labeled Fibonacci numbers satisfy $\displaystyle x_{n+1} = \frac{3x_n+\sqrt{5x_n^2-4}}{2}$.

I'm having a lot of trouble showing this though... what's your take on this?
One more thing: you need to show this is the only sequence that generates positive solutions. I've figured out a way, but let's see you try first.

We want to show $\displaystyle F_{2n+3}=\frac{3F_{2n+1}+\sqrt{5F_{2n+1}^2-4}}{2}$.

Now $\displaystyle F_{2n+3} = F_{2n+2}+F_{2n+1} = F_{2n+1}+F_{2n}+F_{2n+1} = 2F_{2n+1}+F_{2n}$.

Therefore it suffices to show $\displaystyle \sqrt{5F_{2n+1}^2-4} = F_{2n+1}+2F_{2n}$. (Can you see why?)

So... $\displaystyle \sqrt{5F_{2n+1}^2-4} = F_{2n+1}+2F_{2n} \iff F_{2n+1}F_{2n}+F_{2n}^2 = F_{2n+1}^2-1$.

This last result can be shown inductively (I omit the details, but have verified it).

Since we know this is the only sequence of positive integers that satisfies this equation, we have all solutions to $\displaystyle x^2+y^2+1=3xy$ with $\displaystyle x>0$:
$\displaystyle (x,y) = \{(F_{2n+1},F_{2n-1}),\; (F_{2n+1},F_{2n+3}) \;|\; n\geq0\}$. (When $\displaystyle n=0$, $\displaystyle F_{2n-1} = F_{-1} = 1$.)
The solutions with $\displaystyle x<0$ follow analogously.

13. Thanks guys. I also see that this equation is very related to
$\displaystyle X^2+Y^2+2=XYZ$ which was what I actually need to solve and find relations to the Fibonacci sequence.

14. Originally Posted by Liu997
Thanks guys. I also see that this equation is very related to
$\displaystyle X^2+Y^2+2=XYZ$ which was what I actually need to solve and find relations to the Fibonacci sequence.
Well excel's telling me there's only solutions when $\displaystyle z=\pm4$. If only this was a proof!

So I'd say this is going to be a two step process:

1.) Show $\displaystyle z=\pm4$ generates the only solutions.

2.) Find these solutions.

15. I already did use the excel to show the answers for that equation. Since I received this Equation as an assignment, I could really use some help. My teacher pointed me to the direction of assigning Fibonnacci numbers as algebraic expressions. Sorry for the late responses I usually don't have access to a computer regularly.