Solve in integers the equation \[ x^2+xy+y^2 = \left(\frac{x+y}{3}+1\right)^3. \]
Problem
Source: USAMO 2015 Problem 1, JMO Problem 2
Tags: USA(J)MO, USAMO, Diophantine equation, USAJMO, algebra, number theory, Hi
29.04.2015 00:15
What I did on this problem is setting $x+y=3k$, and using a quadratic to find $x$. The discriminant evaluates to $(k-2)^2(4k+1)$, which must be a perfect square. After a bit of substitution, I got that $(x,y)=(n^3+3n^2-1,-n^3+3n+1)$. Is this how y'all did it?
29.04.2015 00:15
Yeah, but the answer looked insane. Did the same thing alex, used the quadratic formula and different variable names though.
29.04.2015 00:17
I didn't find it *that* easy for JMO. Maybe for USAMO. Also rawr elliptic curves. We do the trick of setting $a=x+y$ and $b=x-y$. This rewrites the equation as \[ \frac14\left( (a+b)^2+(a+b)(a-b)+(a-b)^2 \right) = \left( \frac a3 + 1 \right)^3 \] where $a,b \in \mathbb Z$ have the same parity. This becomes \[ 3a^2+b^2 = 4\left( \frac a3 + 1 \right)^3 \] which is enough to imply $3 \mid a$, so let $a = 3c$. Miraculously, this becomes \[ b^2 = (c-2)^2 (4c+1). \] So a solution must have $4c+1=m^2$, with $m$ odd. This gives \[ x = \frac 18 \left( 3 (m^2-1) \pm (m^3-9m) \right) \quad\text{and}\quad y = \frac 18 \left( 3 (m^2-1) \mp (m^3-9m) \right). \] For mod $8$ reasons, this always generates a valid integer solution, so this is the complete curve of solutions. Actually, putting $m=2n+1$ gives the much nicer curve \[ \boxed{x = n^3+3n^2-1 \quad\text{and}\quad y = -n^3+3n+1} \] and permutations. For $n=0,1,2,3$ this gives the first few solutions of $(-1,1)$, $(3,3)$, $(19,-1)$, $(53, -17)$, and permutations.
29.04.2015 00:21
I left the cubics in factored form; would I still get full points? Plus my equation is a bit different I probably did something wrong oops
29.04.2015 00:21
This is USAMO #1 as well.
29.04.2015 00:22
Oops, sketchy solution using am-gm and trivial ineq. on mobile; will post solution later
29.04.2015 00:23
Hmm what is the trivial ineq? Is it that $(a-b)^2 \ge 0$?
29.04.2015 00:24
Yes it is.
29.04.2015 00:27
wait does (-51,111) work
29.04.2015 00:29
That satisfies the equations, Ingenio.
29.04.2015 00:30
How much do you think writing it in the form of the sum of squares is worth? I got that but didnt see the factorization.
29.04.2015 00:31
Wrote a computer program and got: x y 1 -1 3 3 19 -1 53 -17 111 -51 199 -109 323 -197 489 -321 703 -487 971 -701 1299 -969 1693 -1297 2159 -1691 2703 -2157 3331 -2701 4049 -3329 4863 -4047 5779 -4861 6803 -5777 7941 -6801 9199 -7939 These are just the first few of the possibilities Note: x and y can be switched.
29.04.2015 00:33
I thought this was NUMBER THEORY so mods, primes, even Eisenstein integers...
29.04.2015 00:33
By am-gm, $(\dfrac{x+y+3}{3})^3\ge3xy$, with equality when x=3, y=3. however that is just for positive ints so we try triv. ineq. giving $x^2+xy+y^2\ge-xy\ge\dfrac{x+y+3}{3}^3$, equality when $x+y=0$. The solutions are $\pm 1, \mp 1$.
29.04.2015 00:34
Yep I took mod 3, then mod 9, then mod 6 then cried.
29.04.2015 00:35
I spent a large amount of time trying to prove that there were finitely many solutions because of http://en.wikipedia.org/wiki/Siegel%27s_theorem_on_integral_points. I got it in the end though.
29.04.2015 00:36
$\pmod{9}$ looked really promising, with all the $3$s and cubes, but first I knew I had to substitute $y=3a-x$, otherwise the RHS wouldn't work properly. Then I found the solution
29.04.2015 00:36
hwl0304 wrote: By am-gm, $(\dfrac{x+y+3}{3})^3\ge3xy$, with equality when x=3, y=3. however that is just for positive ints so we try triv. ineq. giving $x^2+xy+y^2\ge-xy\ge\dfrac{x+y+3}{3}^3$, equality when $x+y=0$. The solutions are $\pm 1, \mp 1$. There are more solutions... I started casework bashing until realizing that the radicand factored.
29.04.2015 00:37
I used mod 3 & mod 9 and somehow showed that there are no solutions
03.01.2022 01:50
OMG Evan!! Anyways the equation $\frac{x+y}{3}$ must be integer, so substitute $x+y=3r$. Then the equation becomes \[ x^2+xy+y^2 = \left(\frac{3r}{3}+1\right)^3. \]. On LHS, I tried completing the square by adding $xy$ term, and adding $xy$ on RHS, then $(x+y)^2= \left(\frac{3r}{3}+1\right)^3 + xy$.
15.01.2022 05:32
We will make the substitution $x+y=3t$. Then, we have that the equation becomes \[(t+1)^3=(3t)^{2}-xy.\]Now, we can make the substitution $y=3t-x.$ Thus, we have \[(t+1)^3=9t^2-x(3t-x).\]From this, we have: \[t^3-6t^2+3t+1=x^2-3xt.\]We can express this as a quadratic in $x$: \[x^2-3tx-(t^3-6t^2+3t+1).\]And now, by the quadratic formula, we have that the solutions to this equation are of the form \[x=\frac{3t \pm \sqrt{9t^{2}+4t^3-24t^2+12t+4}}{2}\]\[=\frac{3t \pm \sqrt{4t^3-15t^2+12t+4}}{2}\]For this to be an integer, it's necessary for the expression in the square root to be a perfect square; i.e. $(4t+1)(t-2)^2$. is a square [which is what it factors to] So $4t+1$ is a perfect square. However, this means that $t=n^2+n$ for some integral $n$. Thus, we have that \[(x,y)=\frac{3n^2+n\pm(n^2+n-2)(2n+1)}{2}\]. \[=(n^3+3n-1,-n^3+3n+1)\]. All steps are reversible, so these are the only solutions and work.
30.03.2022 17:50
We claim the solutions are $\boxed{(t^3+3t^2-1,-t^3+3t+1)}$ and $\boxed{(-t^3+3t+1,t^3+3t^2-1)}$ for $t$ integral. Let $s=\frac{x+y}3$ which is an integer, then: $$9s^2-xy=(s+1)^3\Leftrightarrow x^2-3sx-s^3+6s^2-3s-1=0$$(since $y=3s-x$). This quadratic has an $x$-discriminant: $$\Delta=4s^3-15s^2+12s+4=(4s+1)(s-2)^2$$so $4s+1=r^2$ for some integer $r$. Then $r$ is odd, so with the substitution $r=2t+1$ we obtain $s=t^2+t$. By the quadratic formula: $$x=\frac{3s\pm\sqrt\Delta}2=\frac{3s\pm r|s-2|}2=\frac{3t^2+3t\pm(2t+1)|t^2+t-2|}2.$$If $t\in\{0,-1\}$, then $s=0$ and the first equation gives $(x,y)=(1,-1),(-1,1)$ which are solutions included in the solution set.. Otherwise, $t^2+t-2\ge0$, so $x\in\{t^3+3t^2-1,-t^3+3t+1\}$. Since the equation is symmetric in $x,y$, these give the general solutions as before.
31.03.2022 21:02
The answers are $\boxed{(n^3+3n^2-1, -n^3+3n+1)}$ and $\boxed{(-n^3+3n+1,n^3+3n^2-1)}$ for all integers $n$. Set $x+y=a$ and $x-y=b$. Then we obtain \[\frac{3a^2+b^2}{4}=\left(\frac{a}{3}+1\right)^3\]so we can set $a=3k-3$ to get \[\frac{3(9k^2-18k+9)+b^2}{4}=k^3\iff b^2=4k^3-27k^2+54k-27=(k-3)^2(4k-3).\]Then we must have $4k-3=(2n+1)^2$ for some integer $n$, which means that $k=n^2+n+1$ and $b=\pm(2n^3+3n^2-3n-2)$. Then $a=3n^2+3n$, so that \[(a,b)=(3n^2+3n,2n^3+3n^2-3n-2),(3n^2+3n,-2n^3-3n^2+3n+2)\]and since $x=\frac{a+b}{2}$ and $y=\frac{a-b}{2}$ our final answer is \[(x,y)=\boxed{(n^3+3n^2-1,-n^3+3n+1)},\boxed{(-n^3+3n+1,n^3+3n^2-1)}.\]
12.12.2022 04:47
is this bashy or clean idk Multiply both sides by $27$, to get \[27x^2+27xy+27y^2=(x+y+3)^3\]Expanding we get, \[27x^2+27xy+27y^2 = (x+y)^3+9x^2+18xy+9y^2+27x+27y+27\]We want another cubic term and a nicer LHS so we move the squares from the LHS to the RHS \[27xy= (x+y)^3-18x^2+18xy-18y^2+27x+27y+27\]Note that we can make $(x+y-6)^3$ because of the coefficients of the squares so we make it $(x+y-6)^3$. Making the RHS, $(x+y-6)^3$, we get \[-27xy+81x+81y-243 = (x+y)^3-18x^2-36xy-18y^2+108x+108y+216 = (x+y-6)^3\]The LHS can be factored by SFFT to get \[-27(x-3)(y-3) = (x+y-6)^3\]Substitute $a = x-3$ and $b=y-3$ to get \[-27ab=(a+b)^3\]Note that we have symmetric sums, so we let $p = a+b$ and $q=ab$ and plug it into a quadratic to get \[z^2-pz+q = z^2-pz-(\frac{p^3}{27}) = 0\]If we use the quadratic formula, we get \[(a,b) = \cfrac{p\pm\sqrt{p^2+\frac{4p^3}{27}}}{2}\]Note that $p$ must be divisible by $3$, so we substitute $p = 3k$ to get \[(a,b) = \cfrac{3k\pm k\sqrt{9+4k}}{2}\]We need $9+4k$ to be a square but it also has to be an odd square so we need \[9+4k = (2n+1)^2\]Rearranging the terms give \[k = n^2+n-2\]We can plug this back into the quadratic formula to get \begin{align*}(a,b) &= \cfrac{3n^2+3n-6\pm(n^2+n-2)(2n+1)}{2} \\ &= \cfrac{3n^2+3n-6\pm (2n^3+3n^2-3n-2)}{2} \\ &= (n^3+3n^2-4, -n^3+3n-2)\\ \end{align*}We can also flip it because of symmetry. We still have $(a,b) = (x-3,y-3)$ so we add $3$ to each of the expressions to get \[(x,y)=\boxed{(n^3+3n^2-1,-n^3+3n+1)},\boxed{(-n^3+3n+1,n^3+3n^2-1)}.\] Thanks to megarnie for helping me out with the end $9+4k = (2n+1)^2$ part.
25.12.2022 06:25
Most solutions to this problem are quite unmotivated, often involving a magical $x + y = 3s$ substitution, or observing that a cubic polynomial just happens to have a squared factor. We'll present a motivated solution, using natural observations: ones that a contestant might first notice when approaching the problem. Unfortunately, there are a lot of calculations. We hide the details to enhance the reading of the solution. Part I: complex paramaterization Experienced contestants may recall that the polynomial $x^2 + xy + y^2$ factors: with this in mind, define $\omega = e^{2\pi i/3}$ and set \begin{align*} a & = \omega x - \omega^2 y\\ b & = \omega y - \omega^2 x \end{align*}so \[ x^2 + xy + y^2 = -ab. \]In addition, we have \begin{align*} a+b & = (x+y)(\omega - \omega^2)\\ \iff x+y & = \frac{a+b}{\omega - \omega^2}. \end{align*}The provided equation thus transforms into \begin{align*} -ab & = \left( \frac{a+b}{3(\omega - \omega^2)} + 1 \right)^3\\ \iff -27ab(\omega - \omega^2)^3 & = [a + b + 3(\omega - \omega^2)]^3\\ \iff 27ab[3(\omega - \omega^2)] & = [a + b + 3(\omega - \omega^2)]^3 \end{align*}where we observe that $(\omega - \omega^2)^2 = -3$. Motivated by the above, we set $c = 3(\omega - \omega^2) = (\omega^2 - \omega)^3$, so that \[ (a+b+c)^3 = 27abc. \]However, this equation can be easily solved: Claim. We have $(a+b+c)^3 = 27abc$ if and only if there exist $p$, $q$, $r$ with sum $0$ satisfying $(a, b, c) = (p^3, q^3, r^3)$.
$\square$ Note that we can multiply all of $p$, $q$, $r$ by the same power of $\omega$ without affecting anything, so we can suppose $r = \omega^2 - \omega$. Thus, there exist $p$ and $q$ satisfying \begin{align*} p + q + (\omega^2 - \omega) & = 0\\ \omega x - \omega^2 y & = p^3\\ \omega y - \omega^2 x & = q^3. \end{align*}Moreover, these describe all complex solutions $(x, y)$ to the equation: take $p$ and $q$ with sum $\omega - \omega^2$, and solve for $x$ and $y$. Part II: real parametrization We must now isolate the real solutions $(x, y)$. Observe that \[ \overline{q}^3 = \overline{\omega y - \omega^2 x} = \omega^2 y - \omega x = -p^3, \]so \[ p^3 = -\overline{q}^3 \implies p = -\omega^k \overline{q} \]for some $k \in \{0, 1, 2\}$. If $k = 1$, then $p = -\omega\overline{q}$, so \begin{align*} -\omega\overline{q} + q & = \omega - \omega^2\\ \implies -\omega^2 q + \overline{q} & = \omega^2 - \omega\\ \implies -q + \omega\overline{q} & = 1 - \omega^2\\ \implies q - \omega\overline{q} & = \omega^2 - 1, \end{align*}a contradiction.
It follows that $k = 0$; i.e. $p = -\overline{q}$. In other words, $p$ and $q$ have opposite real parts and equal imaginary parts. From \[ p + q = \omega - \omega^2 = 2\omega + 1, \]we obtain that there exists a real $t$ satisfying \begin{align*} p & = t + 1 + \omega = t - \omega^2\\ q & = -t + \omega. \end{align*}Finally, we can solve for $x$ and $y$. We have \begin{align*} \omega x - \omega^2 y & = p^3 = (t - \omega^2)^3\\ & = t^3 - 3t^2 \omega^2 + 3t \omega - 1\\ \omega y - \omega^2 x & = q^3 = (-t + \omega)^3\\ & = -t^3 + 3t^2 \omega - 3t \omega^2 + 1. \end{align*}This is a linear system: the solution is
So far, we have only used the fact that $x$ and $y$ are real. Thus, all real solutions are given by the mentioned \[ (x, y) = (-t^3 + 3t + 1, t^3 + 3t^2 - 1) \]for real $t$. Part III: integer parametrization To conclude, we isolate the integer solutions: Claim. If $-t^3 + 3t + 1$ and $t^3 + 3t^2 - 1$ are integers, then $t$ is also an integer. (The converse is clearly true.)
$\square$ To conclude, all solutions are given by \[ x = -t^3 + 3t + 1 \quad \text{and} \quad y = t^3 + 3t^2 - 1 \]as $t$ ranges over the integers. Their validity can be seen by reversing the steps above.
13.03.2023 03:24
Clearly $3|x+y$, so set $x +y = 3s$ and $xy =p$. Then, the given equation becomes \[ 9s^2 - p = (s + 1)^3 = s^3 + 3s^2 + 3s + 1\implies p = -s^3 + 6s^2 - 3s - 1.\]Now, notice that $x,y$ are the roots of $P(t) = t^2 - 3st + p = t^2 - 3st + (-s^3 + 6s^2 - 3s -1)$. Since $x,y$ are integers, the discriminant of $P$ must be a perfect square. The discriminant is \[ D = 9s^2 - 4(-s^3 + 6s^2 - 3s - 1) = 4s^3 - 15s^2 + 12s + 4 = (s - 2)^2(4s + 1),\]which is a square if and only if $4s + 1$ is a square. Thus, set $4s + 1 = (2n+1)^2\implies s = n^2 + n$ where $n$ is an integer. Then, we have $$\pm \sqrt{D} = \pm \sqrt{(n^2 + n-2)^2(2n+1)^2} = \pm (n^2 + n - 2)(2n + 1) = \pm (2n^3 + 3n^2 - 3n - 2),$$So the roots of $P$ are \[ \frac{3n^2 + 3n\pm (2n^3 + 3n^2 - 3n - 2)}{2} = n^3 + 3n^2 - 1, -n^3 + 3n + 1.\]Hence, the answer is $(x,y) = (n^3 + 3n^2 - 1, -n^3 + 3n + 1)$ (and permutations) for any integer $n$.
02.07.2023 03:31
hwl0304 wrote: By am-gm, $(\dfrac{x+y+3}{3})^3\ge3xy$, with equality when x=3, y=3. however that is just for positive ints so we try triv. ineq. giving $x^2+xy+y^2\ge-xy\ge\dfrac{x+y+3}{3}^3$, equality when $x+y=0$. The solutions are $\pm 1, \mp 1$. This only works when x and y are both positive.
07.09.2023 02:21
We set $s=x+y,d=x-y$ and substitute these in to get $$27d^2=4s^3-45s^2+108s+108$$Taking $\mod 27$ of this gives $3|s$, so we let $s=3k$. Substituting $k$ into the equation, we get that $$d^2=(4k+1)(k-2)^2$$Giving that $4k+1$ is a (odd) perfect square, so we let it be $(2n+1)^2$ Substituting this into the equation and doing some algebraic manipulation eventually give $x=n^3+3n^2-1,y=-n^3+3n+1$ Full proof here: https://infinityintegral.substack.com/p/usajmo-2015-contest-review
09.03.2024 03:36
Reminds me of USAMO 1987/1. I claim that there are infinitely many solutions, and all of them are in the form of \[(x,y)=\left(\frac{3\left(\frac{m^2-1}{4}\right)+m\left(\frac{m^2-1}{4}\right)}{2},\frac{3\left(\frac{m^2-1}{4}\right)-m\left(\frac{m^2-1}{4}\right)}{2}\right),\]or \[(x,y)=\left(\frac{3\left(\frac{m^2-1}{4}\right)-m\left(\frac{m^2-1}{4}\right)}{2},\frac{3\left(\frac{m^2-1}{4}\right)+m\left(\frac{m^2-1}{4}\right)}{2}\right),\]where $m$ is an odd integer. Obviously, in order for the RHS to be an integer like the LHS must be, $3\mid x+y$. Let $x+y=3k$. Now, we have that \[(x+y)^2-xy=x^2+xy+y^2=\left(\frac{x+y}{3}\right)^3,\]\[\iff 9k^2-xy=(k+1)^3,\]\[\iff xy=9k^2-(k+1)^3,\]and if we put this into a quadratic equation, note that $x$, $y$ must be roots of \[r^2-(3k)r+(9k^2-(k+1)^3),\]which has discriminant $\sqrt{-27k^2+4(k+1)^3}$. Therefore, if $x$, $y$ are integers, we must have $-27k^2+4(k+1)^3$ be a perfect square. However, this factors as $(k-2)^2(4k+1)$, which means that $4k+1$ must be a perfect square! Therefore, if we let $k=\frac{m^2-1}{4}$ (note that $m$ must be odd for $k$ to be an integer; and $k$ must be an integer since $x+y=3k$ and $3\mid x+y$!) and plug it in, we get \[r=\frac{3\left(\frac{m^2-1}{4}\right)\pm m\left(\frac{m^2-1}{4}\right)}{2},\]which must be an integer since all odd squares are $1$ mod $8$, making $\frac{m^2-1}{4}$ even. Therefore our solutions are all in the form \[(x,y)=\left(\frac{3\left(\frac{m^2-1}{4}\right)+m\left(\frac{m^2-1}{4}\right)}{2},\frac{3\left(\frac{m^2-1}{4}\right)-m\left(\frac{m^2-1}{4}\right)}{2}\right),\]or \[(x,y)=\left(\frac{3\left(\frac{m^2-1}{4}\right)-m\left(\frac{m^2-1}{4}\right)}{2},\frac{3\left(\frac{m^2-1}{4}\right)+m\left(\frac{m^2-1}{4}\right)}{2}\right),\]as desired, finishing the problem. *Note: yeah, it would probably be better on the grader to simplify by letting $m=2n+1$.
14.06.2024 21:08
If $x+y$ is odd, the LHS is odd but the RHS is even, a contradiction. Hence is $x+y$ is even. Clearly $3\mid x+y$. Let $a:=\frac{x+y}{6}$ and $b:=\frac{x-y}{2}$, which are integers. Then \[ 27a^2+b^2=(2a+1)^3=8a^3+12a^2+6a+1\implies b^2=(a-1)^2(8a+1). \]It follows that $8a+1=:n^2$ is a perfect square so $8a=(n-1)(n+1)$. Since $n-1$ and $n+1$ have the same parity, there exists $d\mid 2a$ such that $2d=n-1$ and $\frac{4a}{d}=n+1$. Thus $\frac{2a}{d}-d=1$ so $2a=d(d+1)$. It follows that $b=\sqrt{4d(d+1)+1}\left(\frac{d(d+1)}{2}-1\right)$ so \[ (x,y)=\left(\frac{3d(d+1)}{2}+\frac{(d-1)(d+2)(2d+1)}{2},\frac{3d(d+1)}{2}-\frac{(d-1)(d+2)(2d+1)}{2}\right)=\boxed{(d^3+3d^2-1,-d^3+3d+1)} \]are the only solutions. $\square$
05.10.2024 20:44
If I made a mistake, feel free to point it out or PM me.
15.12.2024 06:18
What a strange problem. The statement strongly motivates $x+y=k$ to get $$27(x^2+x(k-x)+(k-x)^2) = (k+3)^3 \implies x = \frac{1}{18} \left( 9k+(k-6)\sqrt{12k+9} \right)$$(the negative solution just switches $x$ and $y$). We need $12k+9=m^2, m \in \mathbb{Z}$ so $m \equiv 3 \pmod{6} \implies m = 6n+3$. So $k = \frac{(6n+3)^2-9}{12} = 3n^2+3n$. Plugging this in gives $x = \frac{1}{18}\left( 9(3n^2+3n) + (3n^2+3n-6)(6n+3)\right) = n^3+3n^2-1$ and $y = k - x = 3n^2+3n-(n^3+3n^2-1)=-n^3+3n+1$. So (with switching x, y obviously) we have $$\boxed{(n^3+3n^2+1, -n^3+3n+1)}$$
02.01.2025 05:50
Nice problem! We claim that the set of solutions is exactly characterized by (up to permutation) \[(x, y) = (n^3 + 3n^2 - 1, -n^3 + 3n + 1)\]for any $n \in \mathbb{Z}$. It is not hard to check that this works. We will now show that a pair $(x, y)$ must satisfy this form. Since the LHS is an integer, this is enough to imply that $3 \mid x + y$. Set $x + y = 3j$, $xy = p$ for integers $p, j$. Substituting, we obtain \[p = 9j^2 - (j + 1)^3\]However, $x, y$ are the roots of $P(m) = m^2 - 3jm + p$, so the discriminant \[\delta = 4(j + 1)^3 - 27j^2 = (4j + 1)(j-2)^2\]is a perfect square, which is equivalent to $4j + 1 = (2n + 1)^2 \implies j = n^2 + n$. By the quadratic formula, the solutions to $P$ are \[\frac{3(n^2 + n) \pm (n^2 + n - 2)(2n + 1)}{2} = \boxed{(n^3 + 3n^2 - 1, -n^3 +3n + 1)}\]and we are done.
07.01.2025 16:18
Note that $3 \mid x + y$ and by parity inspection both $x, y$ are odd. Now consider the substitution $x = 3a - b, y = 3a + b$ for integers $a, b$, the relation becomes \[(3a - b)^2 + (3a - b)(3a + b) + (3a + b)^2 = (2a + 1)^3 \iff 8a^3 - 15a^2 + 6a + 1 = b^2\]which factors as $(a - 1)^2(8a + 1) = b^2$. Now $8a + 1$ must be a perfect square, which can all be determined by $k^2$ for some odd $k$. Letting $8a + 1 = k^2$ yields \[ (a, b) = \left( \dfrac{k^2 - 1}{8}, \dfrac{k^3 - 9k}{8} \right) \implies (x, y) = \left( \dfrac{-k^3 + 3k^2 + 9k - 3}{8}, \dfrac{k^3 + 3k^2 - 9k - 3}{8} \right) \]as the entire curve of solutions for odd $k$.