1
$\begingroup$

Euler Theorem: $a^{\varphi(m)}\equiv 1 \pmod m ,$ For $(a,m)=1.$

Using the above show that for $m=p^\alpha$ where $p$ is prime and $m\geq3$ $$a^{\frac{\varphi(m)}{2}}\equiv \pm1 \pmod m,~where~(a,m)=1$$ I know $\varphi(m)$ is even. So $\frac{\varphi(m)}{2}$ is some integer.

$\endgroup$
1
$\begingroup$

What do you get if you square $a^{\phi(m)/2}$?

$\endgroup$
  • $\begingroup$ The square is $a^{\phi(m)}$ $\endgroup$ – user194772 Dec 6 '14 at 16:08
  • $\begingroup$ Right. Can you simplify that? Then, what are its square roots? $\endgroup$ – Empy2 Dec 6 '14 at 16:09
  • $\begingroup$ What do you mean "its square root"? $\endgroup$ – user194772 Dec 6 '14 at 16:12
  • $\begingroup$ First, what is $a^{\phi(m)}$ equal to? $\endgroup$ – Empy2 Dec 6 '14 at 16:13
  • $\begingroup$ I think you are saying that since $$ a^{\varphi(m)}\equiv1(mod~m)$$ then the square root of $ a^{\varphi(m)}$ is $\equiv\pm1(mod~m)$? $\endgroup$ – user194772 Dec 6 '14 at 16:21

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.