Results 1 to 5 of 5

Thread: 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 $\displaystyle 3^{40}\, (mod 7) $

    I know that I can take $\displaystyle 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 $\displaystyle 3^{40}\, (mod 7) $

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

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

    ie

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

    so we get

    $\displaystyle 3^6 \equiv 1 \mod (7)$

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

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

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

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

    $\displaystyle 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:

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

    Fermats little theorem gives us:

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

    $\displaystyle 4^{15}=(4^{6})^{2} \cdot 4^{3} $ $\displaystyle \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:

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

    Fermats little theorem gives us:

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

    $\displaystyle 4^{15}=(4^{6})^{2} \cdot 4^{3} $ $\displaystyle \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: Nov 10th 2008, 01:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 30th 2008, 05:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 30th 2008, 09:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 29th 2008, 10:57 AM

Search Tags


/mathhelpforum @mathhelpforum