3
$\begingroup$

I want to show that in $\Bbb F_p$ where $p$ is an odd prime, that half the non-zero elements are squares.

Now I know that all fields $\Bbb F_p$ where $p$ is prime are isomorphic to $\Bbb Z / \Bbb p Z$, and I have tested a few examples and I can see that it holds for them, so I don't doubt it is true, but I am unsure how to prove it.

Can I please have a hint, but not a full solution. If you give me a full solution I won't get to have the eureka moment and I won't remember it!

$\endgroup$
1
  • 3
    $\begingroup$ @GeorgeV.Williams I was left in a weird position when I needed only hints and not full solutions, if I looked in other questions I was likely to ruin it :\ $\endgroup$
    – beginner
    Jan 2, 2015 at 3:59

2 Answers 2

Reset to default
5
$\begingroup$

Hint

Method 1:

For an upper bound, note that $x^2=(-x)^2$, so how many squares can there be at most?

For a lower bound, suppose that $a^2\equiv b^2\mod{p}$. Hence $(a-b)(a+b)\equiv0\mod{p}$. What can you conclude about the relationship of $a$ to $b$?

Method 2:

Recall that $\mathbb{Z}/p\mathbb{Z}$ is cyclic, so has some generator $g$. Consider an arbitrary element $g^n$. For which $n$ is $g^n$ a square?

$\endgroup$
4
$\begingroup$

Hint: Consider the homomorphism $\phi : \mathbb F_p^\times \to \mathbb F_p^\times$ defined by $\phi(x) = x^2$, and note $\phi$ is surjective onto the set of squares. What is $\ker \phi$ (note $p$ is odd)?

$\endgroup$
6
  • $\begingroup$ Trivial question, but is $\operatorname{ker} \phi$ the elements that go to $0$ or $1$ here? $\endgroup$
    – beginner
    Jan 2, 2015 at 3:57
  • 1
    $\begingroup$ @beginner, $\mathbb F_p^\times$ refers to the multiplicative subgroup of $\mathbb F_p$. It does not contain $0$, and the identity is $1$ (since $1x = x$). The kernel refers to the identity, and so we are talking about elements which go to $1$. $\endgroup$
    – George V. Williams
    Jan 2, 2015 at 4:00
  • $\begingroup$ @George sorry that makes perfect sense, thank you. $\endgroup$
    – beginner
    Jan 2, 2015 at 4:04
  • $\begingroup$ $\operatorname{Ker}\phi = \{1,p-1\}$? $\endgroup$
    – beginner
    Jan 2, 2015 at 4:58
  • 1
    $\begingroup$ @beginner, yes. What do you conclude? (You might know a relevant result as "the first isomorphism theorem.") $\endgroup$
    – George V. Williams
    Jan 2, 2015 at 5:03

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