<s>[INST] 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 
$$
??
 [/INST] 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$. 
</s>