Proving Solutions for x^2 ≡ -23 (mod 4*59) with Jacobi Symbol

  • Context: Graduate 
  • Thread starter Thread starter b0mb0nika
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around the congruence equation x^2 ≡ -23 (mod 4*59) and the methods to demonstrate the existence of solutions. Participants explore the applicability of the Jacobi symbol and the Legendre symbol in this context, along with the implications of the even modulus.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested

Main Points Raised

  • One participant questions the use of the Legendre symbol due to the even modulus and inquires about the applicability of the Jacobi symbol.
  • Another participant suggests checking properties of potential solutions, specifically noting that x^2 ≡ -23 (mod 4) leads to x^2 ≡ 1 (mod 4) and x^2 ≡ -23 (mod 59) leads to x ≡ ±9 (mod 59).
  • A correction is made regarding the solutions, indicating that x should be ±6 (mod 59) instead of ±9.
  • One participant expresses a desire to demonstrate the existence of solutions without actually finding them, seeking alternative methods.
  • Another participant notes that known methods typically require odd numbers and questions whether the specific case of 23 being a square modulo both 4 and 59 is coincidental.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the methods to prove the existence of solutions, and multiple competing views regarding the use of the Jacobi symbol and the nature of the modulus remain evident.

Contextual Notes

The discussion highlights limitations related to the even modulus and the specific properties of the numbers involved, which may affect the applicability of certain mathematical tools.

b0mb0nika
Messages
36
Reaction score
0
I have to show that this congruence has solutions:

x^2 == -23 ( mod 4*59)

i don't think i can use the legendre symbol for that bc 4* 59 is even.

can i use the jacobi symbol ? ( -23 /4*59) or does it have to be odd too ?
 
Physics news on Phys.org
Firstly I'd check what properties any solution would have, namely

x^2= -23 = 1 mod 4
x^2=-23 = 36 mod 59.

so x =+/-9 mod 59 and x=1,3 mod 4

and i'd find what these translate to mod 236 (chinese remainder theorem)
 
Errata: so x =+/-9 mod 59 and x=1,3 mod 4, that's x=+/-6.
This then gives us four solutions.
 
sorry, indeed i mean x=+/-6 mod (59)

(note your errata has an erratum in it, it fails to mention which one i buggered up.)
 
Gee whiz! i was trying not to call attention to you personally! Sorry.
 
but by doing what u guys said..that would give me the solutions to the congruence. I don't really need to find them. Is there maybe another way to do it, just to show that it has solutions, without actually finding them?
 
There is no way I know of to do it, but that means little. Looking at the known methods for these things they need odd numbers. Do you think it was just coincidence that 23 happened to be an obvious square both modulo 4 and modulo 59?
 

Similar threads

Replies
12
Views
11K
  • · Replies 11 ·
Replies
11
Views
3K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 21 ·
Replies
21
Views
3K
Replies
2
Views
4K
  • · Replies 5 ·
Replies
5
Views
6K
  • · Replies 4 ·
Replies
4
Views
7K
  • · Replies 1 ·
Replies
1
Views
4K