Range for the coeffients returned by gcdext
Niels Möller
nisse at lysator.liu.se
Fri Sep 19 09:11:37 CEST 2003
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
More information about the gmp-devel
mailing list