Results 1 to 5 of 5

Math Help - Congruence

  1. #1
    Senior Member Twig's Avatar
    Joined
    Mar 2008
    From
    Gothenburg
    Posts
    396

    Congruence

    hi

    I would be grateful if someone could walk me through how exactly to calculate 3^{40}\, (mod 7)

    I know that I can take 3^{40}\, (mod 7) \equiv (3\, (mod 7))^{40}

    How do I proceed?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by Twig View Post
    hi

    I would be grateful if someone could walk me through how exactly to calculate 3^{40}\, (mod 7)

    I know that I can take 3^{40}\, (mod 7) \equiv (3\, (mod 7))^{40}

    How do I proceed?
    Since 7 is prime we can use fermat little theorem

    ie

    a^{p-1} \equiv 1 \mod (p)

    so we get

    3^6 \equiv 1 \mod (7)

    now 6|40 to give 40=6\cdot 6+4

    so now 3^{40}=(3^6)^6\cdot 3^4

    But now mod 7 we know that this is the same as

    (3^6)^6\cdot 3^4 \mod (7) =1^6\cdot 3^4 \mod (7)

    81 \mod (7)=4\mod (7)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Twig's Avatar
    Joined
    Mar 2008
    From
    Gothenburg
    Posts
    396
    So basically, if I take another example, quite similar:

     4^{15}\, (mod\, 7)

    Fermats little theorem gives us:

     4^{6} \equiv 1 \, (mod \, 7) , and

     4^{15}=(4^{6})^{2} \cdot 4^{3}  \Rightarrow 4^{15} \, (mod\, 7) \equiv (4^{6})^{2} \cdot 4^{3} \, (mod\, 7 ) \equiv 4^{3} \, (mod\, 7) \equiv 64 \, (mod\, 7)\equiv 1  \, (mod\, 7 ) ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by Twig View Post
    So basically, if I take another example, quite similar:

     4^{15}\, (mod\, 7)

    Fermats little theorem gives us:

     4^{6} \equiv 1 \, (mod \, 7) , and

     4^{15}=(4^{6})^{2} \cdot 4^{3}  \Rightarrow 4^{15} \, (mod\, 7) \equiv (4^{6})^{2} \cdot 4^{3} \, (mod\, 7 ) \equiv 4^{3} \, (mod\, 7) \equiv 64 \, (mod\, 7)\equiv 1 \, (mod\, 7 ) ?
    Yes you got it
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Twig's Avatar
    Joined
    Mar 2008
    From
    Gothenburg
    Posts
    396
    Thanks again!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: May 12th 2009, 10:19 AM
  2. Congruence
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 10th 2008, 01:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 05:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 09:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 10:57 AM

Search Tags


/mathhelpforum @mathhelpforum