Theorem 122. of Hardy's Theory of Numbers.

Question

The following is from the Theory of Numbers by Hardy, et al. Obviously, the number of roots of (8.2.1) is at least the product of the numbers of roots of the separate congruences (8.2.2). But what if this type of solution to (8.2.1)? : Let $d$ be a solution to $f(x) \equiv 0 \ (\text{mod m})$ such that $f(x) \equiv 0 \ (\text{mod m_r})$ for one $r \in {\{1,2, \dots k}\}$ and not a solution to none of the $f(x) \equiv 0 \ (\text{mod m_i})$ for $i \ne r$. Then $d \equiv c_l \ (\text{mod m_r})$ and congruent to other solutions of other modules so is not one of those types in the set of elements like (8.2.3). So why the number of roots of (8.2.1) equals the product of the numbers of roots of the separate congruences (8.2.2)?

Answer 1

The claim is that every root mod $m$ of $f$ gives a unique set of solutions mod $m_i$ and vice versa. You see how to go from the first to the second. To go the other way you have to take $k$ solutions $d_1, ... , d_k$ such that $f(d_i) = 0 \text{ mod }m_i$. (Note the size of this set is equal to the product of the number of solutions to each $f(x) = 0 \text{ mod } m_i.$) Pick the unique number $d$ mod $m$ such that $d = d_i$ mod $m_i$ for all $i$ (this is the Chinese remainder theorem, and can be done by the euclidean algorithm).

For example, if we want to find the roots of $f(x) = x^2 + 3$ mod $12,$ we write $12 = 4 * 3,$ so $m_1 = 4, m_2 = 3.$ We solve $x^2+3 = 0$ mod $4,$ getting solutions $1$ and $3.$ We solve $x^2+3 = 0$ mod $3,$ and find $x=0$ is our only solution. Note that $x=1$ does not solve the original problem mod $12.$ However if we find a number that is $1$ mod $4$ and $0$ mod $3$, like $9,$ then we find: $$9^2 + 3 = (-3)^2 + 3 = 9 + 3 = 0 \text{ mod }12.$$ The second solution comes from finding a number that is $3$ mod $4$ and $0$ mod $3,$ ie $3$ mod $12.$