[GAP Forum] Thue's Lemma

[Juergen Mueller]

Dear Sergey, dear Frank,

just a short additional comment on this:

Actually, I did not know either that this Lemma has a name attached to it,
in my eyes it was part of mathematical folklore.

Anyway, the standard algorithmic solution (which is the one Frank has
implemented, as far as I see) is also known as Gauss's algorithm finding
a shortest vector in a lattice of rank 2 in Euclidean space (applied to the
lattice spanned by [n,0] and [x,1]). As such, it as a variant of the
Euclidean algorithm in Z, and a predecessor of the LLL algorithm.

And indeed, as it is essentially the Euclidean algorithm running,
this works efficiently for HUGE numbers, as you have observed.
For more details, see for example Algorithm 1.3.14 in Cohen's book
`A course in computational algebraic number theory'.

Best wishes, Jürgen (Müller)