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

$\begingroup$

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

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

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy