20230323, 21:20  #1 
Mar 2016
2^{4}×3^{3} Posts 
x²+y²=1 mod p ?
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. 
20230323, 22:24  #2 
"Forget I exist"
Jul 2009
Dartmouth NS
2·5^{2}·13^{2} Posts 
If x,y don't work neither will the additive inverses.

20230323, 23:05  #3  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{2}×2,549 Posts 
Quote:
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: Code:
forprime(p=2,800,if(p%40==31p%40==39,for(x=4,p\2,if(kronecker(1x^2,p)>=0,print(p" "x" "lift(sqrt(Mod(1x^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 

20230323, 23:34  #4  
"Forget I exist"
Jul 2009
Dartmouth NS
2·5^{2}·13^{2} Posts 
Quote:


20230324, 13:00  #5 
Feb 2017
Nowhere
2·31·103 Posts 
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(1x^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. 
20230325, 15:30  #6 
Jun 2003
2×811 Posts 
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) (p1/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? Last fiddled with by Citrix on 20230325 at 15:41 Reason: Grammar 
20230325, 16:30  #7  
Feb 2017
Nowhere
6386_{10} Posts 
Quote:
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 p1 for p == 1 (mod 4). 

20230404, 18:08  #8 
Feb 2017
Nowhere
2×31×103 Posts 
On the congruence x^2 + y^2 == k (mod p)
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 p1 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 p1 is even, it has a subgroup of order (p1)/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 (p1)/2 residues (mod p) are quadratic nonresidues. We use R to denote a (nonzero) quadratic residue and N a quadratic nonresidue. 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 (p1)/2 quadratic nonresidues (mod p), there is at least one R for which R + 1 = N, a quadratic nonresidue (mod p). So there is at least one quadratic nonresidue N for which x^2 + y^2 == N (mod p) is solvable. Finally, for any given quadratic nonresidue N, the set of quadratic nonresidues 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 nonresidue N, we can obtain solutions for any other quadratic nonresidue 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 [x1, y; y, x1][a;b] = [0;0] so (since here a and b are not both 0) the determinant (x1)^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 p1. Then 1 + m*(p1) = p^2, giving m = p+1. If p == 1 (mod 4), the order p1 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*(p1) 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*(p1) = p^2  2*p + 1 = (p1)^2, so m = p1. 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 p1, which is the order of the group SO(2) (mod p). Let s = g^((p1)/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 p1; 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 nonresidue (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 PariGP 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). 
20230405, 00:25  #9 
Dec 2022
448_{10} Posts 
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.

20230405, 12:59  #10  
Feb 2017
Nowhere
2·31·103 Posts 
Quote:
The multiplicative group mod 4 is cyclic, but it does not follow that x^2 + y^2 == 1 (mod 4) is solvable. 

20230406, 00:04  #11 
Dec 2022
2^{6}×7 Posts 
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 wellknown 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. 