Finding $d$ in RSA Encryption mathematically and by hand

Question

I'm working on this RSA encryption problem and the catch is that it must be done by hand and mathematically.

Let's say $p=11$, $q=13$ $$N=p \cdot q=11 \cdot 13=143$$ I chose $e$ to be relatively prime to $(p-1)(q-1)$, $e=23$ So the public key is $(23,143)$

Now I want to find out $d$ and for that I've come across $2$ different methods. First is using this formula $$23 \cdot d \equiv1 \mod120$$ where I can't seem to work out what $d$ is. I tried to solve it like a quadratic equation $$23x=1 \mod 120$$ $$x=\frac {1}{23}$$ which doesn't make sense. Then I came across this other method to find the value of $d$.

$$∃k : e \cdot d +k(p-1)(q-1) \equiv1$$ $$23 \cdot (47) + (-9)\cdot120=1$$ So the private key would be $(47,143)$ but there is no mention of how they figured out the value of $d$ and $k$. That's why I need some help to work out the value of $d$ in a way so that I can find it given any problem.

Answer 1

Suppose that you know $e$ and $n$, and want to find out $d$ such that $ed \equiv 1 \pmod{n}$ (this is possible if $(n,e) = 1$). An efficient way to do this is to use the extended Euclidean algorithm, which finds two integers $a,b$ such that $an + be = (n,e) = 1$. You can use $d = b \bmod{n}$, since $de \equiv be \equiv 1-an \equiv 1 \pmod{n}$.