So I'm reading Knuth's 'Discrete Mathematics' at the moment and there's a paragraph detailing how many solutions are there for $x^{2} \equiv 1 \pmod{p}$.
So other cases (when $p$ is an odd prime or when p is equal to $2$ or $4$) are clear to me, but I'm having trouble wrapping my head around the case when $p=2^{k}$ with $3 \leq k$.
Here's what's troubling me
If $2^{k}|(x - 1)(x + 1)$ then either $(x - 1)$ or $(x + 1)$ is divisible by $2$ but not by $4$, so the other one must be divisible by $2^{k-1}$.
How come? I don't see that at all...
In general, there are cases in which neither $x+1$ nor $x-1$ is divisible by $2$ (take $x$ to be an even number).
It is given that $2^k | (x+1)(x-1) $.
Suppose neither $x+1$ nor $x-1$ is divided by $2$, then $2$ does not divide $(x+1)(x-1)$. So, there is no point of considering $2^k | (x+1)(x-1)$.
So, without loss of generality, suppose $2$ divides $x+1$
suppose both $(x+1)$ and $(x-1)$ are divisible by $4$ then, we should have $2^{2m} |(x+1)(x-1) $ which need not be the case always... (it is not specified that power of $2$ is even)
So, we can suppose $x+1$ is divisible by $2$ but not by $4$.
So, we should have $2^{k-1} | (x+1)$