0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is exactly what I was looking for, thank you very much. $\endgroup$ – OmegaTauPhi Jun 8 '18 at 6:05
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I was unaware of this truth, but my primes are indeed of this form, which is extremely helpful, thank you. $\endgroup$ – OmegaTauPhi Jun 8 '18 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.