Number Theory - Number of Solutions

1. For each of the following congruences, determine the number of solutions.
(a). x2 = 103 (mod 420).
(b). x2 =29 (mod 1080).
(c). 2x2 -5x + 23 = 0 (mod 675).
(d). x2 + 3x - 22 = 0 (mod 108).

(a) Note that 420 = 2^2 * 3 * 5 * 7

x^2 = 103 = 3 (mod 4) has no solutions (squares mod 4 are 0, 1).
Hence, x^2 = 103 (mod 420) has no solutions as well.
----------------
(b) 1080 = 2^3 * 3^3 * 5.

x^2 = 29 = 5 (mod 8) has no solutions (squares mod 8 are 0, 1).
Hence, x^2 = 29 (mod 1080) has no solutions as well.
----------------
(c) 675 = 3^3 * 5^2.

2x^2 - 5x + 23 = 0 (mod 3)
==> -x^2 - 2x - 1 = 0 (mod 3)
==> (x + 1)^2 = 0 (mod 3)
==> x = 2 (mod 3).
Hence, there is a unique solution mod 3^2 and thus 3^3 as well (by the 'lifting' theorem).

2x^2 - 5x + 23 = 0 (mod 5)
==> 2x^2 - 2 = 0 (mod 5)
==> x = -1 or 1 (mod 5).
Hence, there are two solutions mod 5^2 by the lifting theorem.

By the Chinese Remainder Theorem, there are 1 * 2 = 2 distinct solutions mod 675.
-----------------
(d) 108 = 2^2 * 3^3

x^2 + 3x - 22 = 0 (mod 4)
==> x^2 + 3x + 2 = 0 (mod 4)
==> (x + 1)(x + 2) = 0 (mod 4)
==> x = 2, 3 (mod 4) by trial and error (being careful about possible zero divisors).
So, there are 2 solutions mod 4.

x^2 + 3x - 22 = 0 (mod 3)
==> x^2 - 1 = 0 (mod 3)
==> x = -1 or 1 (mod 3).
Hence, there are two solutions mod 3^2 and thus mod 3^3 by the lifting theorem.

By the Chinese Remainder Theorem, there are 2 * 2 = 4 distinct solutions mod 108.
------------------
I hope this helps!