Euler's Criterion and Wilsons Theorem

I am trying to prove: if $m = p_1p_2\cdots p_r$ with $2 < p_1 < \cdots < p_r$ prime, then

$$x^2 \equiv 1\mod m$$

has $2^r$ solutions modulo $m$.

I know Euler's Criterion: $p$ is an odd prime s.t $p$ does not divide $b$. Then

$$b^{\frac{p-1}{2}} \equiv 1 \mod p \iff b \equiv t^2 \mod p\text{ for some }t \in \mathbb{Z}$$

and I know Wilson's Theorem: $n\mid (n-1)! +1 \iff$ $n$ is prime

1. How do I put these together?
• I think you will find the Chinese remainder theorem useful in this case. – Lord_Farin Oct 18 '12 at 14:51

Hint $\$ CRT (Chinese Remainder Theorem) yields multiplicativity of root counting functions,
i.e. by CRT, $\rm\:(n_1,n_2)= 1\:\Rightarrow\ \exists$ isomorphism $\rm\,h: \Bbb Z/n_1n_2 \to \Bbb Z/n_1 \times \Bbb Z/n_2\:$ via $\rm\:h(a) = (a_1,a_2).$
So for $\rm\,f\in \Bbb Z[x],\:$ we have: $\rm\: 0 = f(a)\iff (0,0) = h(f(a)) = f(h(a)) = f((a_1,a_2)) = (f(a_1),f(a_2)).$
In particular, for a polynomial like $\rm\: h = x^2 -1,\:$ which has precisely two roots $\pm1$ in each factor $\rm\,\Bbb Z/p,\ p\ne 2,\:$ it has precisely $\rm\,2^k\:$ roots in $\rm\,\Bbb Z/(p_1\cdots\, p_k)\,\cong\, \Bbb Z/p_1 \times \cdots \times \Bbb Z/p_k\! = R,\:$ which corresponds to every possible combination of sign choices in $\rm(\pm1,\,\ldots\,,\pm1)\in R.$
• Could you give me a more intuitive approach? I am beginning to see that by the CRT. I will have $r$ congruences each with $2$ solutions. Then it follows that I have $2^r$ solutions. – codeMasterFiveThousand Oct 18 '12 at 23:20