2 ms·
> 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 t
by 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.