Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
7  
It's always cyclic. If $g$ is a primitive root mod $p$, then $g^2$ is a generator of the group of quadratic residues. –  Qiaochu Yuan Apr 4 '11 at 3:03
    
@Qiaochu Yuan, thanks. And I would like to accept this answer, if you put it. –  awllower Apr 4 '11 at 3:11
10  
More generally: it is a finite subgroup of the multiplicative group of a field, and such things are always cyclic. –  Mariano Suárez-Alvarez Apr 4 '11 at 3:11
    
@Mariano Suárez-Alvarez: Also thanks very much. –  awllower Apr 4 '11 at 3:13

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
In line 10, perhaps you mean (($p_i$)-1)($(p_i)^{a_i -1})$?? –  awllower Apr 4 '11 at 4:46
1  
In any case, c'est magnifique. –  awllower Apr 4 '11 at 4:47
    
@awllower: I don't think it's line 10, but I think I see what you mean. Thanks! –  Arturo Magidin Apr 4 '11 at 4:48
    
Ah! It's line 20, sorry... –  awllower Apr 7 '11 at 13:12

Your Answer

 
discard

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.