Division modulo a prime in modular arithmetic

I am looking for a way to implement division in modular arithmetic using modulo prime.

The method I found in math books is to try $u$ such that

$au \equiv 1 \pmod{p}$

$b/a \equiv bu \pmod{p}$

where $a, b, u \in Z_p$ (remainder class modulo a prime $p$). But trying things is probably not a good and fast approach (as it seems to me it has linear complexity and my $p$ can be big, up to $10^9$). What is the right way to do division in modulo prime?

To divide $b$ by $a$, you follow two steps: first you find $u$ such that $au \equiv 1 \pmod{p}$, and then you compute $bu \pmod{p}$. To find $u$, you run the extended GCD algorithm on $a$ and $p$. If it is indeed the case that $a \not\equiv 0 \pmod{p}$, then since $p$ is prime $(a,p) = 1$. So the GCD algorithm will come up with numbers $u,v$ such that $$ au + pv = 1. $$ In other words, $au \equiv 1 \pmod{p}$.

StackExchange Computer Science Q#10552, answer score: 10