# 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
```