Iranian Mathematical Olympiad

Answer. Any square-free number.

Since $S_j$ doesn't exist for $j\le 1$, the statement is held for $i=1$. On the other hand if for an integer $n>1$ there exists a prime number $p$, which $p^2\mid n$, $n$ is not a valid number; Because for all integer numbers $x,y$ $$x^2+n{y}^2=x^2+\left(\frac{n}{p^2}\right)(yp{)}^2.$$ which means that $$S_n\subseteq S_{\frac{n}{p^2}}.$$ Now we prove that any square-free number has the property.

Lemma. If $n$ is a square-free positive integer then there are distinct odd prime numbers $p_k$ for $1\le k\le n-1$ where $-n$ is a quadratic residue modulo $p_k$ but $-k$ is not. i.e. in Legendre symbol $$\left(\frac{-n}{p_k}\right)=1,\left(\frac{-k}{p_k}\right)=-1.(1)$$ Proof. Assume that $n=q_1\dots q_m$, where $q_i$'s are prime numbers. The claim is that at least one of the $q_i$'s does not divide $k$; otherwise if for $1\le i\le m$ $q_i$ divides $k$ then $$n\mid k⟶n\le k;$$ Which is a contradiction. Without loss of generality assume that $q_m$ is one of the numbers that does not divide $k$. So $k=q_1\dots q_r{\ell }_1\dots {\ell }_t{D}^2$ where $0\le r<m$. If $q_1\dots q_m{\ell }_1\dots {\ell }_t$ is an odd number then the numbers $4,q_1,\dots ,q_m,{\ell }_1,\dots ,{\ell }_t$ are pairwise coprime so by applying the Chinese remainder theorem there exists an integer $x$ where $$\{\begin{array}{ll}x\equiv 3(\mathrm{mod}4)& \\ x\equiv -1(\mathrm{mod}{q}_i)& 1\le i\le m-1\\ x\equiv u(\mathrm{mod}{q}_m)& \\ x\equiv -1(\mathrm{mod}{\ell }_i)& 1\le i\le t.\end{array}$$ Where $u$ is an integer number which $-u$ is a non-quadratic residue modulo $q_m$. Notice that thus $q_m$ is an odd prime number such a number exists. Because $x$ and $4q_1\dots q_m{\ell }_1\dots {\ell }_t$ are coprime, By applying Dirichlet theorem, there are infinitely many prime numbers of the form $x+4q_1\dots q_m{\ell }_1\dots {\ell }_{t}d$. Take one of those like $p_k$ where $p_k>\max (n,3)$. By applying the law of quadratic reciprocity for odd prime numbers $p_k$ and $q_j$ $$\left(\frac{p_k}{q_j}\right)\left(\frac{q_j}{p_k}\right)=(-1{)}^{\frac{(p_k-1)(q_j-1)}{4}}.(2)$$ $$p_i\equiv 3(\mathrm{mod}4)⟹\frac{p_k-1}{2}\equiv 1(\mathrm{mod}2)$$ So $$(-1{)}^{\frac{(p_k-1)(q_j-1)}{2}}=(-1{)}^{\frac{q_j-1}{2}}.$$ It's easy to check that $$\left(\frac{-1}{q_j}\right)=(-1{)}^{\frac{q_j-1}{2}}.$$ Also for $1\le j\le m-1$ $$\left(\frac{p_k}{q_j}\right)=\left(\frac{-1}{q_j}\right).$$ Then according to (2) $$\left(\frac{p_k}{q_j}\right)\left(\frac{q_j}{p_k}\right)=\left(\frac{-1}{q_j}\right)\left(\frac{q_j}{p_k}\right)=(-1{)}^{\frac{(p_k-1)(q_j-1)}{4}}=(-1{)}^{\frac{q_j-1}{2}}=\left(\frac{-1}{q_j}\right).$$ So $$\left(\frac{q_j}{p_k}\right)=1\forall j:1\le j\le m-1$$ In the same way $$\left(\frac{{\ell }_s}{p_k}\right)=1\forall s:1\le s\le t.$$ In addition $$\left(\frac{p_k}{q_m}\right)\left(\frac{q_m}{p_k}\right)=(-1{)}^{\frac{(p_k-1)(q_m-1)}{4}}=(-1{)}^{\frac{q_m-1}{2}}=\left(\frac{-1}{q_m}\right).$$ Also $$\left(\frac{p_k}{q_m}\right)\left(\frac{q_m}{p_k}\right)=\left(\frac{u}{q_m}\right)\left(\frac{q_m}{p_k}\right)=\left(\frac{-1\times -u}{q_m}\right)\left(\frac{q_m}{p_k}\right)=-\left(\frac{-1}{q_m}\right)\left(\frac{q_m}{p_k}\right)$$ So $$-\left(\frac{-1}{q_m}\right)\left(\frac{q_m}{p_k}\right)=\left(\frac{-1}{q_m}\right)⟶\left(\frac{q_m}{p_k}\right)=-1$$ Since the Legendre symbol is a completely multiplicative function of its top argument, then $$\begin{array}{rl}\left(\frac{-k}{p_k}\right)& =\left(\frac{-1}{p_k}\right)\prod _{j=1}^r\left(\frac{q_j}{p_k}\right)\prod _{s=1}^t\left(\frac{{\ell }_s}{p_k}\right)\left(\frac{D^2}{p_k}\right)=\left(\frac{-1}{p_k}\right)\prod _{j=1}^r\prod _{s=1}^{t}1=-1,\\ \left(\frac{-n}{p_k}\right)& =\left(\frac{-1}{p_k}\right)\prod _{j=1}^m\left(\frac{q_j}{p_k}\right)=\left(\frac{-1}{p_k}\right)\left(\frac{q_m}{p_k}\right)\prod _{j=1}^{m-1}1=-1\times -1=1.\end{array}$$ So if $n$ and ${\ell }_1\dots {\ell }_t$ are odd numbers, $p_k$ has been found. If one is ${\ell }_j$'s is two; Assume that ${\ell }_t=2$ and take $$\{\begin{array}{ll}x\equiv 7(\mathrm{mod}8)& \\ x\equiv -1(\mathrm{mod}{q}_i)& 1\le i\le m-1\\ x\equiv u(\mathrm{mod}{q}_m)& \\ x\equiv -1(\mathrm{mod}{\ell }_i)& 1\le i\le t-1.\end{array}$$ Since $q_m$ does not divide $k$ then it is an odd prime number and like before $u$ exists. Because $x$ and $8q_1\dots q_m{\ell }_1\dots {\ell }_{t-1}$ are coprime, By applying Dirichlet theorem, there are infinitely many prime numbers of the form $x+8q_1\dots q_m{\ell }_1\dots {\ell }_{t-1}d$. Take one of those like $p_k$ where $p_k>\max (n,3)$. Thus $$\left(\frac{2}{p_k}\right)=(-1{)}^{\frac{p_k^2-1}{8}}=1$$ So $$\left(\frac{{\ell }_1}{p_k}\right)=1$$ and the proof is the same as before. Also if one of the $q_1,q_2,\dots ,q_{m-1}$ is two the proof is still as before. Now assume that $q_m=2$. $$\{\begin{array}{ll}x\equiv 3(\mathrm{mod}8)& \\ x\equiv -1(\mathrm{mod}{q}_i)& 1\le i\le m-1\\ x\equiv -1(\mathrm{mod}{\ell }_i)& 1\le i\le t-1.\end{array}$$ In this case (By applying Dirichlet theorem we can take $p_k$ similarly) $$\left(\frac{2}{p_k}\right)=(-1{)}^{\frac{p_k^2-1}{8}}=-1.$$ So $$\left(\frac{q_m}{p_k}\right)=-1.$$ And the proof of the lemma is done.

Now back to the main problem. Take $p_1,p_2,\dots ,p_{n-1}$ as lemma says. Because $-n$ is a quadratic residue mod $p_i$, there exists an integer number $a$ such that $$a^2\equiv -n(\mathrm{mod}{p}_i)⟹a^2+n\equiv 0(\mathrm{mod}{p}_i).$$ Also $$(a+p_i{)}^2+n-(a^2+n)=p_i(2a+p_i).$$ Since $n\ne 0(\mathrm{mod}{p}_i)$ and $p_i$ is odd then $2a$ is not divisible by $p_i$ and then $2a+p_i$ is not divisible by $p_i$. So if $a^2+n$ is divisible by $p_i^2$ then $(a+p_i{)}^2+n$ is not and $$(a+p_i{)}^2+n\equiv 0(\mathrm{mod}{p}_i).$$ So there exists an integer number $x_i\in \{a,a+p\}$ which $$\{\begin{array}{l}(x_i{)}^2+n\equiv 0(\mathrm{mod}{p}_i)\\ (x_i{)}^2+n\not\equiv 0(\mathrm{mod}{p}_i^2).\end{array}$$ The numbers $p_1^2,p_2^2,\dots ,p_{n-1}^2$ are pairwise coprime so by applying Chinese remainder theorem there exists an integer number $x$ such that $$x\equiv x_k(\mathrm{mod}{p}_k^2)\forall j:2\le j\le l.$$ Claim 1. The number $x^2+n$ doesn't belong to any of the subsets $S_1,S_2,\dots ,S_n$. Proof. If not, then there is an integer $1\le r\le n-1$ which $x^2+n\in S_r$. Because $1\le r\le n-1$ so take $p_r$. Also there exists integer numbers $u,v$ such that $$x^2+n=u^2+r{v}^2.(3)$$ By the definition of $p_r$ $$\{\begin{array}{l}x\equiv x_r(\mathrm{mod}{p}_r),\\ (x_r{)}^2+n\equiv 0(\mathrm{mod}{p}_r),\\ (x_r{)}^2+n\not\equiv 0(\mathrm{mod}{p}_r^2).\end{array}(4)$$ According to equation (3) $$u^2+r{v}^2\equiv 0(\mathrm{mod}{p}_r).$$ Since $r\ne 0(\mathrm{mod}{p}_r)$, then $$u\equiv 0(\mathrm{mod}{p}_r)⟺v\equiv 0(\mathrm{mod}{p}_r).$$ So if one of them is divisible by $p_i$ then the another one is too and then the whole number $u^2+r{v}^2$ will be divisible by $p_i^2$ which contradicts with (4). Also $$u^2+r{v}^2\equiv 0(\mathrm{mod}{p}_r)⟹u^2\equiv (-r)v^2(\mathrm{mod}{p}_r).$$ By Taking $\frac{p_r-1}{2}$ exponent of each side of the last equivalence $$u^{p_r-1}\equiv (-r{)}^{\frac{p_r-1}{2}}{v}^{p_r-1}(\mathrm{mod}{p}_r).(5)$$ Since $u,v\not\equiv 0(\mathrm{mod}{p}_r)$ by Fermat's little theorem $$u^{p_r-1}\equiv v^{p_r-1}\equiv 1(\mathrm{mod}{p}_r)$$ And from (5) $$(-r{)}^{\frac{p_r-1}{2}}\equiv 1(\mathrm{mod}{p}_r).$$ Let $g$ be the primitive root of the ${\mathbb{Z}}_p^{\ast }$ so there exists an integer number $m$ which $$g^m\equiv -r(\mathrm{mod}{p}_r).$$ By Taking $\frac{p_r-1}{2}$ exponent of each side of the equivalence $$g^{\frac{p_r-1}{2}}\equiv (-r{)}^{\frac{p_r-1}{2}}\equiv 1(\mathrm{mod}{p}_r).$$ Since the order of $g$ is $p_r-1$ in ${\mathbb{Z}}_p^{\ast }$ $$p_r-1\mid m\frac{p_r-1}{2}⟹2\mid m.$$ So $m$ is an even number and then $-r$ is a quadratic residue which is a contradiction. This contradiction shows that our first assumption that $x^2+n$ belongs to $S_r$ is wrong so $n$ has the property that is mentioned in the question. So all of the numbers with the property have been found. $\square$