Find all positive integers $m$ such that there exists integers $x$ and $y$ that satisfies $$m \mid x^2+11y^2+2022.$$
Problem
Source: FKMO 2022 Problem 5
Tags: number theory, Divisibility, Chinese Remainder Theorem, quadratic residue, Hensel s Lemma
23.04.2022 21:05
23.04.2022 22:38
@above is slightly careless but the idea is there, nevertheless pretty standard for FKMO P5. The answer is all $m \in \mathbb{N}$ such that $\nu_2(m) \leq 1, \nu_{337}(m) \leq 1, 11 \nmid m$. The idea is that we can reduce to prime powers by CRT and then use Hensel to generate solutions of higher powers by fixing $y \in \mathbb{N}$. Firstly, we will show that no other $m \in \mathbb{N}$ work. $\textbf{Lemma 1:}$ $11 \nmid m$ $\textbf{Proof)}$ If $11 \mid m \mid x^2+11y^2+2022$ which is a contradition as $-2$ is a quadratic non-residue $\pmod{11}$. $\blacksquare$ $\textbf{Lemma 2:}$ $\nu_2(m) \leq 1$ $\textbf{Proof)}$ If $4 \mid m \mid x^2+11y^2+2022$ then $4 \mid x^2-y^2+2$ which is not possible because $x^2 \equiv 0,1 \pmod{4}$ for all $x \in \mathbb{N}$. $\blacksquare$ $\textbf{Lemma 3:}$ $\nu_{337}(m) \leq 1$ $\textbf{Proof)}$ We will prove that there are no solutions to $x^2+11y^2+2022 = 0$ other than $(x,y) = (0,0)$ in $\mathbb{F}_p^2$. Assume for the ssake of contradiction that there is such a solution then $x^2 \equiv -11y^2 \pmod{337}$ which means that $\left( \frac{-11}{337} \right) = 1$ then as $-1$ is a quadratic residue $\pmod{337}$ we must have that $\left( \frac{11}{337} \right) = 1$, then $$\left( \frac{337}{11} \right) = \left( \frac{11}{337} \right) \cdot \left( \frac{337}{11} \right) = (-1)^{\frac{337-1}{2} \cdot \frac{11-1}{2}} = 1$$which means that $7$ is a quadratic residue $\pmod{11}$, which is a contradiction. Hence, if $337 \mid x^2+11y^2+2022$, then $337 \mid x,y$ because $337 \mid 2022$, then $337^2 \mid x^2+11y^2$ which means that $337^2 \nmid x^2+11y^2+2022$. $\blacksquare$ $\textbf{Lemma 4:}$ If $\nu_2(m), \nu_{337}(m) \leq 1$, $11 \nmid m$, then there exists $(x,y) \in \mathbb{N}^2$ such that $m \mid x^2+11y^2+2022$ $\textbf{Proof)}$ Firstly, notice that if we can find $(x_1,y_1),(x_2,y_2), \cdots, (x_k),(y_k) \in \mathbb{N}^2$ such that $p_i^{l_i} \mid x_i^2+11y_i^2+2022$ for all $i \in \{1, \cdots, k\}$ for distinct primes $p_1, \cdots, p_k$ and $l_i \in \mathbb{N}$ for $i \in \{1, \cdots, k\}$ , then by the Chinese Remainder Theorem, there exists some $x,y \in \mathbb{N}$ such that $\prod_{i=1}^{k} p_i^{l_i} \mid x^2+11y^2+2022$, hence we only have to prove $\textbf{Lemma 4}$ for prime powers, say $p^k$. Firstly, if $p \in \{2,337\}$, take $(x,y) = (0,0) \in \mathbb{F}_p$ and we get a solution as we already know that $\nu_2(m), \nu_{337}(m) \leq 1$, assume now that $p \not\in \{2,11,337\}$. $\textbf{Lemma 4.1}$ There exists some $x \not\equiv 0 \pmod{p}$, $x,y \in \mathbb{N}$ such that $p \mid x^2+11y^2+2022$ for all primes $p \not\in \{2,11,337\}$. $\textbf{Proof)}$ If $p = 3$, take $x \equiv y \equiv 1 \pmod{3}$. Assume for the sake of contradiction that there is no such pair for $p \not\in \{2,3,11,337\}$ , then $-11(x^2+2022)$ is not a quadratic residue for any $x \not\equiv 0\pmod{p}$, we split into two cases. $\textbf{Case 1)}$ $-11$ is a quadratic residue $\pmod{p}$ Then $a+2022$ is a quadratic non-residue for all non-zero quadratic residues $a$. There are $\frac{p-1}{2}$ non-zero quadratic residues and $\frac{p-1}{2}$ quadratic non-residues meaning that there are no quadratic non-residues which differ by $2022$, in fact $a+2022$ for a quadratic non-residue $a$, must be a quadratic residue, ultimately $a+4044$ for a quadratic residue must be a quadratic residue as well, then as $gcd(4044,p) = 1$, we have that the sequence $a+4044 \cdot k$ for $k \in \mathbb{N}$ contains only quadratic residues and in fact spans $\mathbb{F}_p$, which is a contradiction. $\blacksquare$ $\textbf{Case 2)}$ $-11$ is a quadratic non-residue $\pmod{p}$ Then $a+2022$ is a quadratic residue for all non-zero quadratic residues $a$, which again, because $gcd(p,2022)$ means that all elements of $\mathbb{F}_p$ are quadratic residues as $a+2022k$ again spans all residues. $\blacksquare$ $\textbf{Remark:}$ It is possible that we eventually get stuck in our map $x \to x+2022$ as we reach $0$ but, we can in fact go both directions for example, in the second case, if in the sequence $2022, 2022+2022, 2022+2022 \cdot 2, \cdots, 2022+2022(p-1) = 2022p$ we look at the last quadratic non-residue before reaching $0$, then, as there is some quadratic residue that appears before this number in the sequence without any $0$ appearing in between, we get a contradiction. Now, in order to conclude $\textbf{Lemma 4}$, we shall use $\textbf{Lemma 4.1}$, notice that we can find a $gcd(p,x) =1, x,y \in \mathbb{N}$ such that $p \mid x^2+11y^2+2022$, then defining $P(x) = x^2+c$ where $c = 11y^2+2022$, notice that $p \mid P(x)$ and $p \nmid 2x$ because $p \neq 2$ and $gcd(p,x) = 1$ which means that $p \nmid P'(x)$, hence by Hensel's Lemma we can find $x,y \in \mathbb{N}$ such that $p^k \mid x^2+11y^2+2022$ for all $k \in \mathbb{N}$. $\blacksquare$ Putting together $\textbf{Lemma 1, 2, 3, 4}$ we have indeed verified that the solution set is that described above. $\blacksquare$
24.05.2022 04:22
Use Cauchy Davenport Theorem
05.05.2024 13:14
hensel lemma kills it in the end
02.09.2024 10:15
Can anyone post a proof using Cauchy-Davenport Thm?
02.09.2024 11:33