This is trivial in arguments of quadratic residues, but I couldn't solve it using primitive root. The problem seeks to use primitive root to be proved.
Problem: Let $m>2$ be an integer having a primitive root, and let $(a,m)=1$. Prove that $a^{\phi(m)/2}\equiv 1\pmod m$ implies $a$ is a quadratic residue modulo $m$.
My approach is, I know there are $\phi(\phi(m))$ primitive roots in the reduced residue set modulo $m$: $S=\{a_1,a_2,\cdots,a_{\phi(m)}\}$. Then I square the set, to get $T=\{b_1,b_2,\cdots,b_{\phi(m)/2}\}$ where for each $b_i$ there is $a\in S$ such that $a^2\equiv b_i\pmod m$. But I cannot keep writing, I don't know how to continue.
Any suggestion?
Best Answer
Let $g$ be an primitive root mod $m$, then the set $S=\{g,g^2,\cdots, g^{\phi(m)}\}$ forms a reduced residue set mod $m$.
Since $(a,m)=1$, we can express $a$ as a power of $g$, let $a\equiv g^k\pmod m$. So by assumption we have $$g^{k\phi(m)/2}\equiv 1\pmod m.$$ But $g$ is primitive, we see $\phi(m)|k\phi(m)/2$ which is $2|k$, this shows that $a$ is an even power of $g$, which is equivalent to say that $a$ is a quadratic residue modulo $m$.