5
$\begingroup$

This is some old Olympiad problem (I vaguely remember its Iranian )

I factorised it as

$ (x-y)(3x + 3y +1) = y^2 $

Then I fruitlessly tried to prove

$\gcd(x-y, 3x + 3y +1 ) = \gcd (6x+1,6y+1) = 1$

for proving that $x-y$ is a perfect square.

How do I continue my method or are there other ways to approach this intuitively?

$\endgroup$

2 Answers 2

8
$\begingroup$

Defining $z = x-y$, from $y^2 = (x-y)(3x + 3y +1)$, we have $$ y^2 = 3z^2 + 6yz+ z$$ which is equivalent to $$(y - 3z)^2 = z(12z+1).$$

Since $\gcd(z, 12z+1)=1 $, $z$ and $12z+1$ both must be perfect squares.

$\endgroup$
1
  • 1
    $\begingroup$ :Very nice answer. $\endgroup$
    – Khosrotash
    Jan 29, 2017 at 5:37
4
$\begingroup$

Here is the method to approach this sort of problem. Note that $x>y$. Let $\gcd(x,y)=d$. Now, first note that $$x-y=4y^2-3x^2 \equiv 0 \pmod{d^2} \tag{1}$$ Now, $$4y^2-3x^2=4(y-x)(y+x)+x^2 \equiv 0 \pmod {x-y} $$ And $$4y^2-3x^2=3(y-x)(y+x)+y^2 \equiv 0 \pmod {x-y} $$ This gives us that $x-y$ is a common factor of $x^2$ and $y^2$, so it must divide their greatest common divisor, $d^2$. So we have $$d^2 \equiv 0 \pmod{x-y}$$ So $d^2$ and $x-y$ both divide each other. Since $x>y$, we have that $x-y=d^2$. Our proof is done.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.