Results 1 to 5 of 5

Math Help - Module 77

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    Module 77

    Evalute 2^{100000} in mod 77.

    I know that 2^{76} \equiv 1 \ (mod \ 77) , but how should I continue? Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1
    Quote Originally Posted by tttcomrader View Post
    Evalute 2^{100000} in mod 77.

    I know that 2^{76} \equiv 1 \ (mod \ 77) , but how should I continue? Thanks.
    Sorry, but I'm getting 2^{76} \equiv 9 \text{ (mod 77)}.

    There may be a more elegant way to do this but
    Note that 2^{30} \equiv 1 \text{ (mod 77)}

    So
    2^{100000} \equiv 2^{30 \cdot 3333 + 10} \equiv \left ( 2^{30} \right ) ^{3333} \cdot 2^{10} \text{ (mod 77)}

    \equiv 2^{10} \text{ (mod 77)}
    which is easy to finish off.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by tttcomrader View Post
    Evalute 2^{100000} in mod 77.

    I know that 2^{76} \equiv 1 \ (mod \ 77) , but how should I continue? Thanks.
    Hello,

    I guess you wanted to use Fermat's little theorem. Unfortunately, this only works if 77 is a prime number.

    Otherwise, you can use Euler's theorem which states that :

    \forall a \ < n, \ a^{\varphi(n)} \equiv 1 \ (mod \ n)

    With \varphi(n) the Euler's totient function, defined as :

    (p designing prime numbers)

    \varphi(p)=p-1

    \varphi(p^n)=p^{n-1}(p-1) (the first one can be a deduction of this one)

    \varphi(p^n q^r)=\varphi(p^n) \varphi(q^r) (with q a prime number)


    As 77 is 11x7, \varphi(77)=(11-1)(7-1)=60

    => 2^{60}\equiv 1 (mod \ 77)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2
    I actually got to this point with Euler, but then I'm stuck here.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Well,

    Division of 100.000 by 60.

    i'll say that 100 is 60x16+40

    So 100.000 is 60x16000+40.000

    2^{60 \times 16000}=(2^{60})^{16000} \equiv 1^{16000}[77]

    So you can throw off this term...

    There is 40.000 remaining : find the remain of 40.000 in the division by 60 (i've shown steps above, because i'm too lazy to take a calculator )
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: November 30th 2011, 03:50 AM
  2. Module Help
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: November 5th 2011, 04:13 PM
  3. About some module over a DVR
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 13th 2011, 01:48 AM
  4. k[x]-module
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 20th 2010, 04:03 PM
  5. R-module
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: February 20th 2009, 11:14 AM

Search Tags


/mathhelpforum @mathhelpforum