Formula

Start with positive integers a<m. In formulas, Euclid's algorithm looks like the following:

$$\begin{array}{ccccccc\vert c\vert c} &&&&&&&0&1\\ \text{Di... ... &=&q_{n+1} &\cdot &r_n &+& 0 &h_{n+1}&k_{n+1} \\ \end{array}$$

Subscripts are used to indicate the order in which the numbers appear. For instance, q₁, q₂, ..., is the sequence of quotients.

The remainders form a sequence, too, with r_-1=m, r₀=a, r₁, r₂, ..., r_n+1=0. Because the remainder is always less than the divisor, these form a strictly decreasing sequence

$$r_{-1} > r_0 > r_1> r_2>\dots > r_n >0=r_{n+1}$$

The formula for the h's and k's are as follows:
$$\begin{align*}h_{l} & = q_l \, h_{l-1} + h_{l-2} \\ [3pt] k_{l} & = q_l \, k_{l-1} + k_{l-2} \\ [3pt] \end{align*}$$
This is called a two-term recurrence, because to get the next term in the sequence, we have to use the previous two terms.

At every step in Euclid's algorithm we have

$$h_j \,a - k_j\, m = (-1)^j r_j$$

j is a subscript indicating which step we are at. The power (-1)^jis -1 times itself j times; hence, it is +1 if j is even and -1 if j is odd.

Therefore the very last nonzero remainder, which is the smallest, satisfies

$$h_n \,a - k_n\, m = (-1)^n r_n$$

That last nonzero remainder r_n is the greatest common divisor of aand m. If it turns out to be 1, then our equation says

$$h_n a \equiv (-1)^n \pmod m$$

after discarding the multiple of m. That's why the solution to $a\, x \equiv 1 \pmod{m}$ is x= (-1)ⁿ h_n, or h_n if n is even and -h_n if n is odd.