Solutions to $a^2\equiv 1\mod 2^k$

Question

I apologize in advanced as my literacy in this subject is not too great and this question may either be trivial or impossible as of yet.

I have seen many questions on stack exchange utilizing the Chinese Remainder Theorem to find solutions of $a^2\equiv 1\mod (p*q)$, where $p$ and $q$ are distinct primes.

My question is whether we can find nontrivial (besides $a\equiv \pm1\mod 2^k$) solutions of $a^2\equiv 1\mod 2^k$ by any method other than brute force, or whether solutions exist at all.

(Off the top of my head, $3^2\equiv 1\mod 2^2$, and furthermore, $3^2=2^2+1$, but I do not think that $a^2=2^k+1$ for any other $k$.)

Answer 1

Obviously $a$ needs to be odd, and by going to $-a$ if necessary we can assume $a\equiv 1\pmod 4$.

Therefore assume $a=2^nm+1$ with $n\ge 2$ and $m$ odd. We then have $$ a^2 = 2^{2n}m^2 + 2^{n+1}m + 1 $$ In binary, the rightmost set bits are $1$ itself and $2^{n+1}$. The latter of these does not coincide with any bit of $2^{2n}m^2$ because $2n>n+1$. That bit vanishes modulo $2^k$ iff $n+1\ge k$.

So the only solutions are $\pm 1$ and $2^{k-1}\pm 1$.

Answer 2

Hint: You're asking for $2^k|(a+1)(a-1).$ $\gcd(a+1,a-1)$ is at most $2$.

Answer 3

As $a$ is odd, $a\pm1$ are even

If $2^k$ divides $(a+1)(a-1)$ for $k-2\ge1$

$\implies2^{k-2}$ divides $\dfrac{a+1}2\cdot\dfrac{a-1}2$

Now $\dfrac{a+1}2-\dfrac{a-1}2=1$

So, they are relatively prime, hence both cannot be even

If $\dfrac{a+1}2$ is even, it must be divisible by $2^{k-2}$

What if $\dfrac{a-1}2$ is even?