Solutions to $a^2\equiv 1\mod 2^k$
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$.)
$\endgroup$ 23 Answers
$\begingroup$Hint: You're asking for $2^k|(a+1)(a-1).$ $\gcd(a+1,a-1)$ is at most $2$.
$\endgroup$ 1 $\begingroup$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$.
$\endgroup$ $\begingroup$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?
$\endgroup$
