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$?
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.