# Use primitive root to prove if $a^{\phi(m)/2}\equiv 1\pmod m$ then $a$ is a quadratic residue modulo $m$.

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?

• Let $g$ be a primitive root. Express $a$ as a power of $g$. Consider the consequences of $a^{\phi(m)/2}\equiv1\bmod m$, and why it forces $a$ to be an even power of $g$. – Gerry Myerson Mar 14 at 2:20
• Additively it boils down to $\bmod 2n\!:\ nk\equiv 0\,\iff 2\mid k,\,$ by $\ 2n\mid nk\iff 2\mid k.\,$ This arithmetic occurs in the exponents of the generator $g$ when you follow Gerry's hint, where $\,n = \phi(m)/2,\,$ and $\,a = g^k\ \$ – Bill Dubuque Mar 14 at 3:25
• Thank you all! I understand it. – kelvin hong 方 Mar 14 at 3:49
• Good! Let me encourage you to post an answer, kelvin. – Gerry Myerson Mar 15 at 1:41

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