3 ms·
Well, since you say this isn't a homework problem ... Wilson's theorem says that for (p-1)! == -1 (p) iff p is prime. Easily proved by pairing each non-unit w
by ColinWright 7y ago
Well, since you say this isn't a homework problem ...
Wilson's theorem says that for (p-1)! == -1 (p) iff p is prime. Easily proved by pairing each non-unit with its multiplicative inverse, noting that a^{-1} != a (mod p), and so 1x2x3x4x...x(p-2)x(p-1) can have everything paired off and leave just the (p-1) term, hence if p is prime, (p-1)! == -1 (mod p).
I suggest you take some time to work through that and convince yourself.
Now consider p an odd prime with p==1 (mod 4). Consider (p-1)!. Pair every a with (p-a) and hence note that 1x2x3x4x...x(p-1)/2 equals (p+1)/2 x ...x(p-1) up to a multiple of -1. But since p==1 (mod 4), (p-1)/2 is even, and so we have 1x2x3x4x...x(p-1)/2 == (p+1)/2 x ...x(p-1) (mod p).
But that's (p-1)!, which by Wilson's theorem is -1, and so {((p-1)/2)!}^2 == -1 (mod p).
As an example, consider p=13. Then (p-1)/2 is 6, 6! = 720, which is 5 (mod 13), and 5^2 = 25 == -1 (mod 13).
You'll need to work through the details to convince yourself.
FWIW, I don't understand any of your last paragraph, because (a * b) / b doesn't seem at all hard to me ... unless you're working in a group you haven't told me about.
- AnimalMuppet 7y agoThank you. Yeah, it's going to take me a bit to work through all that. (I'm thinking about this in my evenings, and when tests are running at work.) On the last paragraph: I had thought (assumed?) that, in the integers mod p, (a * b)/b was hard if p was large. Is there an algorithm better than O(p) for this? My group was the complex integers modulo p. Now to do (a * b)/b, you have to find both the real and imaginary components of a.
- ColinWright 7y ago> Thank you. You're welcome > Yeah, it's going to take me a bit to work through all that. It does go stage by stage, so get a good feel for the proof of Wilson's theorem first. That gives you most of the necessary tools for the insight in the next step. > On the last paragraph: I had thought (assumed?) that, in the integers mod p, (a * b)/b was hard if p was large. Is there an algorithm better than O(p) for this? You can find the multiplicative inverse in Z_p by using an extended Euclidean Algorithm, which works in O(log p), and hence is trivial. > My group was the complex integers modulo p. Now to do (a * b)/b, you have to find both the real and imaginary components of a. Probably similarly efficient, as the Euclidean Algorithm works in the Gaussian Integers, but I haven't checked it. My contact details are in my profile.
- AnimalMuppet 7y agoSo {((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.