Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
