# How do I prove that $a\in (\mathbb{Z}_{p}^{*})^2 \Leftrightarrow a^{\frac{p-1}{2}}\equiv 1 \pmod p$

$p$ is prime number $>2$ and $a$ is a square. $\mathbb{Z}_{p}^{*}$ is a cyclic group.

I need to show that $$a\in (\mathbb{Z}_{p}^{*})^2 \iff a^{\frac{p-1}{2}}\equiv 1 \pmod p$$

Any ideas how?

I need to prove two directions...

Thank you!

Q: Have you any idea how do I prove this direction? $\Longleftarrow$ (I understand the other direction, but please help me with this one...)

• $a^{\frac{p-1}{2}} = ?$ Nov 25, 2013 at 17:23
• Have you seen en.wikipedia.org/wiki/Fermat%27s_little_theorem ? Nov 25, 2013 at 17:26
• Because they are both equivalent to $a$ not being a multiple of $p$? Nov 25, 2013 at 17:26
• @PrahladVaidyanathan - I try to use this theorem, but I didn't understand how it's help me...
– CS1
Nov 25, 2013 at 17:28
• @AshGX - So, how it's prove it? I need to get 2 directions...
– CS1
Nov 25, 2013 at 17:29

Let $a=b^2$$a^{\frac{p-1}{2}} = ({b^2})^{\frac{p-1}{2}} = b^{p-1}\equiv1\pmod p$$ • Why should$a$be a square modulo$p$? Nov 25, 2013 at 17:29 • Because that's what is given. Nov 25, 2013 at 17:29 • This is one direction, how I prove the other one? Thank you! – CS1 Nov 25, 2013 at 17:30 • @Stefan Oh, I see! Nov 25, 2013 at 17:30 • At the second direction we have to use that this is a cyclic group... – CS1 Nov 25, 2013 at 17:34 By little Fermat, we know that for any$a\neq 0$in$\Bbb Z_p^\times$we have$a^{p-1}=1$. This means that$a^{\frac{p-1}2}=\pm 1$. It is a theorem that in$\Bbb Z_p^{\times}$, exactly half of the elements are squares (namely, those that correspond to$1^2,2^2,\ldots,\left(\frac{p-1}2\right)^2$) and half are non-squares. But by Lagrange's theorem,$a^{\frac{p-1}2}=1$has at most$\dfrac{p-1}2$solutions and by the previous claim at least$\dfrac{p-1}2$solutions. Thus, it has exactly$\dfrac{p-1}2$solutions, the squares$\mod p$. Thus if$a=b^2$the equations holds, and if$a$is not a square the equation doesn't. ADD Using$\Bbb Z_p^\times$is cyclic. Let$g$be a primitive root modulo$p$. We can write$a=g^k$for some$k$. By$g^{k(p-1)/2}=1$, it follows that${\rm ord}(g)=p-1\mid (p-1)k/2$. This gives$k/2$is an integer, so$k=2m$, and$a=g^{2m}=g'^2$where$g'=g^m$. • Unfortunately I can't use L. theorem... – CS1 Nov 25, 2013 at 19:09 • @YoavFridman I have added something. – Pedro Nov 25, 2013 at 19:17 • You have that$a^{(p-1)/2}=1$. Substitute. – Pedro Nov 25, 2013 at 19:20 • @YoavFridman Did you read what I have added? Read it carefully. – Pedro Nov 25, 2013 at 19:22 • @YoavFridman Think about it a little more. What does it mean that$p-1\mid (p-1)k/2$? Write it out, and conclude that$k/2\$ must be an integer.