Thread: Quadratic Reciprocity

Question:

Solve the quadratic congruence x^2=11(mod 35).

[Hint: after solving x^2=11(mod 5) and x^2=11(mod 7), use the Chinese
remainder theorem.]

1. What x satisies x^2= 11 (mod 5)?
You can answer that by "brute strength": 1^2= 1, 2^2= 4, 3^2= 9= 4 (mod 5), 4^2= 16= 1 (mod 5) (Aha!).

2. What x satisfies x^2= 11 (mod 7)?
Do the same thing as above.

Now, what is the "Chinese remainder theorem"?

Originally Posted by cathwelch

Question:

Solve the quadratic congruence x^2=11(mod 35).

[Hint: after solving x^2=11(mod 5) and x^2=11(mod 7), use the Chinese
remainder theorem.]

You know the factors of 35 and you obviously know the CRT, but I do not understand the basis of the question. Are you looking for a simple answer, or a method to solve it?

Originally Posted by HallsofIvy

1. What x satisies x^2= 11 (mod 5)?
You can answer that by "brute strength": 1^2= 1, 2^2= 4, 3^2= 9= 4 (mod 5), 4^2= 16= 1 (mod 5) (Aha!).

I wonder why you didn’t go Aha! three numbers earlier.

Just not very bright!