Maths Olympiad Prep

Library / /16 of 42

Number theory Difficulty 5.6 AIME, harder Prove it Ireland

Find all integer solutions (x,y)(x, y) to the equation
x2xy+y2=2023. x^2 - x y + y^2 = 2023.

Solution

Note that 2023=17272023 = 17^2 \cdot 7 and let (x,y)(x, y) be a solution. If we assume that yy is not divisible by 1717, there exists a number aa such that ayx(mod17)a y \equiv x \pmod{17}. We then have
0=x2xy+y2y2(a2a+1)(mod17), 0 = x^2 - x y + y^2 \equiv y^2 (a^2 - a + 1) \pmod{17},
hence a2a+10(mod17)a^2 - a + 1 \equiv 0 \pmod{17}. This implies that a61(mod17)a^6 \equiv 1 \pmod{17}, because
a61=(a31)(a3+1)=(a31)(a+1)(a2a+1). a^6 - 1 = (a^3 - 1)(a^3 + 1) = (a^3 - 1)(a + 1)(a^2 - a + 1).
On the other hand, by Fermat's little theorem, a161(mod17)a^{16} \equiv 1 \pmod{17}. Then a2a2a16a18(a6)31(mod17)a^2 \equiv a^2 \cdot a^{16} \equiv a^{18} \equiv (a^6)^3 \equiv 1 \pmod{17}, hence a±1(mod17)a \equiv \pm 1 \pmod{17}. But for these two values of aa we get a2a+12a21≢0(mod17)a^2 - a + 1 \equiv 2 - a \equiv 2 \mp 1 \not\equiv 0 \pmod{17}, a contradiction. Hence, yy must be divisible by 1717.

It follows that xx must also be divisible by 1717, and we look for solutions (x,y)=(17u,17v)(x, y) = (17u, 17v). Let N(x,y)=x2xy+y2N(x, y) = x^2 - x y + y^2 and note that
N(x,y)=(2xy)2+3y24. N(x, y) = \frac{(2x - y)^2 + 3y^2}{4}.
Then 2023=N(17u,17v)=172N(u,v)2023 = N(17u, 17v) = 17^2 N(u, v), iff 7=N(u,v)7 = N(u, v), or equivalently
28=(2uv)2+3v2. 28 = (2u - v)^2 + 3v^2.
Because v228/3v^2 \le 28/3 and 2828 is not a square, to find solutions to this equation we only need to consider v{±1,±2,±3}v \in \{\pm 1, \pm 2, \pm 3\}. To a solution with negative vv there corresponds one with positive vv, obtained by changing the signs of both, uu and vv. Because 283=5228 - 3 = 5^2, 2812=4228 - 12 = 4^2, and 2827=1228 - 27 = 1^2, we have these three cases for solutions with positive vv
v=1,2uv=±5,v=2,2uv=±4,v=3,2uv=±1. v = 1, \quad 2u - v = \pm 5, \quad v = 2, \quad 2u - v = \pm 4, \quad v = 3, \quad 2u - v = \pm 1.
The possibilities for solutions (u,v)(u, v) with positive vv are therefore
(3,1)(2,1)(3,2)(1,2)(2,3)(1,3). (3, 1) \quad (-2, 1) \quad (3, 2) \quad (-1, 2) \quad (2, 3) \quad (1, 3).
Thus we obtain 1212 solutions to the original equation, namely
(x,y)=(17,51),(34,51),(17,34) (x, y) = (17, 51), (34, 51), (-17, 34)
and all the variants (x,y)(-x, -y), (y,x)(y, x), (y,x)(-y, -x) of these.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.