# Quadratic congruence and primitive roots

From Apostol Chapter $10$ q$6$:

Assume $m>2$, $(a,m)=1$ and there exists an $x$ such that $x^2\equiv a \pmod m$.

Prove that $x^2\equiv a \pmod m$ has exactly two solutions iff $m$ has a primitive root.

I can do the "if" part by explicitly showing that if $g$ is a primitive root of $m$ then if $g^k$ is a soln then $g^{k+\phi(m)/2}$ is the other distinct soln and any soln is congruent to one or the other.

However no progress on the "only if" part.

-
I still can't see how to put the answer in an analytic number theory form. – apatch Dec 14 '11 at 17:47
Despite the title of Apostol's book, not everything in it is analytic by nature. – lhf Dec 17 '11 at 1:36

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

-
+1 This is correct, but I get the feeling that the OP is looking for a solution that does not rely on the known structure theory of the group of units modulo $m$. – Jyrki Lahtonen Apr 15 '12 at 8:03

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<j<|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<2j<2|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.

-

If $m$ does not have a primitive root then the group of units mod $m$ is not cyclic and so factors as a product of cyclic groups. For each factor, the equation has a solution. Now combine the solutions using the Chinese Remainder Theorem. You may want to start with $a=1$ and $m=8$ or $m=15$.

-
Dear @lhf: You seem to imply that a cyclic group is not a product of cyclic groups. – Pierre-Yves Gaillard Dec 13 '11 at 13:06
@Pierre-YvesGaillard, I meant, as a product of two or more cyclic groups that cannot be simplified into one cyclic group. – lhf Dec 13 '11 at 19:01

Well, my answer is pretty elementary. The part to be proved is "if there are exactly two solutions to the congruence $x^2\equiv a\pmod m$, then m must have a primitive root".

According to proof by contrapositive, above statement is equivalent to the statement "If m does not have primitive roots, then the congruence $x^2\equiv a\pmod m$ does not have exactly two solutions".

Now, since m does not have primitive roots, the order of each integer modulo m belongs to the set of proper divisors of $ϕ(m)$. The number of proper divisors of $ϕ(m)$ is given by $τ(ϕ(m)) -1$.

Now, we know that, $2*(τ(ϕ(m)) -1)$ is less than $ϕ(m)$. Therefore, by pigeon-hole principle, each proper divisor of $ϕ(m)$ is the order of more than 2 integers.

Hence, the order of "square root of a modulo m" is shared by more than two integers modulo m, thats why the congruence $x^2\equiv a\pmod m$ does not have exactly two solutions.

We have proved the contrapositive here, which is in turn equivalent to the original statement as given above.

-
This is closer to what I was hoping for. I still am not sure I get the solution as I am struggling with the link between the order of each element and the number of solutions to $x\equiv a \mod m$. – apatch Dec 18 '11 at 14:41
Here, I am saying that the elements co-prime with m with orders as proper divisors of $\phi(m)$ are always more than 2 for each proper divisor. For example, 15 does not have any primitive roots and $\phi(15)=8$. Proper divisors of 8 are 1,2,4. I am saying that the number of elements with order 2 are more than 2, same goes for orders 4 and 1. Now, the congruence $x^2\equiv a\pmod {15}$ has some solution, the order of which will be shared by more than 2 elements which are co-prime to 15. Hope this helps. – NikBels Dec 19 '11 at 6:08
To continue the example, the elements co-prime to 15 are 1,2,4,7,8,11,13,14. The orders are respectively 1,4,2,4,4,2,4,2. No order is shared by exactly two elements, hence the result. One may nitpick as to the fact that order 1 is shared by only 1 element and not more than two. Well, then the statement modifies to "except for order 1, each order is shared by more than two elements". And in any case, exactly two integers don't share the order, so I guess Q.E.D. – NikBels Dec 19 '11 at 6:23

Assume m has a primitive root. Then $$x^2=a \pmod m$$

iff $$2 ind(x)=ind(a) \pmod{\phi(m)}$$

and since $$m>2$$

this has exactly $$d=(2,\phi(m))=2$$

solutions as long as $$2|ind(a)$$

This is the case as there exists an x such that $$x^2=a \pmod m$$

so if $$x=g^k \pmod m$$ where g is a primitive root (mod m) then $$a=g^{(2k)} \pmod m$$ and so $$2|ind(a)$$

This proves the equivalence of the statements.

Can you critique this argument please?

-