# integer $m$ has primitive root if and only if the only solutions of the congruence $x^{2} \equiv 1 \pmod m$ are $x \equiv \pm 1\pmod m$.

Show that the integer $m$ has primitive root if and only if the only solutions of the congruence $x^{2} \equiv 1 \pmod m$ are $x \equiv \pm 1\pmod m$.

I don't quite understand what this question is asking for, I thought primitive roots had order $\phi(m)$.

• Do you know Gauss' theorem about the cyclicity of $\mathbb Z_m$, i.e. the usual classification of the $m$ that "have primitive roots"? – Tomas Nov 28 '13 at 19:43
• Nope I dont think I know what that is – DJ_ Nov 28 '13 at 20:08
• Gauss theorem is "There is a primitive root modulo $m$ if and only if $m$ is either $2, 4$, a power of an odd prime or twice the power of an odd prime." Knowing this helps. – Tomas Nov 28 '13 at 20:10
• math.stackexchange.com/questions/345668/… – lab bhattacharjee Nov 29 '13 at 4:08

Let $m\geq 3$ and $g$ is a primitive root modulo $m$. Then $\mathbb Z^*_m$ can be fully represented by $\{g_0,\dots,g^{\varphi(m)-1}\}$. Hence, any $x\in \mathbb Z^*_m$ can be written as $x=g^k$ for some $0\leq k<\varphi (m)$ and working in $\mathbb Z_m$: $$x^2=1 \Leftrightarrow (g^k)^2= 1 \Leftrightarrow g^{2k}= 1 \Leftrightarrow \varphi(m) \mid 2k$$ which is only possible for at most two values of $k$, namely $0$ and $\frac{\varphi(m)}{2}$. As $\pm 1$ are always solutions and distinct, those are exactly the two solutions.

The other direction is most likely more difficult, I don't have a proof yet, but you can of course deduce this from Euler's theorem:

If there is no primitive root modulo $m$, then by Euler's theorem $m$ can not be of the form $$2, 4, p^k, 2p^k$$ where $p$ is an odd prime and $k$ is a positive integer. Check carefully, that this implies that $m$ is either a power of two or can be written as product of two coprime numbers which are both at least $3$. In both cases we find more than two solutions:

• $m=2^k$. Define $x=2^{k-1}-1$. Then $x\not\equiv \pm 1\pmod{2^k}$, but $$x^2=(2^{k-1}-1)^2=2^k-2\cdot 2^{k-1} +1 \equiv 1\pmod{2^k}$$
• $m=ab, (a,b)=1, a,b\geq 3$: Then $x^2\equiv 1\pmod a$ and $x^2\equiv 1\pmod b$ have both at least two distinct solutions ($\pm 1$) and the Chinese remainder theorem tells that $x^2\equiv 1\pmod{ab}$ has at least four solutions.
• How come the only other case break down is m=ab,(a,b)=1,a,b≥3 – DJ_ Nov 29 '13 at 21:39

Whenever you see an "if and only if" statement, you need to interpret it in two ways:

1. If $m$ has a primitive root, then the only solutions of the congruence $x^2 \equiv 1 \pmod m$ are $x \equiv \pm 1 \pmod m$. We call this the $\Rightarrow$ direction.
2. If the only solutions of the congruence $x^2 \equiv 1 \pmod m$ are $x \equiv \pm 1 \pmod m$, then the integer $m$ has a primitive root. We call this the $\Leftarrow$ direction.

You need to prove that both 1. and 2. holds.

Whenever you're tackling a problem, you need to master all details associated with the problem. Otherwise any attempt at solving it will lead you nowhere, and the work you attempt will not give you any information. And attempts at solving the problem will always give you some kind of information! I always consider solving problems as further exploring the topic.

It seems that you are not quite familiar with the concept of primitive roots. In a nutshell, we are considering the congruence of any integer $a$ to some power modulo $m$: $a^b \equiv c \pmod m$. If it happens $a$ satisfies the condition $$a^{\phi(m)}\equiv 1 \pmod m,$$ then $a$ is a 'primitive root' modulo $m$. Therefore,

1. This point says there EXISTS some $a$ such that $a^{\phi(m)}\equiv 1 \pmod m$. Now you need to use this to show that the only solutions of $x^2 \equiv 1 \pmod m$ are $x \equiv \pm 1 \pmod m$.
2. This point says that the only solutions of $x^2 \equiv 1 \pmod m$ are $x \equiv \pm 1 \pmod m$. Now you need to use this to show that $m$ has a primitive root.

Hints: For 1.: Let $r$ be a primitive root modulo $m$. Recall first that $\{r, r^2, \ldots, r^{\phi(m)}\}$ is a reduced residue system modulo $m$. This means that all integers $a$ where $(a,m)=1$ are represented, and only these integers can possible satisfy $x^2 \equiv 1 \pmod m$, right? Because if $(x,m)=d > 1$, then $d \mid 1$ in order for the congruence to have any solutions, which is a contradiction. Hence $(x,m)=1$. But then we must have that $x \equiv r^t$ for some $t \in \{1,2,\ldots,\phi(m)\}$ (make sure you understand this step). Hence $$r^{2t}\equiv 1 \pmod m,$$ and therefore $\phi(m) \mid 2t$, so that $\phi(m) k = 2t$ or $t = \phi(m)k/2$. Therefore $$x \equiv r^t \equiv r^{\phi(m)k/2} = \left( r^{\phi(m)/2} \right)^k \equiv (-1)^k \equiv \pm 1 \pmod m.$$

For 2.: Suppose that the only solutions are $x \equiv \pm 1 \pmod m$ and that there is no primitive root modulo $m$. By the primitive root theorem, $m$ is not $2,4,p^a, 2p^a$. We can therefore write $m$ in the form $2^b M$ where $b \geq 3$ and $M$ an odd integer. Since $(2^b,M)=1$ we can split this up and use the Chinese Remainder Theorem. It can be shown that there are at least three solutions of $s^2 \equiv 1 \pmod{2^b}$. Call these $s_i$, $i=1,2,3$. Certainly there is one solution of $x^2 \equiv 1 \pmod M$. By the Chinese Remainder Theorem, the system $x \equiv s_i \pmod{2^b}$ ($i=1,2,3$), $x^2 \equiv 1 \pmod M$ has a unique solution. Since these are distinct modulo $m$, there must be one that is not $\pm 1 \pmod m$. Hence our assumption was false and $m$ must have a primitive root.

• Yes that makes sense to me but I still don't know how to get anywhere knowing how to break the question apart – DJ_ Nov 28 '13 at 20:09
• Is N the same as M here? – DJ_ Nov 28 '13 at 22:56
• It is not true, that $m$ is necessarily of the form $2^bM$ for $b\geq 3$ and $M$ odd if $\mathbb Z_m$ is not cyclic. Take $12$ or $30$. – Tomas Nov 28 '13 at 23:41
• What does cyclic mean? – DJ_ Nov 29 '13 at 21:27