Partition Subsets with residues modulo $p$ Think of the set $S={1, 2, ..., p-1}$ where $p$ is a prime. Now think of two subsets $A, B$ of $S$ which satisfies these conditions.


*

*$A\cup B=S$ and $A\cap B=\emptyset$

*For every pair of two elements $(x, y)$ on $A$ or $B$, let $xy\equiv k \pmod{p}$. Then $k\in A$.

*For every pair of two elements $(x, y)$ which satisfies $x\in A$ and $y\in B$, let $xy\equiv k \pmod{p}$. Then $k\in B$.
Prove or disprove that the only pair of such sets $(A, B)$ is, $A$ is the set of quadratic residues and $B$ is the set of quadratic nonresidues.
I proved that there are no primitive roots in $A$. By using this fact, I could prove the problem when $p$ is a prime. I see that my method works for every integer that has a primitive root. But the problem statement seems to work for every integer $n$. (Which means that $S=Z_n^*$.) But I can't prove it.
Lemma 4
There are no primitive roots of $p$ in the set $A$.
Proof) Assume the contrary. Consider the primitive root $r$ of $p$ such that  $r\in A$.  If there exists an element such that $a\neq r$ and $a \in A$, then $ar\in A$. Consequently, $\S=\{ar, ar^2, ... ,ar^{p-1}\}\subset A$ and elements in the set $S$ are all different. By the property of primitive root, $S$ = $Z_p^*$, so $B=\emptyset$, which is a contradiction.
Hence there is no other elements in the set $A$ rather than $r$.
Think of the element $1$. If $1\in B$, then $1\times r=r\in B$, but $r\in A$ and this is a contradiction.
Therefore there are no primitive root in the set $A$.
Assume $p\ge 5$. Think of a primitive root $r$ of $p$. Then by Lemma 4, $r\in B$. The set $A$ is nonempty, so there exists some element $a\in A$. Now $a\times r=ar\in B$. Also $ar\times r=ar^2\in A$. Consequently, $\{ar, ar^3, ar^5, ..., ar^{p-2}\}\subset B$ and $\{a, ar^2, ar^4, ..., ar^{p-1}\}\subset A$.
We now know that $\{ar, ar^3, ar^5, ..., ar^{p-2}\}\cup\{ar^2, ar^4, ..., ar^{p-1}\}=\{ar, ar^2, ar^3, ..., ar^{p-1}\}=Z_p^*$, so therefore if the "good partition" exists, then it should be partitioned like this, so $A=\{ar, ar^3, ar^5, ..., ar^{p-2}\}$ and $B=\{ar^2, ar^4, ..., ar^{p-1}\}$. But we know that $r\in B$, so there exists some nonnegative integer $t$ such that $ar^{2t+1}=r$. By the Legendre Symbol, $(\frac{ar^{2t}}{p})=(\frac{a}{p})=1$, so $a$ is a quadratic residue. Thus, for some element $u=ar^{2k} (k\in Z)$ in $A$, the Legendre Symbol of $u$ modulo $p$ is $(\frac{ar^{2k}}{p})=(\frac{a}{p})=1$. Similarly for some element $v=ar^{2k+1} (k\in Z)$ in $B$, the Legendre Symbol of $v$ modulo $p$ is $(\frac{ar^{2k+1}}{p})=(\frac{a}{p})(\frac{r}{p})=-1$. Therefore $A$ is the set of quadratic residues, and $B$ is the set of quadratic nonresidues. Now by Theorem 1, this partition satisfies the problem statement. Hence the claim.
 A: Great additions to the problem statement.
Perhaps surprisingly, when the modulus does not have primitive roots, the division into quadratic residues and nonresidues does not satisfy property (2)—more specifically, the product of two quadratic nonresidues does not have to be a quadratic residue. (Examples: $3\times5\equiv7\pmod 8$ and $5\times7\equiv11\pmod{12}$.)
In the language of group theory, the conditions are saying that $A$ is a subgroup of $S$ of index $2$, and $B$ is the nontrivial coset of $A$. But when the modulus $q$ does not have primitive roots, the subgroup of quadratic residues does not have index $2$—indeed, it has index $2^{\omega(q)+\delta}$ where $\omega(q)$ is the number of distinct prime factors of $q$ and $\delta\in\{-1,0,1\}$ depends upon the power of $2$ dividing $q$.
There are (multiple) possibilities for $A$ and $B$ when the modulus does not have primitive roots. For example, when $q=8$, we can take $A=\{1,3\}$ or $A=\{1,5\}$ or $A=\{1,7\}$. When $q=24$ we can take $A=\{1,a,b,ab\}$, where $a$ and $b$ are any two distinct elements of $S\setminus1=\{5,7,11,13,17,19,23\}$. When $q=p_1p_2$ where $p$ is prime, we can take $A$ to be all elements of $S$ that are quadratic residues (mod $p_1$) regardless of whether they are quadratic residues (mod $p_2$) and thus (mod $q$), or we can exchange $p_1$ and $p_2$. And so on....
