Congruence Problem

Let y = x + 2 (1). Then x2 + 4x + 3 ≡ 0 (mod m) (2) becomes y2 ≡ 1 (mod m) (3).

Since (1) is a bijective relation, all solutions to (3) corresponds to some solution to (2) and the number of solution will be same. Now, we count number of solution for (3).

Let m = p1e1 * p2e2 * .... * pkek where pi is a prime and ei is a natural number for all 1 ≤ i ≤ k.

Now, from (3) by Chinese Remainder Theorem (CRT) y 2≡ 1 (mod piei) for all 1 ≤ i ≤ k.

Thus, a necessary problem to solve is number of solutions for y2 ≡ 1 (mod pq) where p is a prime and q is a natural number. We divide this problem in the following lemmas:

1. y2 ≡ 1 (mod p) has 2 solutions where p is a prime and p > 2.
2. y2 ≡ 1 (mod pq) has 2 solutions where p is a prime and p > 2 and q is a natural number.
3. y2 ≡ 1 (mod 2q) has 1 solution when q = 1, has 2 solutions when q = 2, has 4 solutions for all q > 2.

Proof of these lemmas are left as an exercise for the readers.

Let f(m) = number of solutions of y2 ≡ 1 (mod m). Then by CRT f(m) = f(p1e1) * f(p2e2) * .... * f(pkek)