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

  • 4
    $\begingroup$ There's $2^{k-1}\pm 1$ too. $\endgroup$ Jun 19 '19 at 18:21
  • $\begingroup$ Thank you, but I am still curious about other, less trivial solutions; do they exist? $\endgroup$
    – Tejas Rao
    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$.

  • $\begingroup$ so, for $k>0$, $a$ is odd and $2^{k-1}|a\pm1$ $\endgroup$ 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?


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.