So you can reverse mod like this:

I mod J=K

and therefore

I=K+J*X (where X can be any rational number)

which is one of the equations mentionned above.

The algorithm goes like this:

function ExtEuclid(A: Integer; var X: Integer; B: Integer; var Y: Integer): Integer;

{ 1. Start with two nonzero integers A and B, and set

(u,U) = (1,0) and (v,V) = (0,1).

2. Express A = q*B + r, q and r integers with 0 <= r < |B|.

3. If r = 0, output |B|, U, and V, and stop.

4. Replace (A,B) by (B,r), (u,U) by (U,u-q*U), and (v,V) by

(V,v-q*V).

5. Go to Step 2 above.}

var

U,V: array[0..1] of Integer;

Q,I: Integer;

begin

I:=0;

U[0]:=1;

V[0]:=0;

U[1]:=0;

V[1]:=1;

repeat

Result:=B;

Q:=A div B;

B:=A-Q*B;

A:=Result;

I:=1-I;

Dec(U[I xor 1],Q*U[I]);

Dec(V[I xor 1],Q*V[I]);

until B=0;

X:=U[I];

Y:=V[I];

end;

Hope this answers your question.