Maths Olympiad Prep

Library / IRL ABooklet /71 of 191

IRL ABooklet

Number theory Difficulty 5.6 AIME, harder Prove it Ireland

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

Solution

Note that 2023=172⋅72023 = 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 ay≡x(mod17)a y \equiv x \pmod{17}. We then have
0=x2−xy+y2≡y2(a2−a+1)(mod17), 0 = x^2 - x y + y^2 \equiv y^2 (a^2 - a + 1) \pmod{17},
hence a2−a+1≡0(mod17)a^2 - a + 1 \equiv 0 \pmod{17}. This implies that a6≡1(mod17)a^6 \equiv 1 \pmod{17}, because
a6−1=(a3−1)(a3+1)=(a3−1)(a+1)(a2−a+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, a16≡1(mod17)a^{16} \equiv 1 \pmod{17}. Then a2≡a2⋅a16≡a18≡(a6)3≡1(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 a2−a+1≡2−a≡2∓1≢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)=x2−xy+y2N(x, y) = x^2 - x y + y^2 and note that
N(x,y)=(2x−y)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=(2u−v)2+3v2. 28 = (2u - v)^2 + 3v^2.
Because v2≤28/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 28−3=5228 - 3 = 5^2, 28−12=4228 - 12 = 4^2, and 28−27=1228 - 27 = 1^2, we have these three cases for solutions with positive vv
v=1,2u−v=±5,v=2,2u−v=±4,v=3,2u−v=±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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.