Question: let $p$ be a Pythagorean prime, and $n$ some integer. Does there necessarily exist a solution to the concurrency $n^2 \equiv (p-1) \mod p$? I've been studying this problem for the last 6 hours, and to no avail. 

The first thing I did was make a table

$$1^2 + 2^2 = 5 \to n^2 \equiv 4 \mod 5 \Rightarrow n = 2,3$$
$$2^2 + 3^2 = 13 \to n^2 \equiv 12 \mod 13 \Rightarrow n = 5,8$$
$$2^2 + 5^2 = 29 \to n^2 \equiv 28 \mod 29 \Rightarrow n = 12,17$$
$$4^2 + 5^2 = 41 \to n^2 \equiv 40 \mod 41 \Rightarrow n = 9,32$$
$$5^2 + 6^2 = 61 \to n^2 \equiv 60 \mod 61 \Rightarrow n = 11,50$$
$$7^2 + 8^2 = 113 \to n^2 \equiv 112 \mod 113 \Rightarrow n = 15,98$$
$$9^2 + 10^2 = 181 \to n^2 \equiv 180 \mod 181 \Rightarrow n = 19,162$$

I also had noticed for non-Pythagorean primes, such as 3,7, and 23, there were no solutions, so that was note-worthy. 

I was hoping to see a good pattern from the table, but none jumped out at me. From this point, I was trying to spot any property I could. I recognize that Pythagorean primes are of the form $4k +1$, so I tried substituting to see what I could demonstrate with algebra but I don't think it was anything significant. Is anyone aware if there will always exist a solution? If so, is there a general formula for $n$?

Answer: 
Another way of formulating this is that $-1$ is a quadratic residue modulo $p$, which is well-known for primes $\equiv 1 \bmod 4$ - so yes it is true. There are various ways of proving this. For example you can use Wilson's theorem that $$(p-1)!\equiv -1 \bmod p$$

Now consider $q=\frac {p-1}2$

$$(p-1)!=1\cdot 2\cdot 3\dots \cdot q\cdot (q+1)\dots \cdot (p-1) \equiv1\cdot 2 \dots \cdot q\cdot (-q) \dots (-1)$$where the last half of the terms are found by deducting $p$ from the original elements. This is then $$\equiv q!\cdot (-1)^q \cdot q!=(q!)^2$$ because $q$ is even. And the $n$ you are looking for is $\equiv \pm q!$

---

To prove Wilson's theorem you can pair each element with its multiplicative inverse modulo $p$ leaving only $1$ and $-1$ unpaired.
Is a "pythagorean prime" a prime with $p\equiv1$ (mod $4$)? It's
a well-known theorem of number theory that the congruence $x^2\equiv-1\pmod p$ has a solution for an odd prime $p$ iff $p\equiv1\pmod 4$.