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