23 Jun
2009
23 Jun
'09
1:55 p.m.
*switching back to English*
Both are correct. The documentation for gmp_gcdext does not define the "correct" answer uniquely. It computes g, s and t such that
g = gcd(a,b) = s a + t b
and |s| <= |b| and |t| <= |a|
If you, for example, want s to never be nonegative, you can do something like
if (s < 0) { s += b; t -= a }
(and then there are some additional borderline cases when you can have s = b or s = 0).