# Is the subgroup of quadratic residues modulo $N = pq$ a cyclic group if $p$ and $q$ are primes?

I saw this question When is the group of quadratic residues cyclic? and the answers to that.

I have a similar question. Assume $N=pq$ where $p$ and $q$ are primes. We know that $\mathbb{Z}^*_N$ is not cyclic. So my question is what can we say about the subgroup of quadratic residues modulo $N$? Is it cyclic, or non cyclic?

-

The direct product of two cyclic groups is cyclic if and only if their orders are relatively prime. Your group is a direct product of cyclic groups of order $(p-1)/2$ and $(q-1)/2$ respectively (the quadratic residues modulo $p$ and modulo $q$), so it is cyclic if and only if $\gcd(p-1,q-1)=2$.

-
+1 Beat me to it by about a minute. – Jyrki Lahtonen Aug 19 '12 at 20:27

Let $p$ and $q$ be prime. If one of the primes is $2$, or $p=q$, then the squares form a cyclic group. This is because the full multiplicative group is cyclic, and if $g$ is a primitive root of $2p$ or $p^2$, then $g^2$ generates our group of squares.

Now let $p$ and $q$ be distinct odd primes. The group of quadratic residues modulo $pq$ is the direct product of two cyclic groups of orders $\frac{p-1}{2}$ and $\frac{q-1}{2}$. This will be cyclic precisely if the orders of the two groups are relatively prime.

To make sure they are relatively prime, we need to have at least one of the two primes of the form $4k+3$. In addition, we must have $p\nmid q-1$ and $q\nmid p-1$. There are infinitely many pairs $(p,q)$ that satisfy these criteria. For example, we can let $p=3$ and $q$ a prime of the form $6k-1$.

It is also easy to produce infinitely many pairs $(p,q)$ of distinct odd primes for which the group of squares is not cyclic. The easiest way is to let $p$ and $q$ be distinct primes of the form $4k+1$.

-