Rozszerzony algorytm euklidesa

// A, B > 0

void euklid(int A, int &x, int B, int &y, int &C){

if(B==0){

x = 1;

y = 0;

C = A;

return;

}

euklid(B, y, A%B, x, C);

y -= (A/B)*x;

}

Cała tajemnica powyższego algorytmu tkwi w równaniu:

(A-[A/B]B)x + B(y+[A/B]x) = C

oraz

A-[A/B]B = A%B dla dodatnich A i B.