Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 6 down vote accepted

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

share|cite|improve this answer
+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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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