How can I work this out?

• March 30th 2009, 05:56 AM
Jimmy_W
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
• March 30th 2009, 06:59 AM
CaptainBlack
Quote:

Originally Posted by Jimmy_W
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:

$
55\times 391=21505=2 \times 10752 +1= 1 \mod (10752)
$

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

CB
• March 30th 2009, 08:08 AM
HallsofIvy
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.