5 ms·
If p is congruent to 3 mod 4 then it can't be the sum of two squares. To see that, consider x^2+y^2 mod 4. Each term is either 0 or 1 mod 4, so the sum can't
by ColinWright 7y ago
If p is congruent to 3 mod 4 then it can't be the sum of two squares. To see that, consider x^2+y^2 mod 4. Each term is either 0 or 1 mod 4, so the sum can't be 3.
If p is congruent to 1 mod 4 then it is the sum of two squares in exactly one way. That's an old theorem and has a gazillion proofs. You can easily find them online.
See if you can leverage that into what you need.
- ColinWright 7y agoNo 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.