The other side
Quadratic residues (numbers that are a perfect square\(\mod p\)) turned out to be the key to showing that we had found all solutions.
Each equation we worked with can be made into a statement about perfect squares. For example, if \(y \equiv 3r^2\mod p \) then \( 12 y \) is a perfect square\(\mod p\) because \begin{align*} 12 y & \equiv 36r^2\mod p \\ & \equiv (6r)^2\mod p \end{align*}
Similarly, if \( y \equiv 3r^2 + r \) then \( 12 y \) is 1 less than a perfect square:
\begin{align*} 12 y & \equiv 36(r^2 + \frac{r}{3}) \mod p \\ & \equiv 36(r^2 + \frac{r}{3} + \frac{1}{36} - \frac{1}{36} )\mod p \\ & \equiv 36\left(r + \frac{1}{6}\right)^2 - 1\mod p \\ & \equiv (6r + 1)^2 - 1\mod p \end{align*}Key fact (Weil): If \( p \) is a prime larger than 40,000,000, then there will always be a consecutive string of 8 or more non-squares\(\mod p\).