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?

  • 2
    $\begingroup$ 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$. $\endgroup$ Commented Mar 14, 2019 at 2:20
  • 1
    $\begingroup$ 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\ \ $ $\endgroup$ Commented Mar 14, 2019 at 3:25
  • $\begingroup$ Thank you all! I understand it. $\endgroup$ Commented Mar 14, 2019 at 3:49
  • 2
    $\begingroup$ Good! Let me encourage you to post an answer, kelvin. $\endgroup$ Commented Mar 15, 2019 at 1:41

1 Answer 1


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .