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.

What are the incongruent solutions for $x^2 \equiv 1 \pmod {2^k}$?

I tested it with a couple small values and came up with the answer and proof.

The answer is, if $k \ge 3, x \in \{1,2^{k-1}-1,2^{k-1}+1,2^k-1\}$.

Also note the lemma that if $2^{k+1}|n \Rightarrow 2^{k}|n$, which is trivial.

Then the proof by induction:

If $k = 3$, it is easy to check that the answer is correct.

Assume that the claim holds for $k \le n$.

Assume $k=n+1$. By the induction hypothesis, we see that $x^2 \equiv 1 \pmod {2^n}$ has four solutions: $\{1,2^{n-1}-1,2^{n-1}+1,2^n-1\}$. Because congruence is symmetric, we also see that $\{2^n+1,3*2^{n-1}-1,3*2^{n}+1,2^{n+1}-1\}$ are solutions.

Now apply the lemma and we see that the set of solutions for $x^2 \equiv 1 \pmod {2^{n+1}}$ is some kind of subset of the set of solutions for $x^2 \equiv 1 \pmod {2^n}$. This means that we only need to check the eight solutions generated above and select the correct ones.

We immediately see that the four solutions implied in the original statement are solutions. To test that the other four are not solutions, I give as an example the case $x=3*2^{n-1}-1$:

$(3*2^{n-1}-1)^2 = 1-3*2^n+9*2^{-2+2 n} = 1-2^n-0+2^{2*n-2}+2^n=1+2^{n-3} \neq 1 \pmod {2^{n+1}}.$

Others in the same way.

By the induction principle, the proof is finished.

Is the proof OK? And how do you prove it without knowing the set of solutions beforehand?

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

I think the way to get the answer without knowing it beforehand is this: $x^2\equiv1\pmod{2^k}$ says $2^k$ divides $(x+1)(x-1)$. Clearly $x$ must be odd, and the gcd of $x+1$ and $x-1$ is $2$, so we have either $x+1$ or $x-1$ divisible by $2^{k-1}$. This leads right away to the four solutions (for $k\ge3$).

share|improve this answer
    
Well, that was simple :D Thanks. –  Valtteri Feb 7 '13 at 23:02
add comment

Here's an easy alternative proof, no induction required.

For $k\geq 3$, $(\mathbb{Z}/2^k)^\times\cong\mathbb{Z}/2^{k-2}\times\mathbb{Z}/2$ (You can prove this with a binomial theorem argument, showing that $5=1+4$ has order $2^{k-2}$). Thus there are exactly four solutions, corresponding to the identity and the three elements of order $2$ in $\mathbb{Z}/2^{k-2}\times\mathbb{Z}/2$.

$\pm 1$ are obviously solutions. A quick check reveals that $2^{k-1}\pm1$ also work.

share|improve this answer
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.