Prove a fraction is a perfect square

[anemone]

If $x,\,y$ are positive integers such that $\dfrac{x^2+y^2}{1+xy}$ is an integer, then $\dfrac{x^2+y^2}{1+xy}$ is a perfect square.

 

[Albert1]

If $x,\,y$ are positive integers such that $\dfrac{x^2+y^2}{1+xy}$ is an integer, then $\dfrac{x^2+y^2}{1+xy}--(1)$ is a perfect square.

Spoiler

let :$x=\left | k^3 \right |,\,\ y=\left | k\right |$
or: $x=\left | k \right |,\, y=\left | k^3 \right |$
then :$(1)\,\,becomes :\,\, k^2$
where $ k \in Z$
and $k\neq 0$

 

[anemone]

Thanks for participating, Albert!

But I don't see how we can relate $x$ and $y$ in $k$ in such a manner. Do you mind to explain it for me? Thanks.:)

 

[Albert1]

Thanks for participating, Albert!

But I don't see how we can relate $x$ and $y$ in $k$ in such a manner. Do you mind to explain it for me? Thanks.:)

Spoiler

let :$\dfrac {x^2+y^2}{1+xy}=k^2$
we have:$x^2+y^2=k^2(1+xy)$
$=x^2(1+\dfrac {y^2}{x^2})$
let $x^2=k^2$ then $\dfrac {y^2}{x^2}=xy$
or $y=x^3$
for $x,y \in N$
we get :$x=\left | k \right | $
$y=\left | k^3 \right |$
because of symmetry $x ,\,and,\, y$ are interchangeable

 

[anemone]

Ah, I see what you meant now, thanks for the response. And thanks again to participating in my challenge.

 

[kaliprasad]

Spoiler

let :$\dfrac {x^2+y^2}{1+xy}=k^2$
we have:$x^2+y^2=k^2(1+xy)$
$=x^2(1+\dfrac {y^2}{x^2})$
let $x^2=k^2$ then $\dfrac {y^2}{x^2}=xy$
or $y=x^3$
for $x,y \in N$
we get :$x=\left | k \right | $
$y=\left | k^3 \right |$
because of symmetry $x ,\,and,\, y$ are interchangeable

Spoiler

by choosing the expression to be $x^2$ we are not considering all possible cases hence the given solution is wrong

 

[anemone]

Hmm...while I do have a solution that approached the problem quite different than Albert's, I think what Albert did is justifiable. But I could be wrong.

Do you have something, an example in mind to say that Albert has not included all possible cases in this problem? :)

And welcome back, kaliprasad! I was, initially, afraid you have gotten old of seeing my challenges and your return to MHB makes me very happy!

 

[kaliprasad]

Hmm...while I do have a solution that approached the problem quite different than Albert's, I think what Albert did is justifiable. But I could be wrong.

Do you have something, an example in mind to say that Albert has not included all possible cases in this problem? :)

And welcome back, kaliprasad! I was, initially, afraid you have gotten old of seeing my challenges and your return to MHB makes me very happy!

I have not claimed that other value is possible but without proving that other value is not possible we cannot assume so

 

[Opalg]

Hmm...while I do have a solution that approached the problem quite different than Albert's, I think what Albert did is justifiable. But I could be wrong.

Albert has shown that every perfect square can occur as a value of \(\displaystyle \frac{x^2+y^2}{1+xy}.\) That is a neat result. But it does not answer the given problem, which is to show that perfect squares are the only natural numbers that can arise in this way. I have tried hard, without any success, to prove that result, which is in a sense the converse of Albert's result. I should very much like to see a solution of it.

 

[Albert1]

if $\dfrac {x^2+y^2}{1+xy}=m\in N$
we have $x^2-mxy+y^2-m=0---(*)$
consider it as a polynomial respect to x with degree 2
then $x=\dfrac {my\pm \sqrt {m^2y^2-4(y^2-m)}}{2}$
for $x,y\in N$
we obtain $m=y^2$ and $x=my=y^3$
if we took (*) as a polynomial respect to y with degree 2 we have $m=x^2$ and $y=x^3$

 

[Nono713]

if $\dfrac {x^2+y^2}{1+xy}=m\in N$
we have $x^2-mxy+y^2-m=0---(*)$
consider it as a polynomial respect to x with degree 2
then $x=\dfrac {my\pm \sqrt {m^2y^2-4(y^2-m)}}{2}$
for $x,y\in N$
we obtain $m=y^2$ and $x=my=y^3$
if we took (*) as a polynomial respect to y with degree 2 we have $m=x^2$ and $y=x^3$

What about the solution $(8, 30)$? In that case we have:

$$\frac{8^2 + 30^2}{1 + 8 \cdot 30} = \frac{964}{241} = 4 = 2^2$$

Yet $8^3 \ne 30$. Below is a dump of all the admissible values of $x$ and $y$, written as $(x, y)$ with $x < y < 1000$:

(1, 1)
(2, 8)
(3, 27)
(4, 64)
(5, 125)
(6, 216)
(7, 343)
(8, 30)
(8, 512)
(9, 729)
(27, 240)
(30, 112)
(112, 418)

