x²+y²=-1 mod p ?

[bhelmes]

A peaceful and pleasant night for you,

If p is a prime then
x²+y²=-1 mod p is always solvable for x,y element N
but is there a better algorithm to solve it instead of checking all permutations ?

Would be nice if you spend me a link or at least a key word.

[science_man_88]

Originally Posted by bhelmes

A peaceful and pleasant night for you,

If p is a prime then
x²+y²=-1 mod p is always solvable for x,y element N
but is there a better algorithm to solve it instead of checking all permutations ?

Would be nice if you spend me a link or at least a key word.

If x,y don't work neither will the additive inverses.

[Batalov]

Originally Posted by bhelmes

A peaceful and pleasant night for you,

If p is a prime then
x²+y²=-1 mod p is always solvable for x,y element N
but is there a better algorithm to solve it instead of checking all permutations ?

Would be nice if you spend me a link or at least a key word.

I can solve half 7/8th of the problem for you.
When p is 1 or 2(mod 4), then you can take x=0 and y=lift(sqrt(Mod(-1,p)))
Else, if p is 3(mod 8), then you can take x=1 and y=lift(sqrt(Mod(-2,p)))
Else, if p is 7 or 23(mod 40), then you can take x=2 and y=lift(sqrt(Mod(-5,p)))

For the rest, when p is 31 or 39(mod 40), you can, for now, loop x (starting from 4), solve for y:

forprime(p=2,800,if(p%40==31||p%40==39,for(x=4,p\2,if(kronecker(-1-x^2,p)>=0,print(p" "x" "lift(sqrt(Mod(-1-x^2,p))));break))))
31 4 13
71 4 14
79 4 33
151 5 27
191 6 66
199 4 88
239 5 90
271 5 40
311 4 43
359 5 127
431 4 198
439 4 185
479 4 221
599 10 194
631 5 115
719 4 197
751 4 67

[science_man_88]

Originally Posted by Batalov

For the rest, when p is 7(mod 8), you can, for now, loop x (starting from 2), solve for y:

parforprimestep(p=7,500,8,for(x=2,(p-1)\2,if(kronecker(-1-x^2,p)>=0,print(p" "x" "lift(sqrt(Mod(-1-x^2,p))));break)))
7 2 3
23 2 8
31 4 13
47 2 18
71 4 14
79 4 33
103 2 43
127 2 54
151 5 27
167 2 50
191 6 66
199 4 88
223 2 21
239 5 90
263 2 28
271 5 40
311 4 43
359 5 127
367 2 27
383 2 83
431 4 198
439 4 185
463 2 213
479 4 221
487 2 143

Fixed code to parforprimestep

[Dr Sardonicus]

AFAICT the only important distinction here for p > 2 is whether p == 1 or 3 (mod 4). In the former case, I don't see any better solution than x = 0, y a square root of -1 (mod p) as already indicated.

For p == 3 (mod 4) it seems to me that checking kronecker(-1-x^2, p) for x = 1, 2, etc. until it is 1 is a good general prescription. As already indicated, x = 1 or 2 covers 3/4 of primes congruent to 3 (mod 4).

I will point out that for p == 3 (mod 4) there is a formula for a square root of a quadratic residue r (mod p), namely Mod(r,p)^((p+1)/4). I don't know whether this is faster or slower than sqrt(Mod(r,p)).

Given one solution to x^2 + y^2 = m (mod p), all solutions can be expressed x*a - y*b, y*a + x*b where a^2 + b^2 = 1.

The group of "rotation matrices" [a,b;-b,a] with a^2 + b^2 == 1 (mod p) is cyclic, and has order p+1 for p == 3 (mod 4). For details, including a method for producing a cyclic generator, see this post.

FWIW the maximum least value of "x" for which -1 - x^2 is a quadratic residue (mod p) for p == 3 (mod 4), p < 500000 is 19 for p = 50311. For p < 2^27 the maximum is 28, for p = 36732511.

[Citrix]

A special case would be:-

You can solve 2*A^2+1==0 (mod p)

Then (2*A^2+1)^2==0 (mod p)

4*A^4+4*A^2+1==0 (mod p)

X^2=4*A^4
Y^2=4*A^2

X^2+Y^2+1==0 (mod p)
X^2+Y^2==-1 (mod p)

Otherwise to generate all the solutions for a prime P you can generate all X^2 values (mod p) (p-1/2 steps)
Then sort the list in ascending order.
You can then find the solutions pairs (Note that only the first half of the terms on the list will need to be checked)
There are plenty of solutions for every P


Does anyone know how to prove that X^2+Y^2==-1 (mod p) always has a solution for all P?

[Dr Sardonicus]

Originally Posted by Citrix

<snip>
Does anyone know how to prove that X^2+Y^2==-1 (mod p) always has a solution for all P?

The case p = 2 is left as an exercise.

For odd primes, see this post. The number of solutions to x^2 + y^2 == k (mod p) is the same for every nonzero k (mod p).

