Prove the set $\{0^2 \bmod p, 1^2 \bmod p, \dotsc, ((p-1)/2)^2 \bmod p\}$ consists of $(p+1)/2$ distinct elements.

Question

The Question

I am currently working on the following problem, which is part of a multistep question.

Prove: The set $\{0^2 \bmod p, 1^2 \bmod p, \dotsc, ((p-1)/2)^2 \bmod p\}$ consists of $(p+1)/2$ distinct elements in $\mathbb{Z}_p$ without repetition.

---

Pieces of a Solution?

Here is what I have so far that I believe is useful:

1. In the previous part, I proved that if $p$ is an odd prime (i.e., $p \neq 2$) and $a,b$ are any two integers with $0 \leq a < b \leq (p-1)/2$, then $a^2 \not\equiv b^2 \pmod{p}$. I believe this helps prove that all the elements in the set mentioned in the question posed are distinct.
2. After looking through a good amount of literature on the matter, it seems helpful to note that, for $x=0^2 \pmod p, 1^2 \pmod p, \dots, ((p-1))/2\pmod p$, we have $x^2\equiv (p-x)^2\pmod p$ since $(p-x)^2=p^2-2px+x^2\equiv x^2 \pmod p$.
3. One other fact that I noticed while scanning the various literature out there is that $x^2\equiv (-x)^2\pmod p$, but I just can't see how that helps me in this problem.

---

My Questions

I have been working on this single problem for two entire days now. Even after seeking help from instructor, I just don't get it. I have articulated my questions to the best of my abilities below.

1. From what I have gathered, this is a somewhat typical problem concerning quadratic residues. Despite this, my instructor never taught that topic, and it is never mentioned within the problem. It seems limiting to not have that definition at hand. Am I able to do this proof without mentioning the words "quadratic residues?"

2. Why does this set end at $((p-1)/2)^2$? Why there? Why not end at $p$?

3. What exactly is $\mathbb{Z}_p$?

4. Most of the proofs I have seen regarding this question have the set starting with $1^2$, not $0^2$. Additionally, I have noticed that these same proofs end up with the result of there being exactly $(p-1)/2$ quadratic residues and exactly $(p-1)/2$ nonresidues. I assume this particular set I am given would count the number of quadratic residues if I understand the proofs I've seen correctly, so where does "$(p+1)/2$" elements come from. Is this a typo?

5. For this problem, does showing that all elements are distinct also show that there is no repetition? I thought sets didn't have repetition to begin with?

---

Sorry guys, I know this is a long one but I could really use the help. Thank you as always!

Answer 1

The answers to each of your 5 questions:

1. Yes.
2. Obviously, $1^2 = (-1)^2 \equiv (p-1)^2 \mod p$, so if $p-1$ were included in the set, it would have repetition.
3. The field of integers modulo $p$. (Read https://en.wikipedia.org/wiki/Finite_field )
4. Count carefully, there are $p+1\over2$ elements listed (start at $0$, end at $p-1\over2$)
5. Yes, you have to show that there is no repetition. To say, $\{1,2,3\}=\{1,1,2,3,3,3\}$, and both set have 3 elements.

---

Proof for the question: (what you already had is indeed useful)

Assume that the set have repetition.

Let $a$ and $b$ be two integers in $\{0,1,2,...,\frac{p-1}2\}$ such that $a\neq b$ and $a^2 \equiv b^2 \mod p$. Therefore, $$a^2 \equiv b^2 \mod p$$ $$a^2 - b^2\equiv 0 \mod p$$ $$p \vert a^2 - b^2$$ $$p \vert (a+b)(a-b)$$ Therefore $p \vert a+b$ or $p \vert a-b$.

$p \vert a-b$ is impossible because $a\neq b$ and $a, b \in\{0,1,2,...,\frac{p-1}2\}$.

$p \vert a+b$ is impossible because $0 \leq a, b \leq \frac{p-1}2$, thus $0 \leq a+b \leq p-1$, also $a\neq b$ so $a+b\geq 1$.

Therfore the assumption is incorrect $\Rightarrow$ Q.E.D.