Results 1 to 10 of 10

Math Help - Modular arithmetic

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    5

    Exclamation Modular arithmetic

    How do I calculate 5^7(mod 77)?
    Im at my wits end- nothing seems to work!!

    Also how is 5^157=1044(mod2773)?! Its there in one of the examples in my book and im wondering where that came from?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    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
    Hello,

    For the first one, I can't really see any simple method.
    5=25, 5^4=25^2=625
    77x2=154 and since 600=4x150, 77x8=154x4=600+16=-9 mod 625

    and 154=155-1=5x31-1 -> 5x31=1 mod 77.

    So finally 5^7=(5^4)^2 * 31 mod 77 = 81*31 mod 77 = 4x31 mod 77 = 124 mod 77 = -30 mod 77.


    As for the second one, it looks awful (even the first one was awful)... in which chapter was it ? what's the context ? it looks like some cipher stuff.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,397
    Thanks
    760
    the first one is a bit tedious, but i don't know about awful.

    5^3 = 125 = 48 mod 77
    5^4 = (48)(5) = 240 = 9 mod 77
    5^5 = 45 mod 77
    5^6 = 225 = 71 = -6 mod 77
    5^7 = -30 = 47 mod 77

    for the second one, 5^5 = 3125 = 352 mod 2773
    5^10 = (352)(352) = 123,904 = 1892 mod 2773
    5^20 = (1892)(1892) = 3,579,664 = 2494 mod 2773
    5^40 = (2494)(2494) = 6,220,036 = 197 mod 2773
    5^80 = (197)(197) = 38,809 = 2,760 = -13 mod 2773
    5^120 = (197)(-13) = -2561 = 212 mod 2773
    5^140 = (212)(2494) = (212)(-279) = -59,148 = -915 mod 2773
    5^150 = (-915)(1892) = -1,731,180 = -828 mod 2773
    5^155 = (-825)(352) = -291,456 = -291 mod 2773
    5^157 = (-291)(25) = -7275 = -1729 = 1044 mod 2773

    i'm sure there's an easier way to compute this, but as you see, it can be done "long-hand"
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2011
    Posts
    5
    Hi! Yes its horribly tedious
    You are right- this is part of cryptography, the RSA cryptosystem to be exact.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2011
    Posts
    5
    Deveno- Thanks sooooo much!!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    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
    Can you give the original questions then ? Because if it's a problem you've been given, there's no point in doing such calculations.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Quote Originally Posted by nicola5 View Post
    How do I calculate 5^7(mod 77)?
    Im at my wits end- nothing seems to work!!

    Also how is 5^157=1044(mod2773)?! Its there in one of the examples in my book and im wondering where that came from?
    The solution in both case requires the 'Chinese Remainder Theorem' which extablishes that if then the pair of equations...



    (1)

    ... has one and only one solution ...

    a) because 77= 7 x 11 is...



    (2)

    ... so that is solution of the pair of equations...



    (3)

    b) this case is a little more 'computational expensive' than the previous one. Because 2773= 59 x 47 is...



    (4)

    ... so that is solution of the pair of equations...



    (5)

    The procedure for solving the pair of equations like (1) will be described in a further post...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1
    Quote Originally Posted by nicola5 View Post
    How do I calculate 5^7(mod 77)?
    Im at my wits end- nothing seems to work!!

    Also how is 5^157=1044(mod2773)?! Its there in one of the examples in my book and im wondering where that came from?
    knowing the chinese remainder theorem helps.
    suppose you found out 5^7(mod 7) and 5^7(mod11) the according to chinese remainder theorem you can find out what is 5^7(mod 77). Even if you dont know chinese rem-theorem still the following will make it clear to you.




    so we have and,


    call 5^7=x so that it doesn't look tedious.

    now the first congruence gives
    substitute this in the second congruence to get:

    now

    substitute this in

    from the above we have:
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    A procedure for solving the pair of equations...



    (1)

    ... obtaining with and distinct primes consists in computing first ...



    (2)

    ... and then...

    (3)

    Now we try to solve the first pair of equations of my previous post...











    ... and we obtain the result obtained by abhishekkgp...

    The second pair of equations can be solved in the same way...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    In my post #7 I did wrong computation of so that now I try to repair...

    Is 2773=59 x 47 and ...





    ... so that the equation pair to be solved is...



    (1)

    Applying the procedure described in #9 we obtain...







    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 11:07 PM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 01:37 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 28th 2010, 05:08 AM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 03:17 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum