Ask HN: Weird property of x^2+1=0 in modular rings | Hacker News Reader

Ask HN: Weird property of x^2+1=0 in modular rings

4 pointsAnimalMuppet9 comments

In a modular ring (the integers modulo p), there can be real (not imaginary) solutions to x^2+1=0. If p is a prime greater than two, then x^2+1=0 has two solutions if p=4n+1 (for some integer n), and zero solutions if p=4n+3.

I can prove that x^2+1=0 has solutions in pairs. (If x^2+1 = 0, mod p, then (p-x)^2+1 = p^2-2px+x^2+1 = x^2+1 = 0, mod p.)

I can even prove that x^2+1=0 has either zero or two solutions. (x and y can't both solve it for y != p-x, if p is prime, because if y=x+k, then (x+k)^2+1 = x^2+2kx+k^2+1 = 0 mod p. But x^2+1=0, so 2kx+k^2 = 0 mod p. That is, k(k+2x) = 0 mod p. But p is prime, so either k = 0 mod p, or k+2x = 0 mod p. If k = 0, then y = x (because y=x+k). If k+2x = 0 mod p, then k+2x = p, so x+(x+k) = p, so x+y=p, so y = p-x. Therefore there are never more than two solutions.)

Can anyone explain why there are always two solutions if p=4n+1, and always zero if p=4n+3?

View on HN

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.

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.

No, 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.

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.

Thank 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.

> 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.

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.

> 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.

> 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.

Reply on news.ycombinator.com