What to do if the Extended Euclidean Algorithm terminates in one step?

Question

I am trying to solve the linear congruence

$14x \equiv 1 \pmod{113}$.

So I first find $\gcd(14, 113) = 1$. However this means that:

$113 = 14(8) + 1$

There is only one step needed. If I don't have any other equations, how do I find the inverse? Thank you for any help!

Answer 1

Since $(8,113)=1$, we multiplying the equation by 8 and get $$ \begin{aligned} 8(14 x) & \equiv 8(1) \\ 112 x & \equiv 8 \\ -1 x & \equiv 8 \\ x & \equiv-8 \\ & \equiv 105 \quad(\bmod 113) \end{aligned} $$