Congruence modulo a power of two let $a \geq 3$. Let $2^a \mid c^2-1$. 
By simple divisibility rules I get 
$$c \equiv 1 \mod 2^a \quad \text{or} \quad c \equiv -1 \mod 2^a  $$
or
$$c \equiv 1 \mod 2^{a-1},\quad  c \equiv  -1 \mod 2 $$
or
$$c \equiv -1 \mod 2^{a-1},\quad  c \equiv  1 \mod 2 $$
Can you explain me how to obtain the following congruence:
$$
c \; \equiv \; \pm 1 + 2^{a-1} \mod 2^a 
$$
??
 A: We want to solve the congruence $(c-1)(c+1)\equiv 0\pmod{2^a}$, where $a\ge 3$. Note that $c$ must be odd, and that $c-1$ and $c+1$ are two consecutive even numbers.
Since $c-1$ and $c+1$ are consecutive even numbers, one of them is congruent to $2$ modulo $4$, and therefore only has one $2$ to contribute to the product.
Case 1: [$c+1\equiv 2\pmod{4}$]  Since $2^a$ divides $(c-1)(c+1)$, $2^{a-1}$ must divide $c-1$. So $c\equiv 1\pmod{2^{a-1}}$, and therefore $c=1+k2^{a-1}$ for some integer $k$. If $k$ is even, then $s\equiv 1\pmod{2^a}$. If $k$ is odd then $c\equiv 1+2^{a-1}\pmod{2^{a}}$. 
It is clear that $c\equiv 1\pmod{2^a}$ and $c\equiv 1+2^{a-1}\pmod{2^a}$ are solutions.
Case 2: [$c-1\equiv 2\pmod{4}$] Then $2^{a-1}$ must divide $c+1$, and therefore $c=-1+k2^{a-1}$ for some integer $k$. If $k$ is even then $c\equiv -1+2^{a-1}\pmod{2^{a}}$, and if $k$ is odd then $c\equiv -1+2^{a-1}\pmod{2^{a}}$.
If $a\ge 3$, then the four solutions are distinct modulo $2^a$. 
A: Extended hints (prove/validate/justify the steps):


*

*$c^2-1=(c-1)(c+1)$

*We want the product $mn$ with $m=c+1$, $n=c-1$ to be divisible by $2^a$. For that to happen we must have an integer $k, 0\le k\le a,$ such that $2^k\mid m$ and $2^{a-k}\mid n$.

*Because $c+1$ and $c-1$ differ from each other by two, at most one of them can be divisible by four.

*Therefore in the second bullet the parameter $k$ must be one of $0,1,a-1,a$. The in-between range of choices does not work.

*The given list of four possibilities comes out of this.

