modular arithmetic - Use Euclid's Algorithm to find the multiplicative inverse

Use Euclid's Algorithm to find the multiplicative inverse of $13$ in $\mathbf{Z}_{35}$

Can someone talk me through the steps how to do this? I am really lost on this one.

Thanks

Answer

Hint: $13$ and $35$ are relatively prime. Use the extended Euclidean algorithm to find the integers $x$ and $y$ such that:

$$13x + 35y = 1$$

From here, simply mod out by $35$:

$$13x \equiv 1 \pmod{35}$$