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

Question

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

Answer 1

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.

Answer 2

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.