x²+y²=-1 mod p ?

[Dr Sardonicus]

Originally Posted by Andrew Usher

<snip>
- there clearly can't be any other residues (the converse statement)
- there can't be any fewer; because the groups are cyclic of even order, 1/2 the members must be residues
<snip>

"Can't be other residues?" What about p^2 (mod p^3)?

For e > 1, the integers (mod p^e) are no longer a field; the multiplicative group no longer consists of all nonzero residues. The multiples of p, a*p for a = 1 to p^(e-1) - 1, are nonzero (mod p^e) but are not in the multiplicative group.

[Andrew Usher]

Of course I meant coprime residues in that context - it is correct with that restriction - and my reference to the multiplicative group rather indicated this.

The final point, again, is that x^2 + y^2 = -1 mod k has solutions if and only if k does not divide by 4. I don't think you disagree with that.

[Dr Sardonicus]

Originally Posted by Andrew Usher

Of course I meant coprime residues in that context - it is correct with that restriction - and my reference to the multiplicative group rather indicated this.

The final point, again, is that x^2 + y^2 = -1 mod k has solutions if and only if k does not divide by 4. I don't think you disagree with that.

Actually, in the post you responded to, I proved that x^2 + y^2 = k (mod p) has a solution for every nonzero residue (mod p) (which, yes, coincides with residues prime to p). I used the fact that the multiplicative group is cyclic to establish that not every residue (mod p) has a square root (mod p). I used this, in turn, to show that there is at least one quadratic residue R (mod p) for which R + 1 is a quadratic non-residue (mod p).

Unfortunately, if you start at 1 and keep adding 1 modulo p^e for e > 1, you will run into multiples of p before you get to 0 (mod p^e), so that argument doesn't really work any more.

My first proof - the one which appeals to Dirichlet's theorem - carries through for residues modulo p^e which are prime to p, for any odd prime p. It doesn't rely at all on the fact that the multiplicative group mod p^e is cyclic.

If you actually have a proof that x^2 + y^2 == -1 (mod p^e) is solvable for odd prime p and e > 1, and which uses the fact that the multiplicative group is cyclic, by all means trot it out.

[Andrew Usher]

I didn't claim to have such a proof, but here's something. Note that I used the cyclicity of the group initially just for my short proof that the coprime residues mod p^e are equivalent to those mod p. But we can go farther with that - your 'Proof 2' can be used mod p^e, because we just find a pair mod p (guaranteed to be non-zero) and use that mod p^e - the multiplication step still works for the cyclic group, and gives all coprime non-residues.

Adding a few other pieces, we can get the most general statement that x^2 + y^2 = a mod b has solutions unless

- a mod b is 3 mod 4 or any power of 2 times that, or
- a divides by an odd power of a prime 3 mod 4, and b divides by a higher power of the same.

[Dr Sardonicus]

Originally Posted by Andrew Usher

Note that I used the cyclicity of the group initially just for my short proof that the coprime residues mod p^e are equivalent to those mod p.
<snip>

"Are equivalent to?" This is utter nonsense. It is true that "coprime to p" and "coprime to p^e" mean the same thing, but that is also true for a composite modulus. Every residue class (mod p) comprises p^(e-1) residue classes (mod p^e). The standard mapping of the residue classes (mod p^e) to the residue classes (mod p) is sometimes called "enlargement of cosets."

Refining a solution of the congruence x^2 + y^2 == k (mod p) for odd prime p to a solution modulo a higher power of p is not trivial. The usual direct argument uses successive approximations. The oddness of p is crucial in making the refinement work in going from (mod p) to (mod p^2). Also crucial is that at least one of x and y (say x) be nonzero (mod p). I note that assuming x is not 0 (mod p) also allows refinement to solutions to x^2 + y^2 == k +m*p (mod p^2).

It is also not trivial to prove that the multiplicative group (mod p^e) is cyclic for odd prime p and e > 1. Again, the usual argument uses successive approximations. And, AFAICT, the fact that the group is cyclic is totally irrelevant to refining solutions of

x^2 + y^2 == k (mod p)

to solutions (mod p^e).

I note that for p == 3 (mod 4), the only solution to x^2 + y^2 == 0 (mod p) is x == y == 0 (mod p). This fact disallows any "refinement" to x^2 + y^2 == m*p (mod p^2) for 0 < m < p.

However, there are many nontrivial solutions to x^2 + y^2 == 0 (mod p^2), e.g. x == p, y == -p (mod p^2).

[Andrew Usher]

I am not sure where you are going here, but I have no wish to argue further or expand the discussion. I took the cyclic nature of the groups as given and observed that, whatever term you wish to use for it, it is then easily seen that the (coprime) quadratic residues (actually, the residues to any power not divisible by p) mod p^e map to those mod p in the obvious sense.

Nor was I ever addressing the construction or enumeration of the sum-of-squares solutions, but only their existence.

Finally I clearly know of the difference between primes 1 mod 4 and 3 mod 4 respecting the sum of residues; that's where the last qualification of my last post comes from.