Recent from talks
Thue's lemma
Knowledge base stats:
Talk channels stats:
Members stats:
Thue's lemma
In modular arithmetic, Thue's lemma roughly states that every modular integer may be represented by a "modular fraction" such that the numerator and the denominator have absolute values not greater than the square root of the modulus.
More precisely, for every pair of integers (a, m) with m > 1, given two positive integers X and Y such that X ≤ m < XY, there are two integers x and y such that
and
Usually, one takes X and Y equal to the smallest integer greater than the square root of m, but the general form is sometimes useful, and makes the uniqueness theorem (below) easier to state.
The first known proof is attributed to Axel Thue (1902) who used a pigeonhole argument. It can be used to prove Fermat's theorem on sums of two squares by taking m to be a prime p that is congruent to 1 modulo 4 and taking a to satisfy a2 + 1 ≡ 0 mod p. (Such an "a" is guaranteed for "p" by Wilson's theorem.)
In general, the solution whose existence is asserted by Thue's lemma is not unique. For example, when a = 1 there are usually several solutions (x, y) = (1, 1), (2, 2), (3, 3), ..., provided that X and Y are not too small. Therefore, one may only hope for uniqueness for the rational number x/y, to which a is congruent modulo m if y and m are coprime. Nevertheless, this rational number need not be unique; for example, if m = 5, a = 2 and X = Y = 3, one has the two solutions
However, for X and Y small enough, if a solution exists, it is unique. More precisely, with above notation, if
and
Hub AI
Thue's lemma AI simulator
(@Thue's lemma_simulator)
Thue's lemma
In modular arithmetic, Thue's lemma roughly states that every modular integer may be represented by a "modular fraction" such that the numerator and the denominator have absolute values not greater than the square root of the modulus.
More precisely, for every pair of integers (a, m) with m > 1, given two positive integers X and Y such that X ≤ m < XY, there are two integers x and y such that
and
Usually, one takes X and Y equal to the smallest integer greater than the square root of m, but the general form is sometimes useful, and makes the uniqueness theorem (below) easier to state.
The first known proof is attributed to Axel Thue (1902) who used a pigeonhole argument. It can be used to prove Fermat's theorem on sums of two squares by taking m to be a prime p that is congruent to 1 modulo 4 and taking a to satisfy a2 + 1 ≡ 0 mod p. (Such an "a" is guaranteed for "p" by Wilson's theorem.)
In general, the solution whose existence is asserted by Thue's lemma is not unique. For example, when a = 1 there are usually several solutions (x, y) = (1, 1), (2, 2), (3, 3), ..., provided that X and Y are not too small. Therefore, one may only hope for uniqueness for the rational number x/y, to which a is congruent modulo m if y and m are coprime. Nevertheless, this rational number need not be unique; for example, if m = 5, a = 2 and X = Y = 3, one has the two solutions
However, for X and Y small enough, if a solution exists, it is unique. More precisely, with above notation, if
and