0
$\begingroup$

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?
  • 1
    I think you will find the Chinese remainder theorem useful in this case.2012-10-18

1 Answers 1

1

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.$

  • 0
    Yes, that's what it boils down to in terms of CRT.2012-10-19