3

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!

beginner
  • 804
  • 3
    @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 :\ – beginner Jan 02 '15 at 03:59

2 Answers2

5

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?

Peter Woolfitt
  • 21,114
4

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)?

George V. Williams
  • 5,213
  • Trivial question, but is $\operatorname{ker} \phi$ the elements that go to $0$ or $1$ here? – beginner Jan 02 '15 at 03:57
  • 1
    @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$. – George V. Williams Jan 02 '15 at 04:00
  • @George sorry that makes perfect sense, thank you. – beginner Jan 02 '15 at 04:04
  • $\operatorname{Ker}\phi = {1,p-1}$? – beginner Jan 02 '15 at 04:58
  • 1
    @beginner, yes. What do you conclude? (You might know a relevant result as "the first isomorphism theorem.") – George V. Williams Jan 02 '15 at 05:03
  • @GeorgeV.Williams This seems like the fun solution, but the first isomorphism theorem is 200 pages from here, so I will learn it now and get back to you tomorrow or the next day. Just know I am working on it and I appreciate your help :) – beginner Jan 02 '15 at 08:55