Range for the coeffients returned by gcdext

[Niels Möller]

Kevin Ryde <user42 at zip.com.au> writes:

> But I expect once one has u,v roughly in the vicinity of a,b then
> any sensible rule can be applied with not much work, certainly not
> much compared to getting there in the first place.

Right, when you have computed g and a random pair u, v such that

  g = u a + v b

what you can do is to compute

  a' = a/g, b' = b/g
  q = floor ( (u-1) /b'),
  u' = u - q b' = (u - 1) mod b' + 1
  v' = v + q a'

Then you get 0 < u' <= b' and a corresponding v' such that

  g = u'a + v'b

So it's two divisions by (the often small) value g, one divmod and one
multiplication. If you only want u', then you don't need the quotient
and the multiplication. And if we're satisfied with a non-unique u' in
the range 0 < u' <= b, the divisions by g can be skipped as well, and
it boils down to only

  u' = (u - 1) mod b + 1  or
  u' = u mod b            if we prefer 0 <= u' < b

Regards,
/Niels