Range for the coeffients returned by gcdext

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> Computing gcdext means that given two positive integers a, b, we
> compute g = gcd(a,b) and two values u, v such that
> 
>   g = u a + v b
> 
> Now, these are not uniquely determined, which can be seen from
> 
>   g = u a + v b = (u + b) a + (v - a) b
> 
> In fact, u is uniquely defined mod b, and v is defined mod a.

A correction: When g != 1, u is defined mod (b/g), and v is defined
mod (a/g). In the usual case, we can determine u and v uniquely in the
ranges

  -a/g < v < 0 < u < b/g
       ^   ^   ^   ^
       1   2   3   4

(note the strict inequalities). The exceptions are: if a = g, then u =
1, v = 0, violating (2). If b = g, then u = b/g, v = -(a/g - 1),
violating (4). And if a = b = g, then we can choose u = 1, v = 0,
violating (2) and (4), or u = 0, v = 1, violating (1) and (3).

So it seems that in all cases we can make make sure that

  -a/g < v <= 0 < u <= b/g  (*)

(All this assumes that a, b are > 0, if a = 0 exclusive-or b = 0, then
u, v are uniquely determined over the whole of Z, but they don't
satisfy the (*) inequality).

/Niels