Results 1 to 3 of 3

Math Help - How can I work this out?

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    47

    How can I work this out?

    Hello,
    Using a calculator,I know that the solution to d = 55^{-1} \ (mod \ 10752) is d = 391.

    Can someone please show me how to prove this by hand using Euclid's Algorithm? Any help would be greatly appreciated.
    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jimmy_W View Post
    Hello,
    Using a calculator,I know that the solution to d = 55^{-1} \ (mod \ 10752) is d = 391.

    Can someone please show me how to prove this by hand using Euclid's Algorithm? Any help would be greatly appreciated.
    Thanks
    You don't need Euclid's algorithm just observe that:

     <br />
55\times 391=21505=2 \times 10752 +1= 1 \mod (10752)<br />

    Or do you mean: Find 55^{-1} \mod(10752) (which you know is 391 by looking in the back of the book)

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,201
    Thanks
    1789
    Captain Black, he said that he knew that "using a calculator" and asked how you would find it "by hand".

    Jimmy W, if d= 55^{-1} (mod 10752) then 55d= 10752k+ 1 for some integer k. That is the same as 55d- 10752k= 1 so, using Euclid's algorithm:
    55 divides into 10752 195 times with remainder 27. 27 divides into 55 twice with remainder 1. That is: 55 -2(27)= 1 and, since 10752- 195(55), that is 55- 2(10752- 195(55))= (1+ 2(195))(55)- 2(10752)= 391(55)- 2(10752)= 1. That means that one solution is d= 391, k= 2.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Work--please check my work for me
    Posted in the Calculus Forum
    Replies: 3
    Last Post: February 1st 2011, 10:02 AM
  2. Replies: 1
    Last Post: July 21st 2010, 07:02 PM
  3. Replies: 1
    Last Post: December 4th 2007, 04:45 PM
  4. help with work
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 4th 2007, 11:36 AM
  5. work
    Posted in the Calculus Forum
    Replies: 0
    Last Post: May 20th 2007, 02:38 PM

Search Tags


/mathhelpforum @mathhelpforum