This number is p+1 for p == 3 (mod 4), and p-1 for p == 1 (mod 4).

[Dr Sardonicus]

I will leave the case p = 2 as an exercise, and assume p is a prime greater than 2.

The integers mod p, Z/pZ or F_p are a field [the usual rules of addition and multiplication for the integers apply, and every nonzero residue (mod p) has a multiplicative inverse (mod p)]. The p-1 nonzero residues thus form a group under multiplication. This group is cyclic, and a cyclic generator is called a primitive root (mod p). Primitive roots are often denoted by g.

Since the multiplicative group of nonzero elements (mod p) is cyclic, and its order p-1 is even, it has a subgroup of order (p-1)/2. If g is primitive root (mod p), this subgroup is generated by g^2. This subgroup thus comprises the nonzero squares (mod p), also called the quadratic residues (mod p). The remaining (p-1)/2 residues (mod p) are quadratic non-residues. We use R to denote a (nonzero) quadratic residue and N a quadratic non-residue.

We note that x = y = 0 (mod p) is always a solution to x^2 + y^2 == 0 (mod p). If k is a nonzero residue (mod p), we have the following quick (but totally ludicrous and computationally not very useful) proof:

PROOF 1: Let p > 2 be prime. Then x^2 + y^2 == k (mod p) is solvable for any nonzero k (mod p).

Let k (mod p) be a nonzero residue class (mod p). We have by the Chinese Remainder Theorem that there is a unique residue class b (mod 4*p) such that b == k (mod p) and b == 1 (mod 4). Clearly b is relatively prime to 4*p.

By Dirichlet's theorem on primes in arithmetic progressions, the arithmetic progression 4*p*n + b, n = 0, 1, 2, etc contains infinitely many primes.

Let q be one of these. Since q == 1 (mod 4), q is the sum of two squares, q = x^2 + y^2. Since q == k (mod p), the congruence x^2 + y^2 == k (mod p) is therefore solvable.

The following proof uses only very basic concepts. I make no claim of originality - I know for a fact that most of the arguments have been known for decades if not centuries, and I'm pretty sure the rest have been as well.

PROOF 2: Let p > 2 be prime. Then x^2 + y^2 == k (mod p) is solvable for any nonzero k (mod p).

First, if R is a (nonzero) quadratic residue (mod p), x^2 + y^2 == R (mod p) is solvable. (Just take x to be a square root of R (mod p), and y = 0.) We also have:

Next, if R is a (nonzero) quadratic residue (mod p), x^2 + y^2 = R + 1 is solvable. (Take x as a square root of R (mod p), and y = 1.)

Now R = 1 is a quadratic residue (mod p) for any prime p. By repeatedly adding 1, we obtain all residues (mod p). Since there are (p-1)/2 quadratic non-residues (mod p), there is at least one R for which R + 1 = N, a quadratic non-residue (mod p). So there is at least one quadratic non-residue N for which x^2 + y^2 == N (mod p) is solvable.

Finally, for any given quadratic non-residue N, the set of quadratic non-residues is given by N*R, where R runs through the set of nonzero quadratic residues (mod p). From a solution to x^2 + y^2 = N for a given quadratic non-residue N, we can obtain solutions for any other quadratic non-residue N*R, by multiplying x and y by a square root of R (mod p).

Thus, we have shown the existence of solutions to x^2 + y^2 = k for every residue k (mod p).

Next, we count the solutions. To do this, note that if a^2 + b^2 = c^2 + d^2 == k (mod p), then (a^2 + b^2)*(c^2 + d^2)/k^2 == 1 (mod p). Using the usual formulas for expressing the product of sums of two squares as a sum of two squares we find that with

x = (a*c + b*d)/k and y = (a*d - b*c)/k, we have M[a;b] = [c;d], where M = [x, y; -x, y] and x^2 + y^2 == 1 (mod p).

Further, the matrix M is unique. [x, y; -y, x][a;b] = [a; b] we have [x-1, y; -y, x-1][a;b] = [0;0] so (since here a and b are not both 0) the determinant (x-1)^2 + y^2 = 2 - 2*x must be 0, so x = 1 and y = 0.

Therefore, the number of solutions to x^2 + y^2 == k (mod p) is the same for every nonzero k (mod p), and this number is equal to the number of solutions to x^2 + y^2 == 1 (mod p). Call this number m.

To determine m, we need to know the number of solutions to x^2 + y^2 == 0 (mod p). For p == 3 (mod 4) the order of the multiplicative group (mod p) is not divisible by 4, so x^2 + 1 == 0 (mod p) has no solutions. It follows that for p == 3 (mod 4) the only solution to x^2 + y^2 == 0 (mod p) is x = 0 and y = 0. The number of pairs (x, y) (mod p) is p*2. The number of nonzero residues is p-1. Then 1 + m*(p-1) = p^2, giving m = p+1.

