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?
The Attempt at a Solution
I think I'm supposed to use the Euclidean algorithm to find d, but he didn't show how.