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$
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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ :Very nice answer. $\endgroup$ – Khosrotash Jan 29 '17 at 5:37
3
$\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.

| cite | improve this answer | |
$\endgroup$

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.