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$ – Gerry Myerson Mar 14 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$ – Bill Dubuque Mar 14 at 3:25
  • $\begingroup$ Thank you all! I understand it. $\endgroup$ – kelvin hong 方 Mar 14 at 3:49
  • 2
    $\begingroup$ Good! Let me encourage you to post an answer, kelvin. $\endgroup$ – 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$.


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.