Results 1 to 6 of 6

Math Help - find the least positive residue

  1. #1
    Member
    Joined
    Feb 2008
    Posts
    125

    find the least positive residue

    Find the least positive residue of 2^2004 modulo 31
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by mandy123 View Post
    Find the least positive residue of 2^2004 modulo 31
    2^5 \equiv 1(\bmod 31) so 2^{2000} \equiv 1^{400} =1 (\bmod 31). Thus, that is 2^{2004} \equiv 2^{4} = 16(\bmod 31).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    10
    I have a similar problem to solve. Let me see if I have this straight in your example before I move on to my problem.

    All multiples of 5 in the exponent will be congruent to 1 modulo 31 or in other words:

    2^(5k) = 1 mod 31 where k is a positive integer.

    When you divide 2004 by 5, you get 4 as a remainder. The remainder is tacked onto the final calculation:

    2^4 = 16 mod 31

    Here's a similar problem I've been working on: Find the least positive residue mod 47 of 2^2222. Please check my solution:

    2^23 = 1 mod 47. Therefore, 2^(23k) = 1 mod 47. Divide 2222 by 23 and I have 14 as a remainder. The final calculation is:

    2^14 = 28 mod 47

    So, 28 is the least positive residue mod 47 of 2^2222.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by carabidus View Post
    ...
    Here's a similar problem I've been working on: Find the least positive residue mod 47 of 2^2222. Please check my solution:

    2^14 = 28 mod 47

    So, 28 is the least positive residue mod 47 of 2^2222.
     2^{2222} \equiv 28 \mod 47
    Your answer is correct.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2010
    Posts
    1

    Question on least positive residule

    Hi,
    I'm trying to understand congruences, and least positive residues in specific. Could someone please explain to me how you get the 16 in

    2^4= 16 mod (31)

    or

    2^2222= 28 mod (47)

    I understand everything until the previous step, but I'm not sure of how you get the 16 and the 28 terms. Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by nush View Post
    Hi,
    I'm trying to understand congruences, and least positive residues in specific. Could someone please explain to me how you get the 16 in

    2^4= 16 mod (31)

    or

    2^2222= 28 mod (47)

    I understand everything until the previous step, but I'm not sure of how you get the 16 and the 28 terms. Thanks in advance.

    Well,  2^4 = 16 and what is  16 modulo  31 ?

    For the other problem, first observe that  2^{23}\equiv 1 \mod{47} .
    This is because  2^{23} = 2^6\cdot 2^6\cdot 2^6\cdot 2^5 .
     2^6=64\equiv 17 \mod{47} , So  2^{23}\equiv 17\cdot 17 \cdot 17 \cdot 32 \mod{47}
     \equiv 7\cdot 17\cdot 32 \mod{47}
     \equiv 25\cdot 32 \mod{47}
     \equiv 1 \mod{47}

    Now  2222 = 96\cdot 23+14
    so  2^{2222} = 2^{96\cdot 23+14} = \left(2^{23}\right)^{96}\cdot 2^{14} \equiv 1^{96}\cdot 2^{14} =2^{14} \mod{47} .

     2^{14} = \left(2^7\right)^2 = 128^2\equiv (-13)^2 \equiv 28 \mod{47}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Least positive residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 11th 2009, 11:58 AM
  2. Least Positive Residue
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 9th 2009, 09:26 AM
  3. Least Positive Residue using Fermat's Litl Thm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 25th 2009, 07:47 PM
  4. [SOLVED] Least Positive Residue
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 11th 2008, 08:45 AM
  5. find the least positive residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2008, 07:07 PM

Search Tags


/mathhelpforum @mathhelpforum