Exercise 3.1.13 (If $r$ is a quadratic residue modulo $m 2$, then $r^{\phi(m)/2} \equiv 1 \pmod m$)

Question

Prove that if $r$ is a quadratic residue modulo $m >2$, then $r^{\phi(m)/2} \equiv 1 \pmod m$.

Richard Ganaye · Accepted Answer

begin{proof} If $r$ is a quadratic residue modulo $m$,  by Definition 3.1, $r \wedge m = 1$, and $r \equiv a^2 \pmod m$ for some integer $a$. Here $m>2$, thus $\phi(m)$ is even. Then, by Euler's Theorem,
\begin{align*}
r^{\frac{\phi(m)}{2} } &\equiv a^{\phi(m)}\
&\equiv 1 \pmod m.
\end{align*}
\end{proof}

Exercise 3.1.13 (If $r$ is a quadratic residue modulo $m >2$, then $r^{\phi(m)/2} \equiv 1 \pmod m$)

Answers

Comments

Exercise 3.1.13 (If $r$ is a quadratic residue modulo $m >2$, then $r^{\phi(m)/2} \equiv 1 \pmod m$)

Answers

Comments

Add answer