# How to prove $r^{\phi(m)/2} \equiv -1$ (mod $m$) if $r^{\phi(m)} \equiv 1$ (mod $m$)?

If we have a primitive root $r$ for $m > 2$ (whatever composite or prime), that $r^{\phi(m)} \equiv 1$ (mod $m$), how can we show that \begin{align} r^{\phi(m)/2} \equiv -1\text{ }(\text{mod } m)? \end{align}

Thanks a lot.

If $r$ is a primitive root modulo $m$ then $1,r,r^2,\dots, r^{\phi(m)-1}$ are distinct modulo $m$.
For example: This means that $\mathbb Z_m^{\times}$ is cyclic. In particular, that means there is only two square roots of $1$ modulo $m$, $1$ and $-1$.
Or: This means that $r^k\equiv -1\pmod m$ for some $k$. But then $r^{\phi(m)-k}=-1$ too, which is impossible unless $k=0$ or $k=\phi(m)/2$. But $k=0$ means $1\equiv -1\pmod m$, so $m\mid 2$.
We have $$r^{\phi(m)} \equiv 1 \pmod m.$$ Taking square roots gives $$r^{\phi(m)/2} \equiv \pm 1 \pmod m.$$ If $r^{\phi(m) / 2} \equiv 1 \pmod m$, then $r$ is not a primitive root, which is a contradiction. thus $r^{\phi(m) / 2} \equiv -1 \pmod m$.
• There are multple square roots of $1$ modulo $m$ in general... – Thomas Andrews Mar 29 '17 at 1:35
• (Er, by mutliple, I meant more than two. For example $4^2=1\pmod{15}$.) But there is no primitive root modulo $15$. You'll need a more careful argument to show that, though. – Thomas Andrews Mar 29 '17 at 1:43