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

[b0mb0nika]

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 ?

 

[matt grime]

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)

 

[robert Ihnot]

Errata: so x =+/-9 mod 59 and x=1,3 mod 4, that's x=+/-6.
This then gives us four solutions.

 

[matt grime]

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.)

 

[robert Ihnot]

Gee whiz! i was trying not to call attention to you personally! Sorry.

 

[b0mb0nika]

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?

 

[matt grime]

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?