As you can see, most of the pairs here are of the form $(u, u^3)$, but there are four "rogue" pairs that are not of that form. I observe that each positive integer $u$ spawns a unique chain of solutions. And, in fact, starting from any integer $u$ and its associated trivial solution $(u, u^3)$, those chains of solutions obey a simple recurrence of the form:

$$(m, n) \implies (n, u^2 n - m)$$

For instance, taking $u = 2$, we get:

$$(2, 8) \implies (8, 30) \implies (30, 112) \implies (112, 418) \implies (418, 1560) \implies \cdots$$

And note that $2^2 \cdot 8 - 2 = 30$, $2^2 \cdot 30 - 8 = 112$, $2^2 \cdot 112 - 30 = 418$, $2^2 \cdot 418 - 112 = 1560$.

Another example, with $u = 3$, we get:

$$(3, 27) \implies (27, 240) \implies (240, 2133) \implies \cdots$$

And, as expected, $3^2 \cdot 27 - 3 = 240$, $3^2 \cdot 240 - 27 = 2133$.

This, of course, is a strict superset of the solutions given by Albert, and seems to be the dominant structure of the set of solutions. I conjecture that all solutions are of this form (exist in a chain for some $u \in \mathbb{N}$), and will try to find a proof of this. Perhaps an inductive proof might work, after showing that all chains are infinite and disjoint, if they are. I feel that this problem is actually pretty hard, but should we all fail to solve the challenge I look forward to anemone's solution which will without doubt be short and elegant :)

 

[Nono713]

Got it, I think. There are probably a few aspects of the proof that could be clarified or are a bit handwavy, but I think the approach is understandable enough.

Spoiler

First assume $m < n$, without loss of generality, as the only solution of the form $(m, m)$ is $(1, 1)$ since if $1 < m < n$ then $mn < n^2$ hence $m^2 + n^2 \ne 1 + mn$. The other solutions for $m > n$ can be obtained by symmetry. Therefore, suppose we have a solution $(m, n)$ with $1 < m < n$ such that:

$$\frac{m^2 + n^2}{1 + mn} = r > 1 ~ ~ ~ \iff ~ ~ ~ m^2 + n^2 = r(1 + mn)$$

Then it is easy to observe that $(rm - n, m)$ is also a solution, as:

$$(rm - n)^2 + m^2 = r^2 m^2 - 2 r m n + n^2 + m^2 = r(r m^2 - m n + 1) = r((r m - n)m + 1)$$

And $(r m - n)m + 1 \ne 0$ since $r > 1$ and so:

$$\frac{(rm - n)^2 + m^2}{1 + (rm - n)m} = r$$

Thus if we apply this formula repeatedly we can generate a sequence of solutions for which the fraction also equals $r$. We must show that for every solution $(m_k, n_k)$ in the sequence, the property that $0 \leq m_k < n_k$ is maintained. We also prove this by induction, by posing:

$$r = \frac{m^2 + n^2}{1 + mn} = \frac{\frac{m^2}{n} + n}{\frac{1}{n} + m} < \frac{\frac{m^2}{n} + m}{m}$$

Hence:

$$rm < \frac{m^2}{n} + m < n + m$$

Which holds since $m < n$, and therefore:

$$rm - n < m$$

By induction, this holds for every term of the series. Furthermore, the lower bound for $rm - n$ tends to zero as $m$ and $n$ get smaller and thus closer to each other, such that $m_k \geq 0$ in the limit. We have thus shown that the sequence is strictly decreasing, and that we will therefore eventually arrive at a solution of the form $(0, s)$ for some integer $s > 0$. As we have proven, the fraction for this term must equal $r$ too, so:

$$\frac{0^2 + s^2}{1 + 0 \cdot s} = r$$

In other words, $s^2 = r$, and so $r$ was a square.
​

 

[anemone]

Interesting and thorough proof,(Yes) thanks Bacterius!

Now it is my turn to show another proof (that I saw somewhere online) here:

Spoiler

Suppose that $\dfrac{x^2+y^2}{1+xy}=k$ is a counterexample of an integer which is not a perfect square, with max $(x,\,y)$ as small as possible. We may assume WLOG that $x<y$ for if $x=y$, then

$0<\dfrac{2x^2}{1+x^2}=k<2$ which forces $k=1$, a perfect square.

Now, $x^2+y^2-k(1+xy)=0$ is a quadratic in $y$, $y^2-kxy+x^2-k=0$. Let $y_1,\,y$ be its roots, so $y_1+y=kx$ and $y_1y=x^2-k$.

As $x,\,k$ are positive integers, suppose $y_1<0$ is incompatible with $x^2+y_1^2=k(1+xy_1)$. As $k$ is not a perfect square, suppose $y_1=0$ is incompatible with $x^2+0=k(1+0\cdot x)$.

Also, $y_1=\dfrac{x^2-k}{y}<\dfrac{y^2-k}{y}<y$

Thus, we have found another positive integer $y_1$ for which $\dfrac{x^2+y_1^2}{1+xy_1}=k$ and which is smaller than the smallest max $(x,\,y)$. This is a contradiction.

It must be the case, then, that $k$ is a perfect square.