# Simple ( ? ) congruence

1. Mar 27, 2005

### b0mb0nika

I have to show that this congruence has solutions:

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

i dont 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 ?

2. Mar 27, 2005

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

3. Mar 28, 2005

### robert Ihnot

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

4. Mar 28, 2005

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

5. Mar 28, 2005

### robert Ihnot

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

6. Mar 30, 2005

### b0mb0nika

but by doing what u guys said..that would give me the solutions to the congruence. I dont really need to find them. Is there maybe another way to do it, just to show that it has solutions, without actually finding them?

7. Mar 31, 2005

### 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?