mersenneforum.org > Math x²+y²=-1 mod p ?
 Register FAQ Search Today's Posts Mark Forums Read

 2023-03-23, 21:20 #1 bhelmes     Mar 2016 24×33 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.
2023-03-23, 22:24   #2
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·52·132 Posts

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

2023-03-23, 23:05   #3
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×2,549 Posts

Quote:
 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:
Code:
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

2023-03-23, 23:34   #4
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·52·132 Posts

Quote:
 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: Code: 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

 2023-03-24, 13:00 #5 Dr Sardonicus     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(-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.
 2023-03-25, 15:30 #6 Citrix     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) (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? Last fiddled with by Citrix on 2023-03-25 at 15:41 Reason: Grammar
2023-03-25, 16:30   #7
Dr Sardonicus

Feb 2017
Nowhere

638610 Posts

Quote:
 Originally Posted by Citrix 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).

 2023-04-05, 00:25 #9 Andrew Usher   Dec 2022 44810 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.
2023-04-05, 12:59   #10
Dr Sardonicus

Feb 2017
Nowhere

2·31·103 Posts

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

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

 2023-04-06, 00:04 #11 Andrew Usher   Dec 2022 26×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 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.

All times are UTC. The time now is 22:38.

Tue Jun 6 22:38:48 UTC 2023 up 292 days, 20:07, 0 users, load averages: 0.71, 0.90, 1.02

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