Results 1 to 2 of 2

Math Help - mod arithmetic

  1. #1
    Member
    Joined
    Jan 2008
    Posts
    114

    mod arithmetic

    This an example in my notes...

    Encipering transformation: f(x) = 9x + 3(mod 100)

    Finding the deciphering transformation:

    Alice now wishes to find a number t such that 9t = 1 mod 100. She finds that 9 x 89 = 1 mod 100. She finds by trial and error (until she improves her arithmetic!) that 9 x 89 = 1 mod 100.

    I was just wondering is there another quicker way that alice can find this t, rather than trial and error?

    Thanks in advance!
    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,

    Quote Originally Posted by hunkydory19 View Post
    This an example in my notes...

    Encipering transformation: f(x) = 9x + 3(mod 100)

    Finding the deciphering transformation:

    Alice now wishes to find a number t such that 9t = 1 mod 100. She finds that 9 x 89 = 1 mod 100. She finds by trial and error (until she improves her arithmetic!) that 9 x 89 = 1 mod 100.

    I was just wondering is there another quicker way that alice can find this t, rather than trial and error?

    Thanks in advance!
    Bézout's identity let us say that if a and b are coprime, there exist u and v such that au+bv=1 -> au=1 mod b.
    We'll find u and v by the Euclidian algorithm

    a=9, b=100

    100=9x11+1
    -> 1=100-9x11 (u=-11 and v=1)

    9x(-11) = 1 mod 100

    -11=89 mod 100

    Hence t=89
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A sum on arithmetic mean...
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 30th 2010, 03:47 AM
  2. Arithmetic Progression or Arithmetic Series Problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 8th 2009, 01:36 AM
  3. arithmetic
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 26th 2009, 11:24 AM
  4. Arithmetic Mean
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 10th 2007, 04:50 PM
  5. Arithmetic Mean
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 8th 2006, 08:01 AM

Search Tags


/mathhelpforum @mathhelpforum