Results 1 to 4 of 4

Thread: x^2 mod 2^b

  1. #1
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163

    x^2 mod 2^b

    Show that the congruence $\displaystyle x^2 \equiv 1 \mod{2^b} $ has $\displaystyle 4 $ solutions when $\displaystyle b \geq 3. $
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by chiph588@ View Post

    Show that the congruence $\displaystyle x^2 \equiv 1 \mod{2^b} $ has $\displaystyle 4 $ solutions when $\displaystyle b \geq 3. $
    first see that $\displaystyle x \equiv \pm 1, \ \text{or} \ 2^{b-1} \pm 1 \mod 2^b$ satisfy the equation. we want to show that there are no other solutions. obviously such solution has got to be odd. so let $\displaystyle x=2^rs + 1,$ where

    $\displaystyle r \geq 1,$ and $\displaystyle s$ is an odd number. then: $\displaystyle x^2-1=2^{r+1}s(2^{r-1}s+1) \equiv 0 \mod 2^b,$ which we'll call it (1). now consider two cases:

    case 1. $\displaystyle r > 1$: then $\displaystyle 2^{r-1}s + 1$ and $\displaystyle s$ are both odd and thus (1) gives us: $\displaystyle r \geq b-1.$ thus: $\displaystyle x =2^r s + 1 \equiv 2^{b-1} + 1 \ \text{or} \ 1 \mod 2^b.$

    case 2: $\displaystyle r=1$: in this case (1) gives us: $\displaystyle s(s+1) \equiv 0 \mod 2^{b-2}.$ but $\displaystyle s$ is odd. hence $\displaystyle s \equiv -1 \mod 2^{b-2}.$ therefore: $\displaystyle x=2s+1 \equiv -1 \mod 2^{b-1}.$ thus: $\displaystyle x \equiv 2^{b-1}-1 \ \text{or} \ -1 \mod 2^b. \ \Box$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by NonCommAlg View Post
    first see that $\displaystyle x \equiv \pm 1, \ \text{or} \ 2^{b-1} \pm 1 \mod 2^b$ satisfy the equation. we want to show that there are no other solutions. obviously such solution has got to be odd. so let $\displaystyle x=2^rs + 1,$ where

    $\displaystyle r \geq 1,$ and $\displaystyle s$ is an odd number. then: $\displaystyle x^2-1=2^{r+1}s(2^{r-1}s+1) \equiv 0 \mod 2^b,$ which we'll call it (1). now consider two cases:

    case 1. $\displaystyle r > 1$: then $\displaystyle 2^{r-1}s + 1$ and $\displaystyle s$ are both odd and thus (1) gives us: $\displaystyle r \geq b-1.$ thus: $\displaystyle x =2^r s + 1 \equiv 2^{b-1} + 1 \ \text{or} \ 1 \mod 2^b.$

    case 2: $\displaystyle r=1$: in this case (1) gives us: $\displaystyle s(s+1) \equiv 0 \mod 2^{b-2}.$ but $\displaystyle s$ is odd. hence $\displaystyle s \equiv -1 \mod 2^{b-2}.$ therefore: $\displaystyle x=2s+1 \equiv -1 \mod 2^{b-1}.$ thus: $\displaystyle x \equiv 2^{b-1}-1 \ \text{or} \ -1 \mod 2^b. \ \Box$
    In case 2, why does $\displaystyle x=2s+1 $?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by chiph588@ View Post
    In case 2, why does $\displaystyle x=2s+1 $?
    Because $\displaystyle r=1$ and so $\displaystyle x=2^rs+1 = 2s+1$.
    ---

    Here is another way to solve this problem. But it is overkill. It is a known result that $\displaystyle \mathbb{Z}_{2^b}^{\times}$ is isomorphic to $\displaystyle \mathbb{Z}_{2} \times \mathbb{Z}_{2^{b-2}}$ for $\displaystyle b\geq 3$.
    Let $\displaystyle \phi: \mathbb{Z}_{2^b}^{\times} \to \mathbb{Z}_{2} \times \mathbb{Z}_{2^{b-2}}$ be an isomorphism.
    An element $\displaystyle x\in \mathbb{Z}_{2^b}^{\times}$ satisfies $\displaystyle x^2 = 1$ if and only if $\displaystyle \phi(2x)=\phi(1)$ iff $\displaystyle 2\phi(x) = 0$.
    Thus, there is a 1-to-1 corresponded between solutions to $\displaystyle x^2 = 1$ in $\displaystyle \mathbb{Z}_{2^b}^{\times}$ and solutions to $\displaystyle 2(x,y) = (0,0)$ in $\displaystyle \mathbb{Z}_{2} \times \mathbb{Z}_{2^{b-2}}$.
    However, there are clearly 4 solutions to $\displaystyle 2(x,y)=(0,0)$.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum