Euclid's algorithm to solve (e x d) mod p = 1

Question

I need to use Euclid's algorithm to find d in the following equation. Given values for e and p

$$(e\times d)\mod p = 1$$

I have used Euclid's algorithm to find the gcd of two numbers but can't see how to apply it to the above.

Answer 1

Hint: The Euclid algorithm not only allows to find the gcd of two numbers, it also allows to find $u$ and $v$ such that if $(a,b)=1$ one has $ua+vb=1$. Now we have $(e,p)=1$ because $p$ is prime and $e$ should not be a multiple of $p$ otherwise $\forall g\in\Bbb{Z},\,e\times g\equiv 0\pmod{p}$. So use the Euclid algorithm to find $u$ and $v$ such that $ue+vp=1$. And this is rewriten $\pmod{p}$ as $u\times e\equiv 1$ and therefore $d\equiv u\pmod{p}$