# Prove that $2xy\mid x^2+y^2-x$ implies $x$ is a perfect square.

Prove that $2xy\mid x^2+y^2-x$ implies $x$ is a perfect square.
My work:
$2xy\mid x^2+y^2-x \implies x^2+y^2-x=2xy\cdot k$
So,$x^2+y^2+2xy-x=(x+y)^2-x=2xy \cdot (k+1)$
And,$x^2+y^2-2xy-x=(x-y)^2-x=2xy \cdot (k-1)$
I found that for $x,y$ both odd, no solution exists. For $x$ even, and $y$ odd,no solution exists. Solution exists only for $x$ odd, $y$ even and $x$ even and $y$ even solution exists. Cannot do anything more. Please help!

-
Have you proved that solutions exist or just that they might? – Daniel Littlewood Feb 4 '14 at 13:30
Do you know the Vieta Root Jumping technique? Hm, not sure if this will work though. – Calvin Lin Feb 4 '14 at 13:33
I found that solutions might exist...actually I can prove that solutions exist for which cases. – Hawk Feb 4 '14 at 13:33
Where did you get this question from? It's a good one. – Zafer Cesur Feb 4 '14 at 20:03

We use the following

Fact: A non-zero integer is a perfect square (by that I mean a number of the form $k^2$ or $-k^2$) if and only if in its prime factorization, the exponent of every prime factor is even.

Now let $p$ be any prime factor of $x$ and $k$ the exponent of $p$ in the prime factorization of $x$. If $k$ is even, there is nothing to show. So assume that $k$ is odd: $k=2j+1$.

Then $p^k|x|2xy|x^2+y^2-x$. Since $p^k|x^2-x$, it must also hold that $p^{2j+1}=p^k|y^2$. Since $y^2$ is a square, also $p^{k+1}=p^{2j+2}|y^2$.

But then $p^{k+1}|2xy|x^2+y^2-x$. But since $p^{k+1}|x^2+y^2$, it also follows that $p^{k+1}|x$. This is a contradiction (we assumed that $k$ is the exponent of $p$ in the factorization of $x$).

Since $p$ was an arbitrary prime factor, the exponents of all prime factors in the prime factorization of $x$ are even, i.e. $x$ is a square in the above sense.

Edit: Made precise what is meant by a square.

-
But, $p$ is just a single prime factor? There can be more...how will you explain that? – Hawk Feb 4 '14 at 14:17
@Hawk This holds for every prime factor. $p$ is an arbitrary prime factor. – Your Ad Here Feb 4 '14 at 14:21
Remark $\$ This essentially uses a $local$ (prime at a time) proof of the GCD Freshman's Dream $\,(a^2,b^2) = (a,b)^2.\,$ Using the global dream form, the proof is a one-liner - see my answer. – Bill Dubuque Feb 5 '14 at 14:53
To be correct, the Fact needs to be restricted to postive integers. As such, does the above method not work for $\ x < 0\,?\$ (I didn't check) – Bill Dubuque Apr 18 '14 at 15:01
For negative $x$ my argument shows that $x=-k^2$ for some integer $k$. So either we call that also "a perfect square" for the purpose of this exercise, or we declare the problem wrong for negative $x$. – Your Ad Here Apr 19 '14 at 8:02

Observe that $\ x\mid y^2\,$ and $\ x = (x\!-\!ky)^2+(1\!-\!k^2)y^2\ ( =\, x^2\!+y^2-2kxy,\ k\in\Bbb Z).\$ Now apply

Theorem $\quad\, n\mid y^2\,$ and $\ n = z^2\!+ay^2\,\Rightarrow\, n\, =\, \pm (z,y)^2$

Proof $\ \pm n = (n,y^2) = (z^2\!+ay^2,y^2) = (z^2,y^2) = (z,y)^2\,$ by GCD Freshman's Dream $\$ QED

-
(+1) Very cool. I wasn't aware that one can do arithmetic so nicely with GCDs. – Your Ad Here Feb 5 '14 at 15:56
@TooOldForMath I expanded the linked answer to include a link to another answer that elaborates more on gcd arithmetic. This arithmetic is quite natural (and powerful!) once one has a little experience with it. – Bill Dubuque Feb 5 '14 at 19:21
It's a bit late,but what was your inspiration behind expressing $x$ in such a convenient way? – rah4927 Apr 18 '14 at 14:26
@rah One simple view is that I completed the square so that I could apply well-known results on (primitive) representation of integers by binary quadratic forms. – Bill Dubuque Apr 18 '14 at 14:55