Divisibility problem (number theory, I believe)

[Greg]

Let $x$ and $y$ be positve integers such that $xy$ divides $x^2+y^2+1$. Show that $$\frac{x^2+y^2+1}{xy}=3$$

 

[mente oscura]

Let $x$ and $y$ be positve integers such that $xy$ divides $x^2+y^2+1$. Show that $$\frac{x^2+y^2+1}{xy}=3$$

Hello.

Spoiler

Vieta jumping - Wikipedia, the free encyclopedia

Regards.

 

[MarkFL]

Hello.

Spoiler

Vieta jumping - Wikipedia, the free encyclopedia

Regards.

It is fine to use a link to back up or justify a technique, but can you show how would apply that to solve the problem?

 

[mente oscura]

It is fine to use a link to back up or justify a technique, but can you show how would apply that to solve the problem?

I sit it. I thought that it was a doubt of someone, but, later, I saw that it was a game. Because of it I edited, to add the spoiler.

Regards.

 

[Nono713]

Let $x$ and $y$ be positve integers such that $xy$ divides $x^2+y^2+1$. Show that $$\frac{x^2+y^2+1}{xy}=3$$

(note: this solution has a mistake, see Opalg's post below)

Spoiler

Suppose that for some positive integers $x, y, k$ with $xy > 1$ we have:
$$\frac{x^2 + y^2 + 1}{xy} = k ~ ~ ~ \iff ~ ~ ~ x^2 + y^2 + 1 = kxy$$
Note that we can take away two $xy$ terms from the RHS to get:
$$x^2 - 2xy + y^2 + 1 = (k - 2)xy$$
Which gives us the factorization:
$$(x - y)^2 + 1 = (k - 2)xy$$
Now for the key step: $(x - y)^2$ cannot be any larger than $xy$, because $\lvert x - y \rvert \leq x$ and $\lvert x - y \rvert \leq y$ thus $(x - y)^2 \leq xy$, and hence $(x - y)^2 + 1 < 2xy$ as $xy > 1$. Therefore to achieve equality we must have $xy$ on the RHS. Hence $k - 2 = 1$ and it follows $k = 3$ for $xy > 1$. It remains to check the case $xy = 1$, that is, $(x, y) = (1, 1)$, which can be seen to yield $k = 3$ as well, and the proof is complete. $\blacksquare$

 

[topsquark]

Let $x$ and $y$ be positve integers such that $xy$ divides $x^2+y^2+1$. Show that $$\frac{x^2+y^2+1}{xy}=3$$

I'm trying a brute force approach and I've got that a = 3n, for n = 1, 2, 3...

It's a pain to work out and I'm solving Diophantine equations to try to find a value for n. So far I've gotten n = 1 has solutions. Still working on other n values. I know the problem has been solved by Bacterius, but
I. Can't. Let. It. Go!

I hate you. (Swearing)

-Dan

 

[Opalg]

There is one step in Bacterius's solution that I don't follow.
[sp]

Now for the key step: $(x - y)^2$ cannot be any larger than $xy$, because $\lvert x - y \rvert \leq x$ and $\lvert x - y \rvert \leq y$

If $x\geqslant y\geqslant0$ then clearly $\lvert x - y \rvert \leqslant x$. But I don't see why $\lvert x - y \rvert \leqslant y$. For example, if $y=1$ and $x=3$ then $|x-y| = 2$, which is greater than $y$. Am I missing something here? [/sp]

 

[Nono713]

There is one step in Bacterius's solution that I don't follow.
[sp]
If $x\geqslant y\geqslant0$ then clearly $\lvert x - y \rvert \leqslant x$. But I don't see why $\lvert x - y \rvert \leqslant y$. For example, if $y=1$ and $x=3$ then $|x-y| = 2$, which is greater than $y$. Am I missing something here? [/sp]

Hm, you are correct. There is a mistake. I am not sure if it can be salvaged based on this but I will make a note in my post in the meantime.

Spoiler

I suppose if we add the condition that $y \geq 2x$ then that step would follow, but of course then it needs to be shown that there are no solutions with $y < 2x$ (for any $k$, not just 3, unfortunately).

 

[Albert1]

Let $x$ and $y$ be positve integers such that $xy$ divides $x^2+y^2+1$. Show that $$\frac{x^2+y^2+1}{xy}=3$$

Spoiler

let :$\dfrac {x^2+y^2+1}{xy}=k--(1)$
we know :$k$ must be odd ,and $k>2$
if $x=y=1$ then $k=3$
because of symmetry we let $x<y$
now we create two sequences $a_n,b_n\in N$
from (1) we have :$x^2-kxy+y^2+1=0----(2)$
the solution of (2) will be:
$x=a_1=1,\,\,\,\,\,\,\,\,\,\,\,\,\,\,y=b_1=2$
$x=a_2=2=b_1,y=b_2=5$
$x=a_3=5=b_2,y=b_3=13$
-----
-----

$x=a_n=b_{n-1} ,y=b_n=\dfrac {kx+\sqrt {k^2x^2-4(x^2+1)}}{2}--(3)$
if you want to find $y=b_n$ ,then $x=a_n=b_{n-1}$
exam $b_2=5=a_3=\dfrac {2k
+ \sqrt {4k^2-20}}{2}$
in order to find :$b_2$ ,$x$ in (3) should be replaced by $b_1=2$
$\therefore k=3$
and the proof is done

 

[topsquark]

I'm confused.

Spoiler

now we create two sequences $a_n,b_n\in N$
$x^2-kxy+y^2+1=0----(2)$
the solution of (2) will be:
$x=a_1=1,\,\,\,\,\,\,\,\,\,\,\,\,\,\,y=b_1=2$
$x=a_2=2=b_1,y=b_2=5$
$x=a_3=5=b_2,y=b_3=13$

How do you know what the series must be if you don't already know k? For instance, how do you know k = 5 doesn't work?

-Dan

 

[Albert1]

I'm confused.

Spoiler

How do you know what the series must be if you don't already know k? For instance, how do you know k = 5 doesn't work?

-Dan

gven :$x,y\in N$
to prove :$\dfrac {x^2+y^2+1}{xy}=k(constant)\in N---(1)$
from (1) we have:
$x^2-kxy+y^2+1=0----(2)$
if $x<y$
for the same value of $k$ ,the soltions of (1)=the solutions of (2) will be :
$x \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\, y$
$a_1\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,b_1$
$a_2=b_1\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,b_2$
$a_3=b_2\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,b_3$
-----
-----
$a_n=b_{n-1}\,\,\,\,\,\,\,\,\,b_n$
for $n=1,2,3------, a_n=b_{n-1}<b_n$
and :
$y=b_{n-1}=a_n=\dfrac{kx+\sqrt {k^2x^2-4(x^2+1)}}{2}-----(*)$
for the same value of $k$ (*) must be all satisfied,and then we can find $k$

 

[topsquark]

gven :$x,y\in N$
to prove :$\dfrac {x^2+y^2+1}{xy}=k(constant)\in N---(1)$
from (1) we have:
$x^2-kxy+y^2+1=0----(2)$
if $x<y$
for the same value of $k$ ,the soltions of (1)=the solutions of (2) will be :
$x \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\, y$
$a_1\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,b_1$
$a_2=b_1\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,b_2$
$a_3=b_2\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,b_3$
-----
-----
$a_n=b_{n-1}\,\,\,\,\,\,\,\,\,b_n$
for $n=1,2,3------, a_n=b_{n-1}<b_n$
and :
$y=b_{n-1}=a_n=\dfrac{kx+\sqrt {k^2x^2-4(x^2+1)}}{2}-----(*)$
for the same value of $k$ (*) must be all satisfied,and then we can find $k$

Let me make my question a bit clearer. You previously generated a list of a_n and b_n. What you seemed to be doing was specifying a series a_n(k) and b_n(k). For the series you gave k = 3. But if k = 6 you would not generate that same series. Yes, I know there isn't one, but you haven't shown it won't work that way.

-Dan

 

[Albert1]

Let me make my question a bit clearer. You previously generated a list of a_n and b_n. What you seemed to be doing was specifying a series a_n(k) and b_n(k). For the series you gave k = 3. But if k = 6 you would not generate that same series. Yes, I know there isn't one, but you haven't shown it won't work that way.

-Dan

Spoiler

View attachment 3467
here x<y
only k=3 will satisfy both (3) and (4)

 

[topsquark]

Spoiler

Okay, now I see what you are doing. Sorry about that. Still, as convincing as the Math is here there is still no reason to say that there isn't a set of values where k is not 3. (I don't mean to be a (Swearing) about this...I'm just trying to see the logic behind it.)

-Dan

 

[Albert1]

$x^2 \,\,mod \,\,3 =0 \,\,\,\, or \,\, 1$
$y^2 \,\,mod \,\,3 =0 \,\, \,\, or \,\, 1$
in this case 0 will be deleted,so we let :
$x=3p\pm 1$
$y=3q\pm 1$ ($p,q\in N \,\ and \, \,p<q$)
for we set $x<y$
this may give us a hint to prove $k=3$ is the only answer

I am thinking----

 

[topsquark]

$x^2 \,\,mod \,\,3 =0 \,\,\,\, or \,\, 1$
$y^2 \,\,mod \,\,3 =0 \,\, \,\, or \,\, 1$
in this case 0 will be deleted,so we let :
$x=3p\pm 1$
$y=3q\pm 1$ ($p,q\in N \,\ and \, \,p<q$)
for we set $x<y$
this may give us a hint to prove $k=3$ is the only answer

I am thinking----

It's a good approach. I worked it out and it says that k must be divisible by 3. I'm going nuts to find a way to narrow that down to k = 3, but with little no real success...I can disprove some k values, but it's nothing like a proof. I like bacterius' solution (I think it's fixed now?), but your approach is closer to mine. Which is why I'm picking your proof apart...it might lead to something I can use in my work.

-Dan

 

[Nono713]

It's a good approach. I worked it out and it says that k must be divisible by 3. I'm going nuts to find a way to narrow that down to k = 3, but with little no real success...I can disprove some k values, but it's nothing like a proof. I like bacterius' solution (I think it's fixed now?), but your approach is closer to mine. Which is why I'm picking your proof apart...it might lead to something I can use in my work.

-Dan

Spoiler

Mine is not fixed, I have not had the time to work on it (exams and stuff). It "works" for all solutions where $y \geq 2x$ (or $x \geq 2y$ by symmetry) as far as I can tell, but I don't know how to prove that all solutions have to satisfy that anyway. It may not be able to be salvaged, unfortunately.

 

[Opalg]

Let $x$ and $y$ be positve integers such that $xy$ divides $x^2+y^2+1$. Show that $$\frac{x^2+y^2+1}{xy}=3$$

[sp]
Suppose that there are positive integers $x$, $y$ and $k$ such that $$\frac{x^2+y^2+1}{xy}=k.$$ Write the equation as $x^2 -kyx + (y^2+1) = 0.\quad(*)$

Keeping $k$ fixed, let $(x_0,y_0)$ be a solution of (*) for which $y_0$ is as small as possible. Since $(y_0,x_0)$ is also a solution, it follows that $x_0\geqslant y_0.$

With $y=y_0$, (*) is a quadratic equation in $x$. One of the solutions is $x_0$. Let $x_1$ be the other solution. Then the sum of the solutions is $x_0+x_1 = ky_0$. Since $x_0$ and $ky_0$ are integers, it follows that $x_1$ is an integer. The product of the solutions is $x_0x_1 = y_0^2+1$. Since $x_0$ and $y_0^2+1$ are positive, it follows that $x_1$ is positive.

Therefore $(x_1,y_0)$ is a positive integer solution of (*) (and so is $(y_0,x_1)$), and it follows from the minimality of $y_0$ that $x_1\geqslant y_0$.

We now have two solutions $(x_0,y_0)$ and $(x_1,y_0)$, with $x_0\geqslant y_0$ and $x_1\geqslant y_0$. Suppose that one (or both) of those inequalities is strict, say $x_1>y_0$. Then $x_1\geqslant y_0+1$, and $$x_0x_1 \geqslant y_0(y_0+1) = y_0^2 + y_0 \geqslant y_0^2+1 = x_0x_1.$$ Since the first and last terms in that string of inequalities are equal, it follows that there must be equality throughout. In particular, $x_0 = y_0 = 1$. But then $k = \dfrac{x_0^2+y_0^2+1}{x_0y_0} = 3.$
The only other possibility is that both the inequalities $x_0\geqslant y_0$ and $x_1\geqslant y_0$ are in fact equalities, so that $x_0 = x_1 = y_0.$ But then $k = \dfrac{2y_0^2+1}{y_0^2} = 2 + \dfrac1{y_0^2}.$ The only way that can be an integer is if $y_0=1$, which again leads to the conclusion that $k=3$.

I assume that mente oscura's hint in comment #2 above is meant to point towards that sort of proof. Starting from one solution of (*), the two solutions to the quadratic equation give rise to an infinite ladder of solutions $(x_n,y_n)$, as in Albert's comments. The key idea in the solution is that instead of climbing up this ladder to get larger and larger solutions, you should go down to the foot of the ladder. That leads inevitably to the minimal solution $x=y=1$, with the consequence that $k=3$.[/sp]

 

[Albert1]

Spoiler

$\dfrac {x^2+y^2+1}{xy}=k----(1)$

$let :x^2=3p+1,\,\, and \,, y^2=3q+1$

then (1) becomes:

$k=\dfrac{3(p+q+1)}{\sqrt{3p+1}\times
{\sqrt{3q+1}}}$

now we will prove:

if both $3p+1, \,\,and \,\,

3q+1$ are perfect square then :

$\sqrt {3p+1}\times\sqrt {3q+1}

=p+q+1----(2) \,\, (p<q,\,\,\,or, \,\,p>q,\,\,if\,\,\, p,q\,\,\,\neq 0)$

this includes :$p=q=0$

then :$x=y=1$

now it is turn to try (2)

I think (2) will be easier