Results 1 to 5 of 5

Math Help - Modulo help

  1. #1
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517

    Modulo help

    hey guys, I have a question here which I dont quite understand how my tutor got from a certain step...

    Compute: 2^21 mod 53

    \Rightarrow 2^{21} = x (mod 53)
    \Rightarrow 2^{21} = 2^{16} \cdot 2^{5} (mod 53)
    \Rightarrow 2^{16} = 2^8 \cdot 2^8 (mod 53)
    \Rightarrow 2^{8} = 256 (mod 53) <--FROM HERE
    \Rightarrow 256 = -9 (mod 53) <-- TO HERE, mainly where that -9 came from

    thanks for the help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,707
    Thanks
    1470
    Quote Originally Posted by jvignacio View Post
    hey guys, I have a question here which I dont quite understand how my tutor got from a certain step...

    Compute: 2^21 mod 53

    \Rightarrow 2^{21} = x (mod 53)
    \Rightarrow 2^{21} = 2^{16} \cdot 2^{5} (mod 53)
    \Rightarrow 2^{16} = 2^8 \cdot 2^8 (mod 53)
    \Rightarrow 2^{8} = 256 (mod 53) <--FROM HERE
    \Rightarrow 256 = -9 (mod 53) <-- TO HERE, mainly where that -9 came from

    thanks for the help!
    53 divides into 256 four times with remainder of 44. That is, 256= 4(53)+ 44. But it is also true, then, that 256= 4(53)+ 53- 9= 5(53)- 9. That is, -9+ 53= 44 so 44= -9 (mod 53). All numbers that differ by 53 are equivalent modulo 53.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,739
    Thanks
    645
    Hello, jvignacio!

    I have no idea why your tutor used such a roundabout approach!


    Compute: 2^{21} mod 53

    2^8 \:\equiv\: 256 \:\equiv\:44 \:\equiv\:-9 \text{ (mod 53)}
    I would solve it like this . . .


    . . \begin{array}{cccc}2^{21} &\equiv& 2,\!097,\!152 & \text{(mod 53)} \\ \\[-3mm]<br /> <br />
& \equiv& 48 & \text{(mod 53)} \end{array}

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by Soroban View Post
    Hello, jvignacio!

    I have no idea why your tutor used such a roundabout approach!


    I would solve it like this . . .


    . . \begin{array}{cccc}2^{21} &\equiv& 2,\!097,\!152 & \text{(mod 53)} \\ \\[-3mm]<br /> <br />
& \equiv& 48 & \text{(mod 53)} \end{array}

    To avoid using big numbers?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by jvignacio View Post
    To avoid using big numbers?

    2^6=11\!\!\!\pmod {53}\Longrightarrow 2^{12}=11^2=15\!\!\!\pmod {53}\Longrightarrow  2^{18}=2^6\cdot 2^{12}=11\cdot 15 = 165=6\!\!\!\pmod {53} \Longrightarrow 2^{21}=2^3\cdot 2^{18}=8\cdot 6=48\!\!\!\pmod {53}

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modulo
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 7th 2010, 05:14 PM
  2. modulo ?
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: April 16th 2010, 03:07 AM
  3. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  4. Modulo 42
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 2nd 2009, 05:00 PM
  5. Modulo
    Posted in the Algebra Forum
    Replies: 11
    Last Post: May 5th 2009, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum