Hey all,

I've been trying to figure out for a whole evening what was wrong in the code I wrote to apply the extended euclidean algorithm on two coprime numbers in order to obtain the multiplicative inverse of $\displaystyle a$ modulo $\displaystyle b$. This is what I get (this is delphi, longword is the basic unsigned 32-bit integer) :

Code:

function ModularInverse(a, b: Longword): Longword;
Var
X, Y, lastX, lastY, temp, quotient: Longword;
begin
X := 0;
Y := 1;
Lastx := 1;
Lasty := 0;
while b <> 0 do
begin
Quotient := A div B;
Temp := B;
B := A mod B;
A := Temp;
Temp := X;
X := Lastx - quotient * X;
Lastx := temp;
temp := y;
y := lasty - quotient * y;
lasty := temp;
end;
Result := X;
end;

But this code keeps failing on even basic inputs like the inverse of 15 modulo 19 ! The answer should be 14 but it just keeps answering either 4, either 10 or sometimes 19 or 0. What the hell is wrong with this ? This is really melting my brain down. I really feel like my computer can't add two numbers right ...

Thanks all