4 ms·
No reply, and it does feel a little like this was a homework question. Even so, if you contact me I can give you more information ... details in my profile.
by ColinWright 7y ago
No reply, and it does feel a little like this was a homework question. Even so, if you contact me I can give you more information ... details in my profile.
- AnimalMuppet 7y agoNo, it's not a homework problem. I'm really long in the tooth to be a student. It's just something I'm curious about. Actually, what I'm really curious about is that, if you take the complex numbers a+bi modulo p, then that forms a ring. It is a quotient ring if p is prime and of the form 4n+3, and not if p is of the form 4n+1. And I am curious as to why. It turns out that it can be reduced to the question I asked. But now I want to know why that is. I didn't answer right away, because I didn't know what to do with your answer. It's interesting, and plausibly relevant, but I must confess that I don't see how at the moment. I mean, x^2+1 has the same form, but... Take 13, for instance. 13 = 4 + 9 = 2^2 + 3^2. But I don't see how that connects to 5^2 + 1 = 26 = 0 mod 13. I'm not saying it's not there. It's very suggestive that what you said splits exactly on 4n+1 vs. 4n+3, but... I don't see the connection yet. Where I'm ultimately kind of trying to head is cryptography. Because of the real and complex components, you could get 2n bits of "hard to crack" out of n bits of "prime number". At least for something like a proof protocol: I generate a and b, and publish a and (a * b). Only I know b, and nobody else can generate it, because (a * b) / b is really hard. But when I publish b, everyone can easily verify that it's the right number.
- ColinWright 7y agoWell, 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.
- 7y ago