# Extended Euclidean Algorithm in RSA [duplicate]

I am trying to solve an RSA problem. In order to calculate $$d$$, I have to calculate $$d$$ with $$e=3$$ and $$d\cdot e\equiv1 \pmod{40}$$ Obviously the answer is $$d=27$$, but I want to solve this with the extended Euclidean algorithm.
Though I know how this works, I am stuck because in the first step of the algorithm I get $$40=3\cdot13+1$$

The remainder is 1 and the algorithm stops there. How do I get $$d=27$$ by using the extended Euclidean algorithm?

I dont have a problem solving other similar examples that dont stop in the first step. But here, because it stops in the first step of the algorithm, I get confused.

• Possible duplicate of Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid. If the answer doesn't satisfy you, les us know. Mar 11 '19 at 11:12
• From $40=3\cdot13+1$ you know $e\cdot13+1\equiv0\pmod{40}$. That is $e\cdot13\equiv-1\pmod{40}$. How do you get from that to a value of $d$ with $d\cdot e\equiv1\pmod{40}$? This is fine for manual computation, but notice that a proper Extended Euclidean Algorithm, like HAC algorithm 2.107, or the Half-Extended variant there specifically intended for computation of modular inverses, won't leave you without a solution.
– fgrieu
Mar 11 '19 at 12:07