17
$\begingroup$

If a and b are two quadratic residues of the prime p, then it is easily checked that ab is also a quadratic residue modulo p; if c is a quadratic residue modulo p, and $ {cd \equiv {1} \pmod{p} } $, then since 1 is a quadratic residue of p, d is a quadratic residue of p; so the set of all quadratic residues form a group, denoted by $ \mathfrak R $. And my question is:

When is $ \mathfrak R $ cyclic?

I am very sorry not able to provide more motivations for studying this question; I want to know out of pure curiosity; it will be appreciated if anyone provides some insight or hint, thanks very much.

$\endgroup$
3
  • 8
    $\begingroup$ It's always cyclic. If $g$ is a primitive root mod $p$, then $g^2$ is a generator of the group of quadratic residues. $\endgroup$ Apr 4, 2011 at 3:03
  • 11
    $\begingroup$ More generally: it is a finite subgroup of the multiplicative group of a field, and such things are always cyclic. $\endgroup$ Apr 4, 2011 at 3:11
  • $\begingroup$ @Mariano Suárez-Alvarez: Also thanks very much. $\endgroup$
    – awllower
    Apr 4, 2011 at 3:13

2 Answers 2

12
$\begingroup$

The original question has been answered (they are always a cyclic group). Perhaps slightly more interesting is:

Fix $m\gt 0$. Then the subset of the units modulo $m$ that are squares forms a subgroup of the invertible elements modulo $m$. When is this subgroup cyclic?

If there is a primitive root modulo $m$ (that is, if the group of units modulo $m$ is cyclic), then the property holds. This occurs when $m$ is a power of an odd prime, twice a power of an odd prime, $m=2$, or $m=4$.

It also holds if $m=8$, since then the only quadratic residue is $1$, so the group of quadratic residues is cyclic. In fact, it holds if $m=2^n$ is a power of $2$, the result holds: because the group of units modulo $2^n$ is isomorphic to $C_{2^{n-2}}\times C_2$ (where $C_k$ is the cyclic group of order $k$), so the group of squares is isomorphic to $C_{2^{n-3}}$, which is cyclic.

Other nontrivial examples include $m=3p^a$ or $m=6p^a$ where $p$ is an odd prime and $a\gt 0$, $m=35 = 5\times 7$ (or more generally, $m=5^a 7^b$); and many others.

To get the complete answer, factor $m$ into primes, $$ m = p_1^{a_1}\cdots p_r^{a_r}$$ where $p_1\lt p_2\lt\cdots\lt p_r$ are primes, and $a_r\gt 0$. By the Chinese Remainder Theorem, the group of units modulo $m$ is $$\left(\mathbb{Z}/m\mathbb{Z}\right)^* = \prod_{i=1}^r \left(\mathbb{Z}/p_i^{a_i}\mathbb{Z}\right)^*.$$

The group of units modulo $p_i^{a_i}$ is

  • Cyclic of order $(p_i-1)p_i^{a_i-1}$ if $p_i$ is odd;
  • Trivial if $p_i=2$ and $a_i = 1$;
  • Isomorphic to $\displaystyle C_{2^{a_i-2}}\times C_2$ if $p_i=2$ and $a_i\gt 1$.

The group of squares of invertible elements modulo $m$ is then isomorphic to a product of groups of the form

  • Cyclic of order $\frac{p_i-1}{2}(p_i^{a_i-1})$ if $p_i$ is odd;
  • Trivial if $p_i=2$ and $a_i\leq 2$;
  • Cyclic of order $2^{a_i-3}$ if $p_i=2$ and $a_i\geq 3$.

The product is cyclic if and only if the orders of the cyclic factors are pairwise relatively prime.

This gives:

Theorem. Let $m$ be a positive integer, and let $p_1,p_2,\ldots,p_r$ be the distinct prime divisors of $m$, $p_1\lt p_2\lt\cdots\lt p_r$. Let $\varphi$ be Euler's totient function. The subgroup of squares of the invertible elements modulo $m$ is cyclic if and only if:

  1. For $m$ odd,
    • $\displaystyle\gcd\left(\frac{\varphi(p_i^{a_i})}{2},\frac{\varphi(p_j^{a_j})}{2}\right) = 1$ for all $1\leq i\lt j\leq r$.
  2. For $m$ even,
    • $\displaystyle\gcd\left(\frac{\varphi(p_i^{a_i})}{2},\frac{\varphi(p_j^{a_j})}{2}\right) = 1$ for $1\lt i\lt j\leq r$; and
    • if $2^a$ is the largest power of $2$ that divides $m$ and $a\gt 3$, then $p_i\equiv 3\pmod{4}$ for all $i\gt 1$.

It is straightforward now to show (e.g., using Dirichlet's theorem on primes in arithmetic sequences) that there are $m$ with arbitrarily many distinct prime divisors for which the subgroup of squares of the units modulo $m$ is cyclic.

$\endgroup$
4
  • $\begingroup$ In line 10, perhaps you mean (($p_i$)-1)($(p_i)^{a_i -1})$?? $\endgroup$
    – awllower
    Apr 4, 2011 at 4:46
  • 2
    $\begingroup$ In any case, c'est magnifique. $\endgroup$
    – awllower
    Apr 4, 2011 at 4:47
  • $\begingroup$ @awllower: I don't think it's line 10, but I think I see what you mean. Thanks! $\endgroup$ Apr 4, 2011 at 4:48
  • $\begingroup$ Ah! It's line 20, sorry... $\endgroup$
    – awllower
    Apr 7, 2011 at 13:12
10
$\begingroup$

The group of quadratic residues $\bmod p$ is always cyclic, since if $g$ is a primitive root then $g^2$ generates it. More generally, as Mariano says, every finite subgroup of the multiplicative group of a field is cyclic.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .