If $d$ is a positive integer such that $d \mid 5+2022^{2022}$, show that $d=2x^2+2xy+3y^2$ for some $x, y \in \mathbb{Z}$ iff $d \equiv 3,7 \pmod {20}$.
Problem
Source: Thailand 2023 TSTST2/3
Tags: number theory
24.08.2023 00:22
Partial solution. I prove if $d\mid 5+x^2$ (where $x=2022^{1011}$) and $d=2x^2+2xy+3y^2$ for some $x,y\in\mathbb{Z}$, then $d\equiv 3,7\pmod{7}$. Take any prime $p\mid 5+x^2$. Clearly $p\ne 5$, $p$ is odd, and $(-5/p)=1$. We now study such prime $p$ more carefully. Case 1. $p\equiv 1\pmod{4}$. In this case, we have $(-5/p)=(-1/p)(5/p)=1$, so $(5/p)=1$. Using quadratic reciprocity, \[ \left(\frac{5}{p}\right)\left(\frac{p}{5}\right) = (-1)^{p-1}=1\Rightarrow \left(\frac{p}{5}\right) =1. \]Hence, $p\in\{1,4\}\pmod{5}$. Case 2. $p\equiv -1\pmod{4}$. In this case, we have $(5/p)=-1$, so $p\in\{2,3\}\pmod{5}$. Now, it is clear that $y$ is odd—otherwise $d$ is even. Furthermore, $2x^2+2xy=2x(x+y)$ is divisible by $4$, so $d\equiv 3\pmod{4}$. Let $N_1$ be the number of primes $q\equiv -1\pmod{4}$ for which $q\mid d$ (repetitions allowed). We obtain that $N_1$ is odd. From here, we immediately obtain $d\in\{2,3\}\pmod{5}$. This, together with the fact $d\equiv 3\pmod{4}$ immediately yields $d\in\{3,7\}\pmod{20}$. It now remains give a construction. I'll come back to this later.
27.08.2023 12:18
This problem is much easier if one knows a bit of theory of binary quadratic forms, i.e. forms $f(x,y)=ax^2+bxy+cy^2$. Important notions include the discriminant $D=b^2-4ac$ and the notion of equivalence of two forms, which means that we can transform one form into another $g(x,y)=f(ax+by,cx+dy)$ by an invertible orientation-preserving linear change of coordinates, i.e. $ad-bc=1$. It is a fundamental fact that there are only finitely many equivalence classes of each discriminant, their number is called the class number $h(D)$. In general, it is hard to decide which numbers are of the form $n=f(x,y)$ for a given form $f$, e.g. $n=2x^2+2xy+3y^2$. However, it is much easier to describe which numbers are represented by some form of a given discriminant $D$. Namely, for $n$ squarefree, this is possible if and only if there are no congruence obstruction, i.e. $t^2 \equiv D \pmod{4n}$ is solvable. The ideal case for the representation problem for a single form is therefore when there is only one equivalence class, i.e. $h(D)=1$. This is why we have a beautiful theorem for the numbers of the form $n=x^2+y^2$ (the two-squares theorem, where $D=-4$) or $n=x^2+xy+y^2$ (the Eisenstein integers, where $D=-3$) but not for e.g. $2x^2+2xy+3y^2$. Indeed, here the discriminant is $-20$ and it is not hard to check (there is a very simple algorithm) that $h(-20)=2$. The two equivalence classes are represented by $x^2+5y^2$ (the "principal form" of discriminant $-20$) and by $2x^2+2xy+3y^2$. From the result above, we therefore find that a squarefree number $n$ coprime to $10$ is of the form $x^2+5y^2$ OR $2x^2+2xy+3y^2$ iff for all prime divisors of $n$, the number $-5$ is a quadratic residue modulo $p$. At this point, we note that the numbers $d \mid 5+2022^{2022}$ trivially have these properties of being coprime to $10$ and all its prime divisors having $-5$ as quadratic residues! Note that by quadratic reciprocity this condition can be rewritten as $d \equiv 1,3,7,9 \pmod{20}$. So all such numbers $d$ are represented by $x^2+5y^2$ OR $2x^2+2xy+3y^2$ (note that we can remove the squarefree condition since any square factor can just be included in the variables $x,y$ as a factor). It remains to decide which numbers are represented by which of the two forms. Here, the so-called genus theory of Gauß comes to our rescue, which in this case really just amounts to the following easy observation: The number $x^2+5y^2$ clearly only represents $1,4\pmod{5}$ and $2x^2+2xy+3y^2$ only $2,3 \pmod{5}$. So $d$ is represented by $2x^2+2xy+3y^2$ iff $d \equiv 2,3 \pmod{5}$ but since $d \equiv 1,3,7,9 \pmod{20}$, this is equivalent to $d \equiv 3,7 \pmod{20}$. Done! Note: In general, there can be several forms in the same genus, so that we cannot distinguish them by just congruence considerations. The first example of this is the discriminant $-56$ where the forms $x^2+14y^2$ and $2x^2+7y^2$ are not equivalent but cannot be distinguished by congruence considerations. To solve the problem of, say, which numbers are of the form $x^2+14y^2$, one then needs much more advanced mathematics (class field theory), in this case the answer would be e.g. that $p=x^2+14y^2$ iff $-14$ is a quadratic residue modulo $p$ (the trivial congruence condition) AND additionally $(x^2+1)^2 \equiv 8 \pmod{p}$ is solvable.