4 ms·
So {((p-1)/2)!}^2 == -1 (mod p), which means that {((p-1)/2)!} is a solution to x^2 +1 = 0 mod p, and therefore there is always a solution (for p = 1 mod 4). I
by AnimalMuppet 7y ago
So {((p-1)/2)!}^2 == -1 (mod p), which means that {((p-1)/2)!} is a solution to x^2 +1 = 0 mod p, and therefore there is always a solution (for p = 1 mod 4). I see.
And this breaks down for p=4n+3, because then (p-1)/2 is odd, and we can't pair the terms that way. But... maybe I'm being dense, but I don't see a way to extend this to prove the other side: that if p = 3 mod 4, there are no solutions. (We've proven that this way doesn't work to construct a solution, but that's not the same as proving that no solution exists.)
Thank you very much for the help this far. This is one of the absolutely cool things about HN - some random guy asks a question, just because it interests him, and a Cambridge PhD gives him time, for free, to help him learn a bit more.
- ColinWright 7y ago> And this breaks down for p=4n+3, because then (p-1)/2 is odd, and we can't pair the terms that way. Right. > ... I don't see a way to extend this to prove the other side: that if p = 3 mod 4, there are no solutions. (We've proven that this way doesn't work to construct a solution, but that's not the same as proving that no solution exists.) Correct. So you are considering x^2+1=0 (mod p) when p=3 (mod 4), and you want to show that no solution exists. If x^2 = -1 (mod p) then x^4 = 1 (mod p). But powers of an element in a group form a subgroup, so the set {1, x, x^2, x^3} is a subgroup of Z_p. By Lagrange's Theorem the size of a subgroup must divide the size of the group, and so we have that 4 must divide p-1. But if p=3 (mod 4) then that's not true, and so x^2 cannot be -1 (mod p). Does that help? I've omitted some details, but it's largely right. > Thank you very much for the help this far. You're welcome, it's been an interesting diversion from some mundane work, and has served as a useful reminder of some fun stuff.
- AnimalMuppet 7y ago> Does that help? Yes. You've been able to pitch your explanations at a level that my only-a-BS-in-math brain could grasp. Thank you very much. It's been a pleasure interacting with you.