Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
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
1  
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
show 3 more comments

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
Much appreciated! –  Margret Button Nov 13 '12 at 3:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.