# 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. – kelalaka 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