Question: I know the answer is $x = 499 + 625\, z$ where $z$ is an integer, from [this source](http://www.wolframalpha.com/input/?i=124x%20%3D%201%20%28mod%20625%29). 

I also know that you use the Extended Euclidean algorithm

Answer: 
Another option is
\begin{align}
124 \, x &= 1 \pmod {625} \iff \\
124 \, x &= 625 \, q + 1 \quad (q \in \mathbb{Z}) \iff \\
124 \, x - 625 \, q &= 1 \quad (q \in \mathbb{Z}) \iff \\
124 \, x + 625 \, y &= 1 \quad (\*)
\end{align}
where $(\*)$ is a linear Diophantine equation in integer $x, y$.

The solution algorithm involves the extended Euclidean algorithm.

For the coefficients $a = 124, b = 625$ we get $g = \gcd(a,b) = \gcd(124, 625) = 1$ so we do not have to rescale and $g$ divides $c = 1$, so we have solutions.

The solutions of the homogeneous equation to $(\*)$ 
$$
124 \, x + 625 \,y = 0
$$
are 
$$
(x\_h, y\_h) = (625 \, t, -124 \, t) \quad (t \in \mathbb{Z})
$$

A particular solution of $(\*)$ is found using the extended Euclidean algorithm which gives ([link](https://www.wolframalpha.com/input/?i=egcd%28124,625%29))
$$
(x\_p, y\_p) = (-126, 25)
$$
All solutions are found by adding a particular solution to the homogenous solutions:
$$4
(x, y) = (625\, t - 126, -124\, t + 25)
$$
The first component is
$$
x = 625 \,t - 126 = 625 \, (t - 1) + 625 - 126 = 625 \, t' + 499
$$
We wish to solve the congruence $124x \equiv 1 \pmod{625}$, which means we must solve for the multiplicative inverse of $124 \pmod{625}$. 

Since $\gcd(124, 625) = 1$, $124$ has a multiplicative inverse modulo $625$. To find the inverse, we use the extended Euclidean algorithm.
\begin{align\*}
625 & = 5 \cdot 124 + 5\\
124 & = 24 \cdot 5 + 4\\
5 & = 1 \cdot 4 + 1\\
4 & = 4 \cdot 1
\end{align\*}
Now, we work backwards to write $1$ as a linear combination of $124$ and $625$.
\begin{align\*}
1 & = 5 - 4\\
 & = 5 - (124 - 24 \cdot 5)\\
 & = 25 \cdot 5 - 124\\
 & = 25(625 - 5 \cdot 124) - 124\\
 & = 25 \cdot 625 - 126 \cdot 124
\end{align\*}
Hence, $-126 \cdot 124 \equiv 1 \pmod{625}$. Thus, $x \equiv 124^{-1} \equiv -126 \equiv 499 \pmod{625}$.