# 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$$.)

• There's $2^{k-1}\pm 1$ too. Jun 19 '19 at 18:21
• Thank you, but I am still curious about other, less trivial solutions; do they exist? Jun 19 '19 at 18:24

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$$.

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

• so, for $k>0$, $a$ is odd and $2^{k-1}|a\pm1$ Jun 19 '19 at 19:06

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?