Let $n\in\mathbb{N}$ be such that $\mathbb{Z}_n^*$ has a primitive root. Let $a$ be such a primitive root. Is the following true? $$a^{\frac{\phi(n)}{2}}\equiv-1\mod{n}$$ where $\phi$ is Euler's function.

It all comes down to whether $x^2\equiv 1\mod{n} \Leftrightarrow x\equiv\pm 1\mod{n}$ is a true statement, which I have failed to prove.


If $\mathbb Z_n^*$ has a primitive root, then $a,a^2,a^3,...,a^{\phi(n)}$ are the elements of $\mathbb Z_n^*$. So, there is a unique number $m$ with $1\le m< \phi(n)$ and $a^m=-1$

This implies $a^{2m}=1$. Therefore we have $\phi(n)|2m$ , but $2m<2\phi(n)$.

It follows $2m=\phi(n)$ and therefore $m=\frac{\phi(n)}{2}$ completing the proof.

Note that for $n=2$, $\mathbb Z_n^*$ has only $1$ element , so we must assume $n>2$, otherwise $\frac{\phi(n)}{2}$ is not an integer. In this case, $-1$ and $1$ are different elements and the proof works.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.