Quadratic congruence and primitive roots

Solution 1:

If you are looking for something more elementary, let's try the following.

Assume contrariwise that the number of solutions of the equation $x^2=a$ in the group $G=\mathbf{Z}_m^*$ is positive but not equal to two.

Is it possible that the equation would have only one solution? No! If $b$ is a solution, then $-b$ is also a solution. For $b$ and $-b$ to be the same solution, we must have $b\equiv -b\pmod m$, or equivalently $m\mid 2b$. As $m>2$, this means that $m$ and $b$ have a common factors, and hence so do $m$ and $a\equiv b^2$ contradicting the assumption that $\gcd(a,m)=1$.

Is it possible that the equation would have at least three solutions? Say, $x_1,x_2,x_3$ are pairwise non-congruent integers all with the property $x_i^2= a$ in $G$. In this case the elements $y_1=x_1x_3^{-1}$ and $y_2=x_2x_3^{-1}$ both satisfy the equation $$ y_i^2=x_i^2x_3^{-2}=aa^{-1}=1,\qquad i=1\ \text{or}\ 2. $$ Furthermore, as the $x_i,i=1,2,3,$ were pairwise non-congruent, we have $y_1\neq1\neq y_2$.

OTOH if $G$ were cyclic, say $G=\langle r\rangle$, then the equation $y^2=1$ can have at most a single non-trivial solution $y\neq1$ in $G$. We see this as follows. The element $y=r^j$, $0&ltj&lt|G|$, is a non-trivial solution of $y^2=1\Leftrightarrow r^{2j}=1\Leftrightarrow |G|$ divides $2j$. Here $2j$ can be divisible by $|G|$ only, when $2j=|G|$, because we know that $0&lt2j&lt2|G|$.

So we have shown that if $x^2=a$ has more than two solutions, then $G$ cannot be cyclic, i.e. $m$ cannot have a primitive root.

Solution 2:

The statement is equivalent to

(1) $(\mathbb Z/m\mathbb Z)^\times$ is cyclic if and only if its largest two subgroup is,

which results immediately from

(2) $(\mathbb Z/m\mathbb Z)^\times$ is cyclic if and only if $m$ is of the form $2, 4, p^j, 2p^j$, where $p$ is an odd prime.

Statement (2) is proved on page 24 of Alan Baker's A concise introduction to the theory of numbers.

EDIT 1. Here is a slightly expanded version of the above answer.

For any positive integer $m$, let $G_m$ be the multiplicative group of the ring $\mathbb Z/m\mathbb Z$, and $T_m$ the largest $2$-subgroup of $G_m$.

Denote by $S$ the set of those positive integers which are equal to $2$, or to $4$, or to a power of an odd prime, or to twice a power of an odd prime.

Let $m$ be a positive integer. We claim:

$(3)$ If $m$ is in $S$, then $G_m$, and a fortiori $T_m$, are cyclic.

$(4)$ If $m$ is not in $S$, then $T_m$, and a fortiori $G_m$, are not cyclic.

In case $(4)$, the group $G_m$ is a product of two groups of even order, and the conclusion is clear.

To prove $(3)$ we can assume that $m$ is a power $p^n$ of an odd prime $p$. We can also suppose that the exponent $n$ is at least $2$.

Let $a$ be a primitive root mod $p$. In particular is $a^{p-1}$ is of the form $1+pb$.

Put $c:=a+px$, and let's try to choose $x$ in such a way that $c$ is a primitive root mod $p^n$.

By computing mod $p$ we see that the order of $c$ in $G_m$ is not a power of $p$. Thus, it is enough to check that $c^{(p-1)p^{n-2}}$ is not congruent to $1$ mod $p^n$. We have $$ c^{p-1}\equiv1+p\ (b+(p-1)\ a^{p-2}\ x)\ \bmod\ p^2, $$ and thus $c^{p-1}\equiv1+p$ mod $p^2$ for some $x$. By induction we get $$ (c^{p-1})^{p^i}\equiv1+p^{i+1}\ \bmod\ p^{i+2} $$ for all positive integers $i$, and in particular $$ (c^{p-1})^{p^{n-2}}\equiv1+p^{n-1}\ \bmod\ p^n. $$ QED

EDIT 2. The following fact has been used. Let $G$ be a finite (multiplicative) abelian groups. Then $G$ can be decomposed as a product of cyclic groups. Let $n$ be the number of even factors. Then the number of solutions $x$ to the equation $x^2=a^2$ is $2^n$, where $n$ is the number of even order factors in the decomposition. (This shows in particular that $n$ depends only on $G$.)