4
$\begingroup$

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

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

2 Answers 2

3
$\begingroup$

Let $a=b^2$$$a^{\frac{p-1}{2}} = ({b^2})^{\frac{p-1}{2}} = b^{p-1}\equiv1\pmod p$$

$\endgroup$
11
  • $\begingroup$ Why should $a$ be a square modulo $p$? $\endgroup$
    – egreg
    Nov 25, 2013 at 17:29
  • $\begingroup$ Because that's what is given. $\endgroup$
    – Stefan
    Nov 25, 2013 at 17:29
  • $\begingroup$ This is one direction, how I prove the other one? Thank you! $\endgroup$
    – CS1
    Nov 25, 2013 at 17:30
  • $\begingroup$ @Stefan Oh, I see! $\endgroup$
    – egreg
    Nov 25, 2013 at 17:30
  • $\begingroup$ At the second direction we have to use that this is a cyclic group... $\endgroup$
    – CS1
    Nov 25, 2013 at 17:34
2
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Unfortunately I can't use L. theorem... $\endgroup$
    – CS1
    Nov 25, 2013 at 19:09
  • 1
    $\begingroup$ @YoavFridman I have added something. $\endgroup$
    – Pedro
    Nov 25, 2013 at 19:17
  • 1
    $\begingroup$ You have that $a^{(p-1)/2}=1$. Substitute. $\endgroup$
    – Pedro
    Nov 25, 2013 at 19:20
  • 1
    $\begingroup$ @YoavFridman Did you read what I have added? Read it carefully. $\endgroup$
    – Pedro
    Nov 25, 2013 at 19:22
  • 1
    $\begingroup$ @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. $\endgroup$
    – Pedro
    Nov 25, 2013 at 19:32

You must log in to answer this question.

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