If p == 1 (mod 4), the order p-1 of the multiplicative group is divisible by 4, so the equation x^2 + 1 == 0 (mod p) is solvable. Given such an x, for any nonzero a (mod p) there are two solutions (a*x, a) and (a*x, -a) (mod p). Therefore, there are 2*(p-1) nontrivial solutions in addition to 0^2 + 0^2 == 0 (mod p), hence 2*p - 1 pairs (x, y) for which x^2 + y^2 == 0 (mod p). In this case we have m*(p-1) = p^2 - 2*p + 1 = (p-1)^2, so m = p-1.

The matrices M = [a, b; -b,a] with a^2 + b^2 = 1 form a group, the "special orthogonal group" SO(2) mod p. These are the 2x2 matrices which are orthogonal (inverse = transpose) and have determinant 1 (mod p). We show that SO(2) (mod p) is cyclic. To do this, note that the characteristic polynomial of [a, b; -b, a] is x^2 - 2*a* x + 1.

If p == 1 (mod 4), let g be a primitive root (mod p), and let a = (g + 1/g)/2 (mod p). Then x^2 - 2*a*x + 1 = x^2 - (g + 1/g)*x + 1 = (x - g)*(x - 1/g). The eigenvalues of M have multiplicative order p-1, which is the order of the group SO(2) (mod p). Let s = g^((p-1)/4)) (mod p). Then with a = (g + 1/g)/2 (mod p) and b = s*(g - 1/g)/2 (mod p), M = [a, b; -b, a] has eigenvalues g and 1/g, hence has multiplicative order p-1; that is, M is a cyclic generator of SO(2) (mod p).

If p == 3 (mod 4) the group SO(2) (mod p) has order p+1. In this case, we use the cyclotomic polynomial of primitive p+1^st roots of unity. Since p == -1 (mod p+1), it follows that the cyclotomic polynomial factors into irreducible quadratic factors (mod p). If x^2 - 2*a*x + 1 is one of these, then 4*a^2 - 4 is a quadratic non-residue (mod p), so that 4 - 4*a^2 is a quadratic residue, and therefore 1 - a^2 is also a quadratic residue (mod p). Let b be a square root of 1 - a^2 (mod p). Then the matrix M = [a, b; -b, a] is in SO(2) (mod p), and its eigenvalues are primitive p+1^st roots of unity, so M has multiplicative order p+1; that is, M is a cyclic generator of SO(2) (mod p).

Finally, we use the count of solutions to x^2 + y^2 == 1 (mod p) to determine when 2 is a quadratic residue (mod p).

For p == 3 (mod 4) the number of solutions is p+1. Of these, there are 4 solutions with either x = 0 or y = 0. The solutions with a*b ≠ 0, a ≠ b, and a ≠ -b occur in sets of 8, namely

[a, b], [-b, a], [-a, -b], [b, -a] and [a, -b], [b, a], [-a, b], [-b, -a].

Any solutions with a*b ≠ 0, and a = b or a = -b occur in a set of 4: [a, a], [-a, a], [-a, -a] and [a, -a].

If p == 3 (mod 8) then the total number of solutions is not divisible by 8, so there can be no solutions with b = ±a; i.e. 2*a^2 == 1 (mod p) has no solution.

If p == 7 (mod 8) however, the total number of solutions is divisible by 8, so there has to be a set of 4 solutions with b = ±a, i.e. 2*a^2 == 1 (mod p) has a solution.

A similar argument shows that for p == 1 (mod 4), 2*a^2 == 1 has no solution when p == 5 (mod 8) and does have a solution when p == 1 (mod 8).

Neither of these arguments is very helpful in finding a square root of 2 (mod p) when it exists. Computationally, the Pari-GP command sqrt(Mod(2, p)) will work.

For p == 3 (mod 4) we also have the general formula s = R^((p+1)/4) (mod p) for a square root of any given quadratic residue R (mod p).

For p = 8*n + 1, if g is a primitive root (mod p), g[sup]n[/sup ± g^-n is a square root of ±2 (mod p).

[Andrew Usher]

It is soluble for a composite modulus if and only if it is not a multiple of 4. This follows almost directly, given that the groups modulo odd prime powers are cyclic.

[Dr Sardonicus]

Originally Posted by Andrew Usher

It is soluble for a composite modulus if and only if it is not a multiple of 4. This follows almost directly, given that the groups modulo odd prime powers are cyclic.

Your argument is flawed.

The multiplicative group mod 4 is cyclic, but it does not follow that x^2 + y^2 == -1 (mod 4) is solvable.

[Andrew Usher]

That wasn't the implication - my argument fails for powers of 2 as yours would for 2. The point was that a composite modulus can be solved if every prime power factor can be and that all odd prime powers can (using a slight modification of your argument). The conclusion follows (knowing that 4 fails).

I wasn't intending a complete proof, but the key additional step is that every quadratic residue mod p an odd prime is a residue mod p^k. This well-known fact I show easily by:

- 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

4 doesn't work, even though it's cyclic, as 2 doesn't meet the second condition.