Results 1 to 7 of 7

Math Help - number theory doubt

  1. #1
    Newbie
    Joined
    May 2007
    Posts
    15

    number theory doubt

    how can u solve 17^-1 mod 100?

    plz explain the method followed in solving such cases where the exponent is a negative number..


    thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1
    Quote Originally Posted by ramanujam View Post
    how can you solve 17^-1 mod 100?

    please explain the method followed in solving such cases where the exponent is a negative number..


    thanks
    You are looking for a number x such that
    x \cdot 17 \equiv 1 (mod 100)

    Basically we're down to trial and error, but we can make the following observation: since the base is 100 we can simply start looking at numbers that multiply by 7 to end in a 1. So we start with this list:
    3, 13, 23, 33, 43, 53, 63, 73, 83, 93

    We also know that in the integer system x is going to have to be larger than 6 to make 17x > 100, so we can count out the 3. (Small savings, but in other problems it might cut the list down significantly.)

    So let's try them:
    13 \cdot 17 \equiv 21 (mod 100)
    23 \cdot 17 \equiv 91 (mod 100)
    33 \cdot 17 \equiv 61 (mod 100)
    43 \cdot 17 \equiv 31 (mod 100)
    53 \cdot 17 \equiv 1 (mod 100)
    63 \cdot 17 \equiv 71 (mod 100)
    73 \cdot 17 \equiv 41 (mod 100)
    83 \cdot 17 \equiv 11 (mod 100)
    93 \cdot 17 \equiv 81 (mod 100)

    So it looks like 17^{-1} = 53 (mod 100)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2007
    Posts
    15
    thanks dan,
    i find this concept of negative exponent very confusing indeed..
    coz 17^-1 is theoretically equal to (1/17) then how come 17^-1 mod 100 is equal to 53..
    could u plz explain this as well..
    Last edited by ramanujam; June 6th 2007 at 06:48 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by ramanujam View Post
    how can u solve 17^-1 mod 100?

    plz explain the method followed in solving such cases where the exponent is a negative number..
    It means the inverse of a number. Given a positive interger n and any integer m, we can write m^{-1}=k (modulo n)) iff mk\equiv 1 (\bmod n). Exactly what topsquak said. It is the inverse.
    ---
    We want to find x such that:
    17x\equiv 1 (\bmod 100).
    Since 100 = 2^2\cdot 5^2.
    We can simulatenously solve (since \gcd(2,5)=1) the congruences:
    17x\equiv 1 (\bmod 4)
    17x \equiv 1(\bmod 25)

    The first one is really simple, add 4 to RHS 4 times to get:
    17x\equiv 17 (\bmod 4) \Rightarrow x\equiv 1(\bmod 4)

    The second one is also not so bad, add 25 to RHS 2 times to get:
    17x\equiv 51 (\bmod 25)\Rightarrow x\equiv 3(\bmod 25)

    So you are left with,
    x\equiv 1 (\bmod 4)
    x\equiv 3 (\bmod 25)

    You can use the Chinese Remainder Theorem.

    To solve this modulo 100 (which is what you are looking for).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2007
    Posts
    15
    thanks perfect hacker
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2007
    Posts
    15
    this is how i have done,plz tell me if there is anything wrong..

    m trying to solve
    17x = 1 mod 100
    using euclidean algorithm this is wat i get

    100 = 17*5+15----> eqn 1
    17 = 15*1+2---->eqn 2
    15 = 7*2 + 1
    2 = 2*1

    now working bacwards
    1 = 15-(7*2)
    1 = 15 - (17-15*1)*7
    1 = 100-(17*5) - 17*7 + 15*7
    1 = 100 - 17 *12 - 15*7
    1= 100 - 17*12 + (100-17*5)*7
    1 = 100(8) - 17*47
    which is of the form
    100(8)+17(-47)=1
    17* (-47) = 1 mod 100
    since we are looking for a positive no hence x = (-47)+100 = 53
    m not too sure abt the reasoning of my last step..
    plz tell me

    cheers
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by ramanujam View Post
    this is how i have done,plz tell me if there is anything wrong..

    m trying to solve
    17x = 1 mod 100
    using euclidean algorithm this is wat i get

    100 = 17*5+15----> eqn 1
    17 = 15*1+2---->eqn 2
    15 = 7*2 + 1
    2 = 2*1

    now working bacwards
    1 = 15-(7*2)
    1 = 15 - (17-15*1)*7
    1 = 100-(17*5) - 17*7 + 15*7
    1 = 100 - 17 *12 - 15*7
    1= 100 - 17*12 + (100-17*5)*7
    1 = 100(8) - 17*47
    which is of the form
    100(8)+17(-47)=1
    17* (-47) = 1 mod 100
    since we are looking for a positive no hence x = (-47)+100 = 53
    m not too sure abt the reasoning of my last step..
    plz tell me

    cheers
    I see you decided not to do it my way.
    Using the Euclidean algorithm is another good way to do it.

    I just cannot follow what you do!
    Here, what an learn frum die meister to how to present mathematical arguments.
    ---

    17x\equiv 1(\bmod 100)
    By definition it means,
    17x - 1 = 100y \mbox{ for some }y\in \mathbb{Z}.
    Thus,
    17x +100z = 1 \mbox{ where }z=-y.

    Now this is a linear diophatine equation.
    You can use the Euclidean algorithm to solve this.
    First, we need to find \gcd(17,100).

    100 = 5\cdot 17 +15
    17 = 1\cdot 15+2
    15 = 7\cdot 2 +1
    Thus, we see that \gcd(17,100)=1.

    Work backwards,
    15 - 7\cdot 2 = 1
    15 - 7 (17 - 1\cdot 15) = 1
    8\cdot 15 - 7\cdot 17 = 1
    8 (100 - 5\cdot 17) - 7\cdot 17 = 1
    8\cdot 100 -47\cdot 17 =1
    17(-47)+100(8)=1
    Thus, we see that x=-47 works.

    Meaning,
    17(-47)\equiv 1(\bmod 100).

    Now you can add 100 to this number because we are working modulo 100 and it makes no difference to get,
    -47 + 100 \equiv 53 (\bmod 100).

    Thus we get 53.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 06:09 PM
  2. Doubt in Number theory
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 16th 2009, 07:22 PM
  3. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  4. number theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 01:19 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum