Results 1 to 7 of 7

Thread: 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
    11,152
    Thanks
    731
    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
    $\displaystyle 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:
    $\displaystyle 13 \cdot 17 \equiv 21$ (mod 100)
    $\displaystyle 23 \cdot 17 \equiv 91$ (mod 100)
    $\displaystyle 33 \cdot 17 \equiv 61$ (mod 100)
    $\displaystyle 43 \cdot 17 \equiv 31$ (mod 100)
    $\displaystyle 53 \cdot 17 \equiv 1$ (mod 100)
    $\displaystyle 63 \cdot 17 \equiv 71$ (mod 100)
    $\displaystyle 73 \cdot 17 \equiv 41$ (mod 100)
    $\displaystyle 83 \cdot 17 \equiv 11$ (mod 100)
    $\displaystyle 93 \cdot 17 \equiv 81$ (mod 100)

    So it looks like $\displaystyle 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; Jun 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
    10
    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 $\displaystyle n$ and any integer $\displaystyle m$, we can write $\displaystyle m^{-1}=k$ (modulo $\displaystyle n$)) iff $\displaystyle mk\equiv 1 (\bmod n)$. Exactly what topsquak said. It is the inverse.
    ---
    We want to find $\displaystyle x$ such that:
    $\displaystyle 17x\equiv 1 (\bmod 100)$.
    Since $\displaystyle 100 = 2^2\cdot 5^2$.
    We can simulatenously solve (since $\displaystyle \gcd(2,5)=1$) the congruences:
    $\displaystyle 17x\equiv 1 (\bmod 4)$
    $\displaystyle 17x \equiv 1(\bmod 25)$

    The first one is really simple, add 4 to RHS 4 times to get:
    $\displaystyle 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:
    $\displaystyle 17x\equiv 51 (\bmod 25)\Rightarrow x\equiv 3(\bmod 25)$

    So you are left with,
    $\displaystyle x\equiv 1 (\bmod 4)$
    $\displaystyle 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
    10
    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.
    ---

    $\displaystyle 17x\equiv 1(\bmod 100)$
    By definition it means,
    $\displaystyle 17x - 1 = 100y \mbox{ for some }y\in \mathbb{Z}$.
    Thus,
    $\displaystyle 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 $\displaystyle \gcd(17,100)$.

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

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

    Meaning,
    $\displaystyle 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,
    $\displaystyle -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: Jul 8th 2011, 06:09 PM
  2. Doubt in Number theory
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Feb 16th 2009, 07:22 PM
  3. Replies: 2
    Last Post: Dec 18th 2008, 05:28 PM
  4. number theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 29th 2008, 01:19 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum