I came across a really interesting blog post on generating a permutation based on quadratic residues of the form $x^2$ $mod$ $p$ (where $p$ is prime). It can be accessed here for further context: https://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/
The premise is that, given a prime number $p$, you can generate a permutation of all integers in $\{1 ...p\}$ by using the equation $x^2$ $mod$ $p$ for $x$ $\lt$ $p/2$, and the equation $p$ $-$ $x^2$ $mod$ $p$ for the remaining $x \lt p$
I've tested his logic for a use case very similar to the one laid out in the post and it seems to hold up, however, I've been unable to find specific literature/proofs regarding the statements he's made. I've done quite a bit of searching on quadratic residues of primes and the specific congruences he mentions, and have found a lot of information out there. But, nothing that I'm able to derive his exact assumptions from easily.
So here I am asking for direction! It may be a simple case of not knowing the correct search terms here. Specifically, I am looking for proofs related to the following statements:
For a prime number $p$, $x^2$ $mod$ $p$ is unique when $2x$ $<$ $p$.
The expression $p$ $-$ $x^2$ $mod$ $p$ fills all remaining integers in $\{1 ...p\}$ provided $p$ $\equiv 3$ $mod$ $4$.
Both of these are standard results in number theory. The first comes from the implication $a^2\equiv b^2\pmod p$ implies $a\equiv\pm b\pmod p$. One proves this by noting that $a^2\equiv b^2\pmod p$ implies $p\mid(a-b)(a+b)$ which implies $p\mid(a-b)$ or $p\mid(a+b)$ (Euclid's lemma).
The second arises from the fact that $-1$ is a quadratic non-residue modulo $p$ when $p\equiv 3\pmod 4$. There are several ways of proving this; one is to apply Euler's criterion that $\left(\frac ap\right)\equiv a^{(p-1)/2}\pmod p$ ($\left(\frac ap\right)$ is a Legendre symbol).