Extended Euclidean Algorithm in RSA 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.
First, 40 = 3*13 + 1

So, we have found 1 in the first step.
Then I can write 1 as following:

1 = 40 - 3*13 and this is equivalent to

1 = 40 - 13*3. 40 is equivalent to 0 mod40.

1 = -13*3. Here we get the inverse of 3 as -13 which is equivalent to 27.