In your example, d = -17
(since Bézout's identity says that there exist x
and y
such that x*a + y*b = gcd(a,b)
).
You are looking for a d
such that e*d = 1 mod phi(n)
, so you can convert this negative d
into a positive value that still satisfies the equation by simply adding a multiple of phi(n)
. In this case we just need to add phi(n)
once, which gives your expected value for d
:
-17 + phi(n) = -17 + 40 = 23