RSA Encryption Problem: Finding d Using Euclidean Algorithm

[muso07]

Homework Statement

This is a problem my lecturer did in class but I'm a bit confused.

We have 2 large primes p=137 and q=131, choose e = 3
n = pq = 137.131 = 17947
(p-1)(q-1) = 136.130 = 17680

Compute d = e^-1 mod (p-1)(q-1) = 3^-1 mod 17680 = 11787.

This is where I'm confused. How did he get d=11787?

Homework Equations

The Attempt at a Solution

I think I'm supposed to use the Euclidean algorithm to find d, but he didn't show how.

 

[JCVD]

for d to be the multiplicative inverse of 3 mod 17680 you need 3*d = 1 mod 17680; there will be a unique positive d < 17680 for which this is true, and this d can be found using the extended euclidean algorithm. the following page will be helpful:
http://www-math.cudenver.edu/~wcherowi/courses/m5410/exeucalg.html

for your problem you will start
17680 = 5893(3) + 1
and the euclidean algorithm terminates quickly because
3 = 3(1) + 0
rearranging the line above you get
1 = 17680 - 5893(3)
so you know that d = -5893, which is 11787 mod 17680.

 

[squidsoft]

Lindsay Childs in "A Concrete Introduction to Higher Algebra" deals with RSA details if you need more information.