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
$$
$$
124 x \equiv 1 \bmod 625
\implies 124 x \equiv 1 \bmod 125
\implies -1 x \equiv 1 \bmod 125
\implies x \equiv -1 \bmod 125
$$

Write $x= 125y-1$. Then
$$
0 \equiv
124 x-1 = (125-1)(125y-1)-1 \equiv -125y-125=-125(y+1) \bmod 625
$$
This implies $y \equiv -1 \bmod 5$. Write $y=5z-1$. Then
$$
x = 125y-1 = 125(5z-1)-1 = 625z - 126 = 625(z-1)+499
$$