Roots of quadratic in $Z_n^2$ I am looking at a probabilistic proof which involves some number theory, an area I'm very weak in. This is the part I have questions about (from The Probabilistic Method by Alon and Spencer):

Let $n$ be prime. On $[0, n-1] \times [0, n-1]$, consider the $n$ points $(x, x^2),$ where $x^2$ is reduced mod $n$ (more formally, $(x, y)$ where $y \equiv x^2 \mod n$ and $0 \le y < n$). If some three points of this set were collinear, they would lie on a line $y = mx + b$, and $m$ would be a rational number with denominator less than $n$. But then in $Z_n^2$, the parabola $y = x^2$ would intersect the line $y=mx+b$ at three points, so that the quadratic $x^2-mx-b$ would have three distinct roots, an impossibility.

So basically the point is to show that none of the $n$ points described at the beginning of the quote are collinear. I will walk through what I understand and don't understand at each point:

Let $n$ be prime. On $[0, n-1] \times [0, n-1]$, consider the $n$ points $(x, x^2),$ where $x^2$ is reduced mod $n$ (more formally, $(x, y)$ where $y \equiv x^2 \mod n$ and $0 \le y < n$).

The first half is very clear to me, but the part stating with "more formally" confuses me because it doesn't seem equivalent. It seems to me that points $(x, y)$ where $y \equiv x^2 \mod n$ and $0 \le y < n$ will include points that fall outside $[0, n-1] \times [0, n-1]$ since although we are limiting $0 \le y < n$, we aren't limiting $x$ to $0 \le x < n$. Maybe this is just assumed though and I'm overthinking it.

If some three points of this set were collinear, they would lie on a line $y = mx + b$, and $m$ would be a rational number with denominator less than $n$. 

This makes sense. The denominator will be less than $n$ since all the points are lattice points in $[0, n-1] \times [0, n-1]$. The only strange case to me would be if $m =0$, but I guess the rest of the proof still works even in this case. What I don't understand is why the fact that the denominator is less than $n$ is important to any other step in the proof.

But then in $Z_n^2$, the parabola $y = x^2$ would intersect the line $y=mx+b$ at three points, so that the quadratic $x^2-mx-b$ would have three distinct roots, an impossibility.

This is where I'm really confused. To my understanding, $Z_n$ is the set $\{0, 1, \ldots, n-1 \}$ where addition is mod $n$. Is $Z_n^2$ just the squares of all these elements, again with addition mod $n$? But this doesn't seem quite right to me. For example, take $Z_4$ which has the set $\{0, 1, 2, 3\}$. Performing mod $4$ on the squares of these elements produces $\{ 0, 1 \}$. But this is no longer closed because, for example, $(1 + 1) \mod 4 = 2$ and $2 \notin \{0, 1\}$.
I'm also confused about why the quadratic $x^2-mx-b$ having three roots is an impossibility. Sure it can't have three roots if we are looking at an ordinary parabola in $\mathbb{R}^2$, but to my understanding this parabola is really like plugging $x$ into $x^2-mx-b$ and then taking mod $n$ of the result. Since we are taking mod $n$ at the end, it seems like we could have $3$ or more roots.
 A: Nicely written post. To your first confusion, book is saying that, if as you have identified, x^2 is greater than or equal to n, then reduce it (ie subtract the correct multiple of n) to y so that (x,y) is in [0,n-1]^2 and (x,y) is congruent to (x,x^2) mod n. 
Now to deal with the slope, say it is p/q. As q, is less than n, it is invertible mod n. (Remember that n is prime!). So there is some number m congruent to p(q^-1) mod n. 
So the slope makes sense as a number mod n and not just as a rational number. Most important, 1/n does not make sense mod n. 
Again, as n is prime, the quadratic equation can have at most 2 roots. And in general, a polynomial of degree d can have at most d roots over a field. More simply, the main feature mod a prime we care about is that no to numbers can multiply to zero unless one of them is divisible by p. 
In your example, it breaks down mod 4 as 2*2=0 mod 4. Mod 2^n a quadratic can in fact have a power of two many roots. eg x^2  mod 2^n has roughly 2^(n/2) roots. 
