Let $P=\{1,2,\cdots,p-1\}$, $P=S\cup T$, prove that $S$ is quadratic residues and $T$ is quadratic nonresidues.

Question

Let $p$ be an odd prime. Assume that the set $\{1,2,\cdots,p-1\}$ can be expressed as the union of two nonempty subsets $S$ and $T$. $S\neq T$, such that the product (mod $p$) of any two elements in the same subset lies in $S$, whereas the product (mod $p$) of any element in $S$ with any element in $T$ lies in $T$. Prove that $S$ consists of the quadratic residues and $T$ of the nonresidues mod $p$.

My proof:

Let $P=\{1,2,\cdots,p-1\}$, we first prove $T\neq P$, and we do this with argued by contradiction, so assume $T=P$, then $1\in T$, choose any $n\in P$, then $n\in T$, since product of any two elements in the same subset (here is $T$) lies in $S$, we see $1\cdot n=n\in S$, which mean $S=P=T$, contradiction. Therefore $T\neq P$.

Now let $a\in P$ be a primitive root modulo $p$, if $a\in S$, then any power of $a$ will be in $S$, which says $S=P$. But $T$ is nonempty, we can choose $b$ in $T$, then the set $bS$ will also equal to $P$, which is $T=P$, contradiction. Therefore we must have $a\in T$, and so $a^2\in S$, and so $\{a^2,a^4,\cdots,a^{p-1}=1\}\subseteq S$. Now we argued by contradiction that the set $\{a^2,a^4,\cdots,a^{p-1}\}$ is $S$. If there is odd number $k$ such that $a^k\in S$, then by $a\in T$, we choose $a^{2h}\in S$ we conclude that $a^{2h+1}\in T$, so that $a^{2h+k+1}\in T$, which says all powers of $a$ in $T$, so $T=P$, contradiction. Therefore $S=\{a^2,a^4,\cdots,a^{p-1}\}$ contains the quadratic residues, so every odd power of $a$ is in $T$, this says $T$ is nonresidues mod $p$.

I think my proof is okay, but the only bad thing is I have used 'primitive root' in my solution, which is not obvious in this question. I know every odd prime $p$ has primitive root mod $p$, but I will be more satisfied if there is a proof not using primitive root, and this can be better to teach people who don't have knowledge about primitive root.

To fulfill this purpose, I throw my second paragraph, and I want to prove either of the following:

• If $a\in S$ then $a$ is a quadratic residue.

• If $b\in T$ then $b$ is a quadratic nonresidue.

• Since $S\neq T$ and $S\cup T=P$, we can choose $a\in S, a\notin T$, prove that $a$ is a quadratic residue.

• Since $S\neq T$ and $S\cup T=P$, we can choose $b\in T, b\notin S$, prove that $b$ is a quadratic residue.

Prove either one of above will lead to a big improvement, of course other solution is appreciated.

Answer 1

I think there is a proof without using primitive roots:

1. We know there are $\frac{p-1}{2}$ quadratic residues because $a^2=b^2 \mod p \iff a = \pm b \mod p$. So there must be $\frac{p-1}{2}$ non-residues.

2. For any $a \in P$, either $a\in S$ or $a \in T$ (or both). In either case $a^2 \mod p \in S$. Therefore all quadratic residues are in $S$.

3. If there is any non-residue $b$ in $S$ then the product of $b$ with each of the quadratic residues (which are in $S$) will also be in $S$. But these $\frac{p-1}{2}$ products are distinct. So all non-residues will be in $S$. By a similar argument if there is any non-residue in $T$ then all non-residues will be in $T$.

4. If $S$ contains all residues and all non-residues then $S=P$. In that case either $T$ is empty or $S=T=P$. But both these possibilities are ruled out by the conditions of the question.

5. Therefore $S$ contains all residues and only residues and $T$ contains all non-residues and only non-residues.