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.

  1. $A\cup B=S$ and $A\cap B=\emptyset$

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

  3. 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.

  • 1
    $\begingroup$ What are your thoughts? What have you tried? Where are you stuck? You need to provide context for your question. Right now, it just looks like you want somebody to do your homework for you; that's not what this site is for. If you add some appropriate context, we will be happy to help. $\endgroup$ – Greg Martin Jun 11 '19 at 1:37
  • $\begingroup$ Added a lot of progress. $\endgroup$ – Hypernova Jun 11 '19 at 14:27

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....

  • $\begingroup$ I see something fun. If there exists a odd prime p dividing n then we can take A to be all the elements of S that are quadratic residues mod p and take B to be the rest. For $n=2^k$, it seems that such partition always exists. How can I prove this? $\endgroup$ – Hypernova Jun 12 '19 at 5:43
  • $\begingroup$ Also I see this. When we take $A$ to be all the elements of $S$ that are quadratic residues modulo n then it doesn't work. But for an element $a\in A$, when we add $n-a$ into $A$ for every single $a$ and say it $A$. Then $A$ seems to work fine. what about this? $\endgroup$ – Hypernova Jun 12 '19 at 5:49
  • $\begingroup$ For $n=2^k$, you can let $A$ be all the elements that are $1\pmod 4$ and $B$ be all the elements that are $3\pmod 4$. Your second construction works occasionally, but not for all moduli: take $n=24$ or $n=60$ or $n=105$, for example—the resulting $A$ still doesn't have enough elements. It also doesn't work for $n=65$ (for example) because $n-a$ is already a quadratic residue, so you don't add anything new. $\endgroup$ – Greg Martin Jun 12 '19 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.