Results 1 to 6 of 6

Math Help - Modulo problem

  1. #1
    Member
    Joined
    Oct 2006
    Posts
    84

    Modulo problem

    Okay, so I'm supposed to find the least nonnegative integer i such that

    4^30 is congruent to i (mod 19).

    I'm not sure how to approach this since my textbook doesn't really say how this type of problem is done so any help would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,845
    Thanks
    320
    Awards
    1
    Quote Originally Posted by clockingly View Post
    Okay, so I'm supposed to find the least nonnegative integer i such that

    4^30 is congruent to i (mod 19).

    I'm not sure how to approach this since my textbook doesn't really say how this type of problem is done so any help would be greatly appreciated.
    My approach here won't be unique, but the method should be fairly clear.

    4^3 = 64 \equiv 7 (mod 19)

    So
    4^{30} = (4^3)^{10} \equiv 7^{10} (mod 19)

    Again:
    7^2 \equiv 11 (mod 19)

    So
    7^{10} = (7^2)^{5} \equiv 11^5 (mod 19)

    You can probably do this one by directly but we can simplify this one last time:
    11^2 \equiv 7 (mod 19)
    11^3 \equiv 1 (mod 19)

    So finally:
    4^{30} \equiv 7^{10} \equiv 11^5 = 11^2 \cdot 11^3 \equiv 7 \cdot 1 = 7 (mod 19)

    4^{30} \equiv 7 (mod 19)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2006
    Posts
    84
    Thanks for your help.

    I am still a little confused as to how you got the very first equation though (listd below)...I'm a little confused as to where the 7 came from...

    4^3 = 64 is congruent to 7(mod 19)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by clockingly View Post
    Okay, so I'm supposed to find the least nonnegative integer i such that

    4^30 is congruent to i (mod 19).

    I'm not sure how to approach this since my textbook doesn't really say how this type of problem is done so any help would be greatly appreciated.
    You can also do this...
    4^{30}=2^{60}
    And,
    2^{18}\equiv 1 (\mbox{ mod }19)
    By Fermat's little theorem since 19 is prime not divisible by 2.
    Cubing,
    2^{54}\equiv 1 (\mbox{ mod }19)
    Multiply both sides by 2^6=64\equiv 7 we we have,
    2^{60}\equiv 7 (\mbox{ mod }19)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by clockingly View Post
    Thanks for your help.

    I am still a little confused as to how you got the very first equation though (listd below)...I'm a little confused as to where the 7 came from...

    4^3 = 64 is congruent to 7(mod 19)
    That is becuase,
    64\equiv 7 (\mbox{ mod }19)
    Right?

    Because it leaves a remainder of 19.

    ( 64=3\cdot 19+7)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615
    Hello, clockingly!

    Another approach . . .


    Find the least nonnegative integer n such that: .  4^{30} \equiv n \pmod{19}

    I found that: . 4^5 \:=\:1024 \:\equiv\:-2 \pmod{19}

    Then: . 4^{30} \:=\:(4^5)^6 \:\equiv\:(-2)^6 \pmod{19}

    And: . (-2)^6\:=\:64\:\equiv\:7\pmod{19}

    Therefore: . 4^{30}\:\equiv\:7\pmod{19}

    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

    I also found that: . 4^9\:\equiv\:1\pmod{19}

    Then: . 4^{30}\:=\:\left(4^9\right)^3\cdot4^3 \:\equiv\:(1^3)4^3\pmod{19}

    And: . 4^3\:=\:64\:\equiv\:7\pmod{19}

    But I see that TPHacker beat me to it.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modulo problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 17th 2011, 07:17 PM
  2. Modulo problem
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: September 7th 2010, 05:53 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. Help with Modulo Problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 24th 2009, 08:54 AM
  5. Modulo problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 7th 2008, 12:25 PM

Search Tags


/mathhelpforum @mathhelpforum