# Number of solutions of $x^2 \equiv 1 \pmod{2^rq}$

I need to show that the number of solutions of

$$x^2 \equiv 1 \pmod{2^rq}, (2^rq) \in \mathbb{N}$$

is $2^{s+t}$ where $s$ = #distinct prime divisors of $q$ and $t$ = 0,1,2 according as $r\le1$, $r=2$, $r\ge3$.

So far I've been able to prove show this for: $x^2 \equiv 1 \pmod{2^r}$

I'm having trouble seeing what happens taken mod ($2^r$ q) Thanks for any help!

-
I think you can just apply chinese remainder theorem? – sperners lemma Nov 12 '12 at 18:07
I was thinking chinese remainder theorem a while back in my thought process..but don't know how this would allow me to determine the number of distinct solution? – Margret Button Nov 12 '12 at 18:11
The solutions modulo $2^rq$ correspond to tuples of solutions, one for each prime divisor $q_i$ of $2^rq,$ modulo $q_i^{r_i}$ where $q_i^{r_i}||2^rq.$ – Andrew Nov 12 '12 at 18:14
I'm very sorry, but I just don't see this – Margret Button Nov 12 '12 at 18:22
@MargretButton, I'm sorry I thought q was prime. – sperners lemma Nov 12 '12 at 18:24

We must assume $q$ is odd (the statement certainly isn't true if $q$ is a power of $2$). Note that if $m_1, m_2, \ldots, m_k$ are relatively prime, $x$ is a solution of $x^2 \equiv 1 \mod m_1 m_2 \ldots m_k$ iff $x^2 \equiv 1 \mod m_1$, $x^2 \equiv 1 \mod m_2,\ \ldots x^2 \equiv 1 \mod m_k$. If $S_j = \{x \in {\mathbb Z}_{m_j}: x^2 \equiv 1 \mod m_j\}$, then $x$ is a solution of $x^2 \equiv 1 \mod m_1 \ldots m_j$ iff $x \in S_j \mod m_j$ for each $j$. By CRT the number of such solutions in ${\mathbb Z}_{m_1 \ldots m_k}$ is $|S_1| |S_2| \ldots |S_k|$: each one corresponds to choosing one member $x_1$ of $S_1$, one member $x_2$ of $S_2$, etc, and then taking $x$ so $x \equiv x_1 \mod m_1$, $x \equiv x_2 \mod m_2$, etc. So you just have to see how many solutions there are mod $2^r$ (which you have already done) and mod $p^m$ if $p$ is an odd prime. For the latter, note that $x^2 - 1 = (x-1)(x+1)$, and $x-1$ and $x+1$ can't both be divisible by $p$.