For any positive integer $n$, define the subset $S_n$ of natural numbers as follow $$ S_n = \left\{x^2+ny^2 : x,y \in \mathbb{Z} \right\}.$$Find all positive integers $n$ such that there exists an element of $S_n$ which doesn't belong to any of the sets $S_1, S_2,\dots,S_{n-1}$. Proposed by Yahya Motevassel
Problem
Source: Iranian TST 2019, second exam day 2, problem 6
Tags: number theory
05.07.2019 01:45
Call an $n$ satisfying the desired property Muriatic. We claim that the Muriatic $n$ are exactly the squarefree positive integers. For $n$ which are not squarefree, say $p^2|n$ for some prime $p$, it is clear that $n$ cannot possibly be Muriatic, since for any positive integer $a = x^2 + ny^2 \in S_n$, we have that $a = x^2 + \frac{n}{p^2} \cdot (yp)^2 \in S_{\frac{n}{p^2}}.$ In other words, $S_n \subseteq S_{\frac{n}{p^2}},$ hence $n$ is not Muriatic. Now, let's show that any squarefree $n$ is Muriatic. Let $n = p_1p_2 \cdots p_k$ be an arbitrary squarefree positive integer. If $n =1$, then $n$ is Muriatic by definition. Else, suppose that $n > 1$. Lemma 1. For any squarefree numbers $a, b$ such that $a | b$ and $a \neq b$, there exists infinitely many primes $p$ so that $\left ( \frac{-a}{p} \right ) = -1$ and $\left ( \frac{-b}{p} \right ) = 1.$ Proof. If both $a, \frac{b}{a}$ have some odd prime divisor, the lemma is trivial by Quadratic Reciprocity and Dirichlet. Otherwise, we consider three cases. Case 1. $a = 1$. In this case, we want to show that there are infinitely many primes $p$ with $\left ( \frac{-1}{p} \right ) = -1$ and $\left ( \frac{-b}{p} \right ) = 1$. The first condition implies that $p \equiv 3$ (mod $4$). If $b = 2$, pick $p \equiv 3$ (mod $8$) and finish with Dirichlet. Otherwise, $b$ is an odd prime, so we can again use Dirichlet to set $\left ( \frac{p}{b} \right ) = (-1)^{\frac{(p-1)(b-1)}{4} + 1}$ and finish with Quadratic Reciprocity. Case 2. $a = 2.$ In this case, $\left ( \frac{-2}{p} \right ) = -1$ gives us that $p \equiv 5, 7$ (mod $8$). We want to show that there are infinitely many primes $p \equiv 5, 7$ (mod $8$) such that $\left ( \frac{(\frac{b}{a})}{p} \right ) = -1.$ Now, we know that $\frac{b}{a}$ has an odd prime divisor, say $q$. Then, we can simply pick $p$ to be an arbitrary thing modulo $\frac{b}{aq}$ (not divisible by $q$ since $b$ is square-free) and then we can pick $p$ to be something modulo $q$ at our own discretion by CRT. From here, this case falls easily from the Quadratic Reciprocity Theorem. Case 3. $\frac{b}{a} = 2.$ Here, we wish to show that there are infinitely many primes $p$ such that $\left ( \frac{2}{p} \right ) = -1$ and $\left ( \frac{-a}{p} \right ) = -1.$ The first condition reads as $p \equiv 3, 5$ (mod $8$). If $a = 1$ we are already done, so otherwise $a$ has an odd prime divisor, say $q$. Then, simply select $p$ to be some arbitrary residue mod $\frac{a}{q}$, and pick it's value modulo $q$ at our discretion. We are then clearly done by the Quadratic Reciprocity Theorem and Dirichlet's Theorem. $\blacksquare$ The following lemma is proven in a similar manner. Lemma 2. For any squarefree $a, b$ with $a \neq b$, there exists infinitely many primes $p$ such that $\left ( \frac{-a}{p} \right ) = -1$ and $\left ( \frac{-b}{p} \right ) = 1.$ Proof. Let $d = \gcd(a, b)$ and $a', b'$ be $\frac{a}{d}, \frac{b}{d}$ respectively. If both $a', b'$ have odd prime divisors, we are done. If any of $a', b'$ are $1$, then we're done by Lemma 1 (e.g. $a' = 1 \Rightarrow a = d|b$). Otherwise, we consider the following two cases. Case 1. $a' = 2$. Then, there is an odd prime divisor $q$ of $b'$ (since $\gcd(a', b') = 1$ and $b' > 1$). As before, select $p$ to be congruent to something arbitrary modulo any prime divisors of $lcm(a, b)$ which are not $2$ or $q$, and $1$ (mod $4$). Then, pick $p$ to be $1$ or $5$ (mod $8$) in order to satisfy $\left( \frac{-a}{p} \right) = -1$, and $p$'s value modulo $q$ to satisfy $\left ( \frac{-b}{p} \right ) = 1.$ Case 2. $b' = 2$. Proof is analogous to the above, left out. $\blacksquare$ With Lemma 2, we are ready to finish. Let $x, y$ be positive integers, to be specified later. From the lemma, for each squarefree $x < n$, we can select a prime $p_x > n$ such that $a^2 + nb^2 \equiv 0$ (mod $p_x$) has nonzero solutions in $a, b$ but $a^2 + b^2 x \equiv 0$ (mod $p_x$) does not. Now, take a solution $(a_x, b_x)$ to the first equation with $p_x^2 \nmid a_x^2 + nb_x^2, p_x \nmid a_x, b_x$, then we stipulate that $x \equiv a_x$ (mod $p_x^2$) and $y \equiv b_x$ (mod $p_x^2$). Since the lemma contains the clause "infinitely many," we can also stipulate that $p_x \neq p_y$ for $x \neq y$. In the end, a solution $(a, b)$ to the resulting system of congruences (exists by CRT) satisfies that $a^2 + nb^2 \in S_n$, but $a^2 + nb^2 \notin S_x$ for any squarefree $x < n$. Indeed, if $a^2 + nb^2 \in S_x$ for some squarefree $x < n$, then we would have that $a^2 + nb^2 = c^2 + xd^2$ for some $c, d \in \mathbb{Z}_{\ge 0}.$ Then, as $p_x | c^2 + xd^2,$ we know that one of $c, d$ is divisible by $p_x$. As $p_x \nmid x$ (since $p_x > n$), this implies that $p_x | c, d$. Therefore, $p_x^2 | c^2 + xd^2 \Rightarrow p_x^2 | a^2 + nb^2$. However, we specifically chose $a_x, b_x$ such that $p_x^2 \nmid a_x^2 + nb_x^2$, and chose $a \equiv a_x, b \equiv b_x$ (mod $p_x^2$), giving us the desired contradiction. $\square$
28.09.2019 12:40
This solution is very similar to Pathological's. I hope that my presentation is more natural. The answer is all squarefree integers. To show that all non-squarefree $n$ does not work, simply note that $S_{k^2n}\subseteq S_n$ for any $n,k\in\mathbb{Z}^+$. Thus the main point of this problem is to show that all squarefree $n$ works. Note that $n=1$ trivially works while $n=2$ works by using $3$. To prevent our desired number from being in $S_1,S_2,\hdots, S_{n-1}$, we use the following lemma. Lemma 1: (Restriction) Let $p$ be a prime and $n\in\mathbb{Z}^+$ such that $\left(\tfrac{-n}{p}\right) = -1$. Then any positive integer $k$ such that $\nu_p(k) = 1$ is not in $S_n$. Proof: Standard quadratic residue trick. Indeed, if $k = x^2+ny^2$ and $p\nmid y$, then $\left(\tfrac{x}{y}\right)^2\equiv -n\pmod p$ which contradicts the condition $\left(\tfrac{-n}{p}\right) = -1$. Thus $p\mid y$ so $p\nmid x$. This means $p^2\mid k$, contradiction to $\nu_p(k)=1$. Now, we have a look at the other view and give a tool to construct a number in $S_n$. Lemma 2: (Construction) Let $p_1, p_2,\hdots,p_t$ be odd primes and $n\in\mathbb{Z}^+$ such that $\left(\tfrac{-n}{p_i}\right) = 1$ for each $i$. Then there exists an element $k$ of $S_n$ which $\nu_{p_i}(k)=1$ for each $i$. Proof: Roughly speaking, we can WLOG $t=1$ because we can collate congruences $\pmod{p_i^2}$ using CRT. Let $p=p_1$. As $\left(\tfrac{-n}{p}\right) = 1$, there exists a positive integer $x$ such that $p\mid x^2+n$. Now we claim that either $x^2+n$ or $(x+p)^2+n$ works. Indeed, if both fails, then $p^2$ must divides both of $x^2+n$ and $(x+p)^2+n$. This means $p^2\mid 2px+p^2\implies p\mid 2x$, impossible. These two lemmas give us a clear idea to construct such element. We take odd primes $p_1, p_2,\hdots,p_{n-1}$ such that $\left(\tfrac{-i}{p_i}\right) = -1$ and $\left(\tfrac{-n}{p_i}\right) = 1$ for each $i$. Then if $k$ is an element of $S_n$ such that $\nu_{p_i}(k)=1$ for each $i$ (which exists), then we would be done. Thus all that remains is to grant the existence of such $p_i$. We do this by the following lemma. Lemma 3: Let $a,b$ be positive integers such that $b>\min\{2,a\}$ is squarefree. Then there exists an odd prime $p$ such that $\left(\tfrac{-a}{p}\right) = -1$ and $\left(\tfrac{-b}{p}\right) = 1$. Proof: As square factor doesn't matter, we can WLOG $a$ is squarefree too. The strategy of the proof is to pick appropriate residue $\pmod 8$ and clear the other constraints using Jacobi's symbol. Case 1: $a=1$ Take $p\equiv 7\pmod 8$ so that $\left(\tfrac{-1}{p}\right) = -1$ and $\left(\tfrac{2}{p}\right) = 1$. By dividing by 2 if necessary, we can WLOG $b$ is odd. Clearly $b>1$ and we have to pick $p$ such that $\left(\tfrac{b}{p}\right) = -1$. Using Jacobi's symbol, we find $$\left(\frac{b}{p}\right) = (-1)^{\frac{p-1}{2}}\left(\frac{p}{b}\right)$$which is possible by picking appropriate residue $p\pmod b$ and use Dirichlet. Case 2: $a>1$ Take $p\equiv 1\pmod 8$ so that $\left(\tfrac{-1}{p}\right) = 1$ and $\left(\tfrac{2}{p}\right) = 1$. Thus the condition is equivalent to $\left(\tfrac{a}{p}\right)=-1$ and $\left(\tfrac{b}{p}\right) = 1$. Thus we can cancel the factor of two in $a,b$ if necessary. Therefore we can WLOG $a,b$ are odd. Clearly $b>1$. Using Jacobi's symbol, both conditions are equivalent to $$\left(\frac{p}{a}\right)=-1 \qquad \left(\frac{p}{b}\right) = -1$$Then it's easy to choose such $p$. Take a prime $q$ which divide $b$ but not $a$. Then let $p\equiv 1\pmod{\tfrac{ab}{q}}$ while $p$ is not a quadratic residue $\pmod q$. Hence we are done by Dirichlet.
14.01.2020 17:45
Pathological wrote: Call an $n$ satisfying the desired property Muriatic. We claim that the Muriatic $n$ are exactly the squarefree positive integers. For $n$ which are not squarefree, say $p^2|n$ for some prime $p$, it is clear that $n$ cannot possibly be Muriatic, since for any positive integer $a = x^2 + ny^2 \in S_n$, we have that $a = x^2 + \frac{n}{p^2} \cdot (yp)^2 \in S_{\frac{n}{p^2}}.$ In other words, $S_n \subseteq S_{\frac{n}{p^2}},$ hence $n$ is not Muriatic. Now, let's show that any squarefree $n$ is Muriatic. Let $n = p_1p_2 \cdots p_k$ be an arbitrary squarefree positive integer. If $n =1$, then $n$ is Muriatic by definition. Else, suppose that $n > 1$. Lemma 1. For any squarefree numbers $a, b$ such that $a | b$ and $a \neq b$, there exists infinitely many primes $p$ so that $\left ( \frac{-a}{p} \right ) = -1$ and $\left ( \frac{-b}{p} \right ) = 1.$ Proof. If both $a, \frac{b}{a}$ have some odd prime divisor, the lemma is trivial by Quadratic Reciprocity and Dirichlet. Otherwise, we consider three cases. Case 1. $a = 1$. In this case, we want to show that there are infinitely many primes $p$ with $\left ( \frac{-1}{p} \right ) = -1$ and $\left ( \frac{-b}{p} \right ) = 1$. The first condition implies that $p \equiv 3$ (mod $4$). If $b = 2$, pick $p \equiv 3$ (mod $8$) and finish with Dirichlet. Otherwise, $b$ is an odd prime, so we can again use Dirichlet to set $\left ( \frac{p}{b} \right ) = (-1)^{\frac{(p-1)(b-1)}{4} + 1}$ and finish with Quadratic Reciprocity. Case 2. $a = 2.$ In this case, $\left ( \frac{-2}{p} \right ) = -1$ gives us that $p \equiv 5, 7$ (mod $8$). We want to show that there are infinitely many primes $p \equiv 5, 7$ (mod $8$) such that $\left ( \frac{(\frac{b}{a})}{p} \right ) = -1.$ Now, we know that $\frac{b}{a}$ has an odd prime divisor, say $q$. Then, we can simply pick $p$ to be an arbitrary thing modulo $\frac{b}{aq}$ (not divisible by $q$ since $b$ is square-free) and then we can pick $p$ to be something modulo $q$ at our own discretion by CRT. From here, this case falls easily from the Quadratic Reciprocity Theorem. Case 3. $\frac{b}{a} = 2.$ Here, we wish to show that there are infinitely many primes $p$ such that $\left ( \frac{2}{p} \right ) = -1$ and $\left ( \frac{-a}{p} \right ) = -1.$ The first condition reads as $p \equiv 3, 5$ (mod $8$). If $a = 1$ we are already done, so otherwise $a$ has an odd prime divisor, say $q$. Then, simply select $p$ to be some arbitrary residue mod $\frac{a}{q}$, and pick it's value modulo $q$ at our discretion. We are then clearly done by the Quadratic Reciprocity Theorem and Dirichlet's Theorem. $\blacksquare$ The following lemma is proven in a similar manner. Lemma 2. For any squarefree $a, b$ with $a \neq b$, there exists infinitely many primes $p$ such that $\left ( \frac{-a}{p} \right ) = -1$ and $\left ( \frac{-b}{p} \right ) = 1.$ Proof. Let $d = \gcd(a, b)$ and $a', b'$ be $\frac{a}{d}, \frac{b}{d}$ respectively. If both $a', b'$ have odd prime divisors, we are done. If any of $a', b'$ are $1$, then we're done by Lemma 1 (e.g. $a' = 1 \Rightarrow a = d|b$). Otherwise, we consider the following two cases. Case 1. $a' = 2$. Then, there is an odd prime divisor $q$ of $b'$ (since $\gcd(a', b') = 1$ and $b' > 1$). As before, select $p$ to be congruent to something arbitrary modulo any prime divisors of $lcm(a, b)$ which are not $2$ or $q$, and $1$ (mod $4$). Then, pick $p$ to be $1$ or $5$ (mod $8$) in order to satisfy $\left( \frac{-a}{p} \right) = -1$, and $p$'s value modulo $q$ to satisfy $\left ( \frac{-b}{p} \right ) = 1.$ Case 2. $b' = 2$. Proof is analogous to the above, left out. $\blacksquare$ With Lemma 2, we are ready to finish. Let $x, y$ be positive integers, to be specified later. From the lemma, for each squarefree $x < n$, we can select a prime $p_x > n$ such that $a^2 + nb^2 \equiv 0$ (mod $p_x$) has nonzero solutions in $a, b$ but $a^2 + b^2 x \equiv 0$ (mod $p_x$) does not. Now, take a solution $(a_x, b_x)$ to the first equation with $p_x^2 \nmid a_x^2 + nb_x^2, p_x \nmid a_x, b_x$, then we stipulate that $x \equiv a_x$ (mod $p_x^2$) and $y \equiv b_x$ (mod $p_x^2$). Since the lemma contains the clause "infinitely many," we can also stipulate that $p_x \neq p_y$ for $x \neq y$. In the end, a solution $(a, b)$ to the resulting system of congruences (exists by CRT) satisfies that $a^2 + nb^2 \in S_n$, but $a^2 + nb^2 \notin S_x$ for any squarefree $x < n$. Indeed, if $a^2 + nb^2 \in S_x$ for some squarefree $x < n$, then we would have that $a^2 + nb^2 = c^2 + xd^2$ for some $c, d \in \mathbb{Z}_{\ge 0}.$ Then, as $p_x | c^2 + xd^2,$ we know that one of $c, d$ is divisible by $p_x$. As $p_x \nmid x$ (since $p_x > n$), this implies that $p_x | c, d$. Therefore, $p_x^2 | c^2 + xd^2 \Rightarrow p_x^2 | a^2 + nb^2$. However, we specifically chose $a_x, b_x$ such that $p_x^2 \nmid a_x^2 + nb_x^2$, and chose $a \equiv a_x, b \equiv b_x$ (mod $p_x^2$), giving us the desired contradiction. $\square$ Please explain "If both $a, \frac{b}{a}$ have some odd prime divisor, the lemma is trivial by Quadratic Reciprocity and Dirichlet. "
17.01.2020 18:43
analysis90 wrote: Please explain "If both $a, \frac{b}{a}$ have some odd prime divisor, the lemma is trivial by Quadratic Reciprocity and Dirichlet. " Pathological describes this technic in cases 1&2.
17.01.2020 21:50
Dadgarnia wrote: For any positive integer $n$, define the subset $S_n$ of natural numbers as follow $$ S_n = \left\{x^2+ny^2 : x,y \in \mathbb{Z} \right\}.$$Find all positive integers $n$ such that there exists an element of $S_n$ which doesn't belong to any of the sets $S_1, S_2,\dots,S_{n-1}$. Proposed by Yahya Motevassel My solution also seems very much similar to the previous solutions. Very nice problem. We claim that the answer is precisely the set of all square-free natural numbers. Necessity - For this we show that $S_{m^2n}\subset S_n$ Let $t\in S_{m^2n} \implies t= x^2+m^2ny^2 \implies t=x^2+n(my)^2 \implies t\in S_n$. Sufficiency - Let $n$ be an square-free natural number . Now we use Chinese Remainder theorem to construct $x$ and $y$ such that $t=x^2+ny^2$ does not lie in any $S_m$ for any $m<n$ Claim 1- For any square-free $m<n$ there exists an odd prime $p_m$ such that $\left(\frac{-m}{p}\right)=-1$ and $\left(\frac{-n}{p}\right)=1$ and all $p_k$ are distinct. Proof- Here we will heavily use Drichlet's Theorem and Quadratic Reciprocity Law For $m=1$ ,we chose $p_1 \equiv 3$ (mod $4$) such that $\left(\frac{n}{p_1}\right)=-1$. For $m>1$ ,let $q$ be a prime dividing $m$ and let $r$ be a prime dividing $n$ such that if $q|n$ then $r=q$ or else it can be anything. Let $U$ be the set of all primes dividing $mn$ other than $q,r$ Let $q' ,r'$ be quadratic non residues modulo $q,r$ respectively. We use Drichlets theorem to find a prime $p_m$ such that $p_m\equiv 1$ (mod $4$) ,$p_m\equiv r'$ (mod $r$), $p_m\equiv q'$ (mod $q$) ,$p_m\equiv 1$ (mod $p$), for all $p\in U$. Note that this prime satisfies our requirements as we can chose it to be as large as we want. Claim 2 - There exists $\alpha_m,\beta_m$ such that $p_m|\alpha_m^2+n\beta_m^2$ but $p_m^2$ doesn't divide it. Proof- As $\left(\frac{-n}{p_m}\right)=1$ there exist $u,v$ such that $(p,uv)=1$ and $p|u^2+nv^2$, if $p^2$ doesn't divide it we are done. If $p^2|u^2+nv^2$ the consider $u+p$ instead of $u$ and we get $(u+p)^2+v^2\equiv 2up \equiv p$ (mod $p^2$) and we are done. Main Part Define $x,y$ such that $x\equiv \alpha_m$ (mod $p_m^2$) and $y\equiv \beta_m$ (mod $p_m^2$). If possible let $t=x^2+ny^2 \in S_l$, let $l=k^2m$ where $m$ is square-free, so $t=u^2+mv^2$ Going mod $p_{m}^2$ we have that $t\equiv p_m$ (mod $p_m^2$). Hence $(p_m,uv)=1$ or else we would have $p_m^2|t$ . So we get that $u^2\equiv -mv^2$ (mod $p_m$), now let $v'$ be such that $vv'\equiv 1$ (mod $p_m$). Then we have $(uv')^2\equiv -m$ (mod $p_m$). Contradiction to $\left(\frac{-m}{p}\right)=-1$. Hence proved.
28.10.2021 09:16
The answer is all squarefree integers. To show that all non-squarefree $n$ does not work,note that $S_{k^2n}\subseteq S_n$ for any $n,k\in\mathbb{Z}^+$. Claim:- For any squarefree $a \in \mathbb{Z}^+$ there exists infinitely many primes $p$ such that $a$ is a quadratic non-residues modulo $p$ Proof:- Many constructions exist a simple one is $$\begin{cases} \text{a is odd} \;\; p=\alpha+\ell_1 \ell_2...........\ell_n \sigma a \; \text{with} \; p \equiv 1 \pmod 4 \\ \text{a is even then any prime p=4ak+ x with x a odd(1 mod 4) quadratic non-residue does the job.} \end{cases}$$ The result follows since all terms in $\{S_x \}_{x <p_1p_2.......p_k}$ have an odd $\nu_p$ whereas $S_n$ has an even $\nu_p$
30.10.2021 13:06
What a beautiful problem !! Here's my solution - Call such an element $e$ to be $n$ good , We claim that a $n$ good element exist if and only if $n$ is square free. First of all we will prove the easy direction--- Suppose we have a $n$ good element $e$ and there exist a prime $p$ such that $p^{2} \mid n$ , let $n = p^{2}. t$ , now as $e$ is $n$ good , there will exist $x, y$ such that $e = x^{2} + ny^{2} = x^{2} + t.(py)^{2}$ , giving $e \in S_{t}$ , but as $t < n$ , this is a contradiction to the goodness of $n$. $\blacksquare$. Now we will prove the harder direction. Suppose $n$ is a square free number , we will construct a $n$ good number $e$. We begin with a crucial claim - Claim - For every natural $x < n$ such that $x$ is not a perfect square , there exist a prime $p \equiv 1 \mod 4$ , such that $\left ( \frac{x}{p} \right ) = -1$ , but $\left ( \frac{n}{p} \right ) = 1$. Proof - Let $n = q_{1}q_{2} \dots q_{k}$ , and $x = p_{1} ^{a_{1}}. p_{2}^{a_{2}} \dots p_{l}^{a_{l}}$. We will construct such a prime $p \equiv 1 \mod 4$. Let $\mathcal{C}$ denotes the set of primes dividing both $n$ and $x$ , note that there exist a $i$ such that $q_{i}$ does not belongs to $\mathcal{C}$. Now as $x$ is not a perfect square , there exist an odd $a_{j}$ , here let $p \equiv b_{j} \mod p_{j}$ , where $b_{j}$ is a quadratic non residue $\mod p_{j}$. From Quadratic reciprocity as $p \equiv 1 \mod 4$ , we get $$\left ( \frac{p}{p_{j}} \right ) \left ( \frac{p_{j}}{p} \right ) = (-1)^{even} = 1$$, giving $\left ( \frac{p_{j}}{p} \right ) = -1$ , now with the same argument for all other primes dividing $x$ and $n$ , make them contribute $-1$. So we will get a congruence of $p$ in modulo all given primes , and such prime will exist by Dirchlet. $\blacksquare$ Now Simply take the pairs $(2,n) , (3,n), \dots (n-1 , n)$ , where second number of each pair is not a perfect square and for each of these pairs let the primes corresponding to above lemma be $r_{2} , r_{3} , ..\dots r_{n-1}$ , where the given primes are not necessarily distinct. Now note that for each prime $r_{i}$ as above mentioned , $-n$ is a quadratic residue , so for each $n$ there exist $t$ such that $-n \equiv t^{2} \mod r_{i}$ , Now from Thue’s lemma , there will exist $m_{i} $ and $n_{i}$ such that $$t \equiv \frac{m_{i}}{n_{i}} \mod r_{i}$$, or equivalently $-n \equiv \frac{{m_{i}}^{2}}{{n_{i}^{2}}} \mod r_{i}$ i.e $$ m_{i} ^{2} + n. n_{i} ^{2} \equiv 0 \mod r_{i}$$. Claim : For a very very big prime and $p \equiv 3 \mod 4$ different from all aforementioned primes there exist $w$ satisfying $ w^{2} \equiv p^{2h-1} \mod p^{2h}$ , for every $h\ge 1$. Proof - Let $g$ be a primitive root $\mod p^{2h}$ , and let $p^{2h-1} \equiv g^{l} \mod p^{2h}$ , so this is equivalent to find a $w$ satisfying $g^{2k} \equiv g^{l} \mod p^{2h}$ , or $2k \equiv l \mod p^{2h-1} . (p-1)$ , where $w \equiv g^{k}$ or equivalently $ k \equiv l . 2^{-1} \mod \frac{p^{2h-1} . (p-1)}{2}$ , which exist as $ gcd ( 2 , \frac{p^{2h-1} . (p-1)}{2}) = 1$ implies $2^{-1}$ exist. $\blacksquare$ Now pick an element $x^{2} + ny^{2}$ from $S_{n}$ such that $$ x \equiv m_{i} \mod r_{i}$$and $$y \equiv n_{i} \mod r_{i}$$for $2 \le i \le n-1$. And $ x \equiv w \mod p^{2h} , y \equiv 0 \mod p^{2h}$ Now such $x , y$ exist by CRT. We will show that this choice of $x, y$ works. Claim - $x^{2} + ny^{2}$ is $n$ good. We will prove that $x^{2} + ny^{2}$ doesn’t belongs to any of the $S_{i} ‘s$ $1 \le i \le n-1$ Case (a) $i$ is perfect square. If $x^{2} + ny^{2}$ $\in S_{i}$ , then it must be sum of $2$ squares , which is not possible as $p$ is a $3 \mod 4$ prime dividing it and $x^{2} + ny^{2} \equiv p^{2h-1} \mod p^{2h}$ i.e $v_{p} (x^{2} + ny^{2})$ = odd. $\blacksquare$ Case (b) - $i$ is not a perfect square. Suppose FTSOC $x^{2} + ny^{2}$ $\in S_{i}$ , then there exist $u , v $ such that $x^{2} + ny^{2} = u^{2} + iv^{2}$ , now as $r_{i}$ divide $x^{2} + ny^{2}$ , it also divide $u^{2} + iv^{2} \equiv 0 \mod q_{i}$ giving $1 = \left ( \frac{-i}{q_{i}} \right ) = \left ( \frac{-1}{q_{i}} \right ). \left ( \frac{i}{q_{i}} \right ) = 1.(-1) = -1$ a contradiction. $\blacksquare$. Hence we are done !!
25.05.2023 09:15
The answer is all squarefree integers. Clearly anything not squarefree fails, as $S_{a^2b}$ is a subset of $S_b$. So it suffices to show that they work. Claim: For any squarefree positive integer $n > 1$, and any $1 \leqslant i < n$, there exists infinitely many primes $q$ such that $-i$ is not a quadratic residue modulo $q$, but $-n$ is. Proof: Since $n$ is squarefree, there exists a prime $p$ dividing $n$ but not $i$. Choose $-1$ to be an NQR, and by quadratic reciprocity and Dirichlet, choose every prime at most $n$ to be a QR, apart from $p$. This ensures the required conditions. $\square$ Note that $p \mid x^2 + ky^2$ means either $p \mid x,y$ or that $-k$ is a quadratic residue modulo $p$. Further, if $-k$ is indeed a QR mod $p$, then we can pick $x,y$ appropriately to ensure that $p$ does divide the value $x^2 + ky^2$. So, for each $1 \leqslant i < n$, let $q_i$ be a prime mentioned in the claim, and pick $x_i, y_i$ such that $\nu_{q_i}(x_i^2 + ny^2) = 1$, also choose the $x_i, y_i$ so that this term is not divisible by any of the other $q_j$, which can be done by CRT. The final observation is that $(a^2 + nb^2)(c^2 + nd^2) = (ac+nbd)^2 + n(ad-bc)^2$ so the product of two numbers in $S_n$ is also in $S_n$. So, we can find $X,Y$ such that $\prod_{i=1}^{n-1} \left(x_i^2 + ny_i^2 \right) = X^2 + nY^2$. I claim this number does not belong to any of the sets $S_1, S_2, \cdots, S_{n-1}$. Suppose not, and it belonged to $S_k$. But then, this implies $q_k$ divides an element of $S_k$, but this is impossible unless $q_k^2$ also divides it. But by construction, the only term divisible by $q_k$ is $x_k^2 + ny_k^2$, which has $\nu_{q_k}$ equal to $1$. This is a contradiction, so this is indeed a new element, so all squarefree numbers do work, as claimed. $\blacksquare$
20.07.2024 13:46
We claim the only solutions are $\boxed{\text{all square-free numbers}}$. It is easy to see that why the non square-free numbers fail obviously. Now for the other direction (obviously $n=1$ works). See that for a number $N \in S_n$, we must have that all primes $p$ which have odd p-adic evaluation, that \[\left(\frac{-n}p \right)=1\]By Quadratic Reciprocity Lemma and Dirichlet's Theorem, there exists infinite such primes. Now let $p_1$, $p_2$, $\dots$, $p_{n-1}$ be distinct such primes, such that all divide $N$ and by Hansel's Lemma, make sure that all of their p-adic evaluation is exactly $1$. Now what is sufficient to do to make sure that $N$ is the number we are looking for, is that \[p_k \nmid a^2+kb^2 \text{ for all squarefree } 1 \leq k \leq n-1 \text{ for any such $a$, $b$}\]See that if $p_k \mid a^2$ or $b^2$ then $\nu_{p_k}(a^2+kb^2) \geq 2$ and so it cannot be $N$. And so we just need to make sure that \[ \left(\frac{-k}{p_k} \right)=-1\]And now see that one can always do this as there is no ``connection" between $k$ and $n$. Remark: I think I should elaborate more on what I meant on the last line. When I say there is no ``connection" it really means because all $p_k$ are distinct, by Quadratic Reciprocity Lemma and Chinese Remainder Theorem, that there are really only ``$2$" conditions on $p_k$, one that $-n$ is a quadratic residue and one that $-k$ isn't and because $-n$ is squarefree, there is no way that the set of prime factors which has odd p-adic evaluation of both $n$ and $k$ are exactly the same.