Results 1 to 4 of 4

Math Help - 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  x^2 \equiv 1 \mod{2^b} has  4 solutions when  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  x^2 \equiv 1 \mod{2^b} has  4 solutions when  b \geq 3.
    first see that 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 x=2^rs + 1, where

    r \geq 1, and s is an odd number. then: 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. r > 1: then 2^{r-1}s + 1 and s are both odd and thus (1) gives us: r \geq b-1. thus: x =2^r s + 1 \equiv 2^{b-1} + 1 \ \text{or} \ 1 \mod 2^b.

    case 2: r=1: in this case (1) gives us: s(s+1) \equiv 0 \mod 2^{b-2}. but s is odd. hence s \equiv -1 \mod 2^{b-2}. therefore: x=2s+1 \equiv -1 \mod 2^{b-1}. thus: 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 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 x=2^rs + 1, where

    r \geq 1, and s is an odd number. then: 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. r > 1: then 2^{r-1}s + 1 and s are both odd and thus (1) gives us: r \geq b-1. thus: x =2^r s + 1 \equiv 2^{b-1} + 1 \ \text{or} \ 1 \mod 2^b.

    case 2: r=1: in this case (1) gives us: s(s+1) \equiv 0 \mod 2^{b-2}. but s is odd. hence s \equiv -1 \mod 2^{b-2}. therefore: x=2s+1 \equiv -1 \mod 2^{b-1}. thus: x \equiv 2^{b-1}-1 \ \text{or} \ -1 \mod 2^b. \ \Box
    In case 2, why does  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  x=2s+1 ?
    Because r=1 and so x=2^rs+1 = 2s+1.
    ---

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

Search Tags


/mathhelpforum @mathhelpforum