[GAP Forum] Thue's Lemma

[Bill Allombert]

On Wed, Jul 27, 2016 at 03:49:39PM +0000, Sergey Shpectorov wrote:
> Hello,
> 
> Does GAP have a function for Thue's Lemma:
> 
> Given integers m>1, X>0, Y>0, such that X<=m<XY, and an integer a, there exist integers 
> x,y such that |x|<X, 0<y<Y, and ay=x mod m.
> 
> or something equivalent?

I could not find it in the documentation either.
This is known under various other name such as "rational reconstruction",
"rational lifting" and "half extended gcd".
This is available in PARI/GP as bestappr.

Cheers,
Bill.