Division modulo a prime in modular arithmetic
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}$.