We call a positive integer $n$ is $good$ , if there exist integers $a,b,c,x,y$ such that $n=ax^2+bxy+cy^2$ and $b^2-4ac=-20$. Prove that the product of any two good numbers is also a good number.
Problem
Source: IZHO 2023 / P5
Tags: number theory
05.02.2023 06:13
The main idea is to prove that $n$ is good if and only if for every prime p, that $n \vdots p$, $x^2 \equiv -5(mod p)$
05.02.2023 10:49
08.02.2023 13:10
Claim 1: Given a prime $p$ with $-5$ as a $QR$, there exists $a,b$ such that $\frac{a^2+5b^2}{p}=1$ or $2$. Proof (Fermat's Christmas Theorem, modified). This can be easily verified for $p\le5$. Let $p\mid r^2+5$. Consider all $(\lfloor \sqrt{p} \rfloor+1)^2$ pairs of integers $x,y$ such that $0\le x,y \le \lfloor \sqrt{p}\rfloor$. By PHP, there exists $x_1,y_1,x_2,y_2$ such that $x_1-ry_1\equiv x_2-ry_2 \pmod{p}$. This means that $(x_1-x_2)\equiv r(y_1-y_2)\pmod{p}$. Squaring, $p\mid (x_1-x_2)^2+5(y_1-y_2)^2=a^2+5b^2$. Note that $a,b< \sqrt{p}$, so $a^2+5b^2<6p$. We thus have the following cases: If $a^2+5b^2=5p$, then $5\mid a$ so $p=b^2+5\left(\frac{a}{5}\right)^2$. If $a^2+5b^2=4p$, then $2\mid a,b$ so $p=\left(\frac{a}{2}\right)^2+5\left(\frac{b}{2}\right)^2$. If $a^2+5b^2=3p$, then $2p=\left(\frac{a+5b}{3} \right)^2+5\left(\frac{a-b}{3} \right)^2=\left(\frac{a-5b}{3} \right)+5\left(\frac{a+b}{3} \right)^2$, one of which would be an integer solution. If $a^2+5b^2=p$ or $2p$, we are done. This completes the proof. Claim 2: Given a number $n$ which divides $x^2+5y^2$ for some integers $x,y$, there exists $a,b$ such that $\frac{a^2+5b^2}{n}=1$ or $2$. Proof (Sum of 2 squares, modified). Note that $(a^2+5b^2)(c^2+5d^2)=(ac-5bd)^2+5(ad+bc)^2$. If $n\mid x^2+5y^2$, then any prime $p\mid n$ will have $-5$ as a QR. Thus, we can find corresponding $a_p,b_p$ with $a_p^2+5b_p^2=p$ or $2p$. Doing this for every prime (with multiplicity) and multiplying all of them together, we get $2^kn=x^2+5y^2$ for some integers $x,y,k$ with $k\ge0$. If $k\ge 2$, then by mod 4 we will have $2\mid x,y$, reducing it to $2^{k-2}n=\left(\frac{x}{2}\right)^2+5\left(\frac{y}{2}\right)^2$. We can do this until $k\le 1$, which completes the proof. Claim 3: If $n$ is good then $n\mid x^2+5y^2$ for some integers $x,y$. Proof. Since $n$ is good, we can find $a,b,c,x,y$ such that $ax^2+bxy+cy^2=n$ and $b^2-4ac=-20$. Note that $b$ is even, so let $b=2b_1$. Then $ac=b_1^2+5$. Thus, $an=a^2x^2+2ab_1xy+acy^2=a^2x^2+2ab_1xy+b_1^2y^2+5y^2=(ax+b_1y)^2+5y^2$, which proves the claim. Claim 4: If $n_1,n_2$ are good then so is $n_1n_2$. Proof. From Claim 3, $n_1\mid x_1^2+5y_1^2$ and $n_2\mid x_2^2+5y_2^2$, so $n_1n_2\mid (x_1^2+5y_1^2)(x_2^2+5y_2^2)=(x_1x_2-5y_1y_2)^2+5(x_1y_2+x_2y_1)^2$. By claim 2, we can find $i,j$ such that $i^2+5j^2=n_1n_2$ or $2n_1n_2$. In the former take $(a,b,c,x,y)=(1,0,5,i,j)$, while in the latter take $(a,b,c,x,y)=(2,2,3,\frac{i-j}{2},j)$. This completes the proof.
08.02.2023 14:06
For the curious ones, see an algorithm (close to an explicit identity, but not quite) here: https://en.wikipedia.org/wiki/Gauss_composition_law, section "An algorithm to find the composite of two IBQFs". Similarly to the easiest approach for this problem (mentioned by @RnstTrjyn), more generally see Proposition 4.1 (a proof is just before the statement itself) at https://dms.umontreal.ca/~andrew/Courses/Chapter4.pdf
17.02.2023 13:16
Related to the above post, one can give a very short and algebraic solution to the problem that does not need any divisibility or primality arguments: Claim: If $n$ is of the form $ax^2+bxy+cy^2$ for some such $a,b,c$, then either $n=x^2+5y^2$ or $n=2x^2+2xy+3y^2$ (for different $x,y$). Proof of Claim: Clearly we may w.l.o.g. assume that $a \ge c>0$ and that $b \ge 0$. Moreover, substituting $x \mapsto x+y$, we may w.l.o.g. assume that $b \le a$. Hence $20=4ac-b^2 \ge 3a^2$ and so $a \le 2$ and a quick casework shows that the only possibilities are $(a,b,c)=(1,0,5)$ and $(a,b,c)=(2,2,3)$. QED Back to the main problem, it now suffices to prove that products of numbers of the form $x^2+5y^2$ or $2x^2+2xy+3y^2$ are again of this form. But this follows immediately from the following three identities: \[(a^2+5b^2)(c^2+5d^2)=(ac+5bd)^2+5(ad-bc)^2.\]\[(a^2+5b^2)(2c^2+2cd+3d^2)=2(ac-bc-3bd)^2+2(ac-bc-3bd)(2bc+bd+ad)+3(2bc+bd+ad)^2.\]\[(2a^2+2ab+3b^2)(2c^2+2cd+3d^2)=(2ac+bc+ad-2bd)^2+5(bc+ad+bd)^2.\](Note that although this might look like black magic, these identities can easily be derived from the factorizations $a^2+5b^2=(a+\sqrt{-5}b)(a-\sqrt{-5}b)$ etc. just as the usual identities for sums of two squares are derived from factorization in $\mathbb{Z}[i]$.)
03.03.2023 18:43
RnstTrjyn wrote: The main idea is to prove that $n$ is good if and only if for every prime p, that $n \vdots p$, $x^2 \equiv -5(mod p)$ Maybe I am misunderstanding this but it should be that the set of good numbers is exactly those with squarefree part consisting only of primes that have $-5$ as a quadratic residue, all these solutions are very similar but I do not understand why it can't be that $-5$ is not a quadratic residue $\pmod{p}$ and we take $p \mid x,y$ which means that $p \mid n$. I think there could be more emphasis on the following identity in this thread, so I will just write it down (it was mentioned in #9): $$n = \frac{(ax+ky)^2+5y^2}{a}$$where $k = 2b, a \mid k^2+5$. This is the crux of my solution and is quite important intuition wise (#10 and #11 also try and transform the expression algebraically to a nicer "Pell-like" form however it is not exactly possible, $2x^2+2x+3y^2$ has to be included along with $5x^2+y^2$ because of how $n \mid 5x^2+y^2$ for $(x,y) \in \mathbb{Z}^2$ implies there exists $(a,b) \in \mathbb{Z}^2$ such that $\frac{a^2+5b^2}{n} \in \{1,2\}$ and not only $\{1\}$ which is the case for Fermat Christmas). Anyways, I enjoy seeing problems like this outside of the IMO (this however would be a very questionable choice at the IMO).
10.03.2023 17:52
$x^2+5y^2$ and $2x^2+2xy+3y^2$ are reduced forms of discriminant $D=-20.$
19.03.2023 19:52
rightways wrote: We call a positive integer $n$ is $good$ , if there exist integers $a,b,c,x,y$ such that $n=ax^2+bxy+cy^2$ and $b^2-4ac=-20$. Prove that the product of any two good numbers is also a good number. Mentioned in Niven's classic book "The theory of numbers" chapter 5 in quadratic forms... lol
14.02.2024 17:58
@gghx I think you need to clarify what $x,y$ integers you are talking about since if in the claim $2$ we put $x, y : n$, then it is not necessary to be $1$ or $2$
15.02.2024 04:11
We claim that $n$ is good if and only if there exist integers $s$ and $t$ such that $s^2-4tn=-20$. Suppose that $n=ax^2+bxy+cy^2$ for some integers $x$ and $y$. Then we can apply a linear transformation so that we may suppose $(x,y)=(1,0)$ whence $a=n$. For the other direction, if $s^2-4tn=-20$ then $n=nx^2+sxy+ty^2$ when $(x,y)=(1,0)$. Let $n$ and $m$ be good. Then we have integers $s$, $t$, $u$, $v$ with $s^2-4tn=-20$ and $u^2-4mv=-20$. Then $-20$ is a quadratic residue modulo $4n$ and $4m$. Let $p^k$ be a prime power with $k\ge 1$ dividing $4mn$. Then if $p$ is odd, $-20$ is a QR mod $p$ and hence a QR mod $p^k$ by Hensel. If $p$ is even, we can readily verify $-20$ is a quadratic residue mod any power of 2 by checking it for 1, 2, 4, 8, 16, 32 and using Hensel for larger powers. Hence $-20$ is a QR mod any prime power dividing $4mn$ and is thus a QR mod $4mn$. So we can find integers $w$, $z$ with $w^2-4mnz=-20$, hence $mn$ is good.