A useful way to understand the extended Euclidean algorithm is in terms of linear algebra.
(This is somewhat redundant to fgrieu's answer, but I decided to post this anyway, since I started writing this before fgrieu expanded their answer. Hopefully the slightly different perspective may still be useful.)
Let's say we're trying to find the inverse of $e$ modulo $\varphi$, i.e. a number $d$ such that $$de \equiv 1 \pmod \varphi.$$ In other words, given $e$ and $\varphi$, we wish to find an integer solution $(d, k)$ to the linear equation $$de + k\varphi = 1.$$ Of course, we know that this equation is only solvable if $\gcd(e,\varphi) = 1$. More generally, if that's not the case, the best we can hope for is a solution to the generalized equation $$de + k\varphi = r,$$ where $r = \gcd(e,\varphi)$ is the smallest positive integer for which such a solution exists.
As it happens, we already have several trivial solutions to this equation, including $$\begin{aligned}d_0 &= 0,& k_0 &= 1,& r_0 &= \varphi,& \text{and} \\ d_1 &= 1,& k_1 &= 0,& r_1 &= e.\end{aligned}$$
However, as noted above, we're specifically interested in solutions that minimize $r$, which these trivial solutions usually don't. However, we hopefully remember from high school algebra that subtracting both sides of a valid equation from the respective two sides of another valid equation yields yet another valid equation: if $x = y$ and $p = q$, then $x - p = y - q$.
Thus, assuming that $r_0 = \varphi > r_1 = e > 0$, we can obtain another solution with an even smaller (but still non-negative) $r$ by repeatedly subtracting both sides of the equation $d_1e + k_1\varphi = r_1$ from the corresponding sides of $d_0e + k_0\varphi = r_0$ until the resulting solution $$\begin{aligned}d_2 &= d_0-a_1d_1,& k_2 &= k_0-a_1k_1,& r_2 &= r_0-a_1r_1,\end{aligned}$$ where $a_1$ is the number of times we've subtracted the smaller solution from the larger one, satisfies $r_2 < r_1$. In fact, we can even directly calculate the multiplier $a_1 = \left\lfloor\frac{r_0}{r_1}\right\rfloor$ (where $\lfloor x \rfloor$ denotes $x$ rounded down, i.e. the largest integer no greater than $x$) without having to do any actual repeated subtraction.
Now we have a new solution $d_2e + k_2\varphi = r_2$, but the new $r_2$ might still not be minimal. However, it is smaller than $r_1$, so we can repeat the same subtraction trick again to obtain yet another new solution $$\begin{aligned}d_3 &= d_1-a_2d_2,& k_3 &= k_1-a_2k_2,& r_3 &= r_1-a_2r_2,\end{aligned}$$ where $a_2 = \left\lfloor\frac{r_1}{r_2}\right\rfloor$, and so on.
More generally, given the two trivial initial solutions, we can keep constructing new solutions with smaller and smaller $r$ using the recurrence $$\begin{aligned}d_{i+1} &= d_{i-1}-a_i d_i,& k_{i+1} &= k_{i-1}-a_i k_i,& r_{i+1} &= r_{i-1}-a_i r_i,\end{aligned}$$ where $a_i = \left\lfloor\frac{r_{i-1}}{r_i}\right\rfloor$.
We can keep repeating this process until, eventually, we find that $r_i$ evenly divides $r_{i-1}$ (which implies that $r_{i+1}$ would be zero, which we don't want). At that point, if $r_i = 1$, then the corresponding coefficient $d_i$ (reduced modulo $\varphi$) is the modular inverse of $e$ that we wanted.
Otherwise, it's not hard to show that $r_i$ in fact evenly divides all $r_j$ for $0 \le j < i$, including $r_0 = \varphi$ and $r_1 = e$, and is thus a nontrivial common divisor (in fact, the greatest common divisor) of $e$ and $\varphi$. In particular, this implies that $e$ is not invertible modulo $\varphi$.
Ps. As fgrieu notes in their answer, it's not actually necessary to keep track of the $k_i$ coefficients if we're only interested in $d$ (and $r$). Thus, an implementation of this algorithm only needs to store $r_i$, $d_i$, $r_{i-1}$, $d_{i-1}$ and the temporary value $a_i$. (Some other temporary values may also be needed in practice, although it should be noted that $r_{i+1}$ and $d_{i+1}$ do not need to be stored separately in general, since they can immediately overwrite $r_{i-1}$ and $d_{i-1}$.)
Here's a simple implementation in Python (which, conveniently, has arbitrary-precision integers built in):
def modinv(e, phi):
d_old = 0; r_old = phi
d_new = 1; r_new = e
while r_new > 0:
a = r_old // r_new
(d_old, d_new) = (d_new, d_old - a * d_new)
(r_old, r_new) = (r_new, r_old - a * r_new)
return d_old % phi if r_old == 1 else None
Try it online!
