Thue's lemma

Template:Short description Template:About 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 Template:Math with Template:Math, given two positive integers Template:Math and Template:Math such that Template:Math, there are two integers Template:Mvar and Template:Mvar such that

$ay\equiv x(\mathrm{mod}m)$

and

$|x|<X,0<y<Y.$

Usually, one takes Template:Math and Template:Math equal to the smallest integer greater than the square root of Template:Math, but the general form is sometimes useful, and makes the uniqueness theorem (below) easier to state.

The first known proof is attributed to Template:Harvs 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 a² + 1 ≡ 0 mod p. (Such an "a" is guaranteed for "p" by Wilson's theorem.)

Uniqueness

In general, the solution whose existence is asserted by Thue's lemma is not unique. For example, when Template:Math there are usually several solutions Template:Math, provided that Template:Math and Template:Math are not too small. Therefore, one may only hope for uniqueness for the rational number Template:Math, to which Template:Mvar is congruent modulo Template:Mvar if y and m are coprime. Nevertheless, this rational number need not be unique; for example, if Template:Math, Template:Math and Template:Math, one has the two solutions

$2a+1\equiv -a+2\equiv 0(\mathrm{mod}5)$.

However, for Template:Math and Template:Math small enough, if a solution exists, it is unique. More precisely, with above notation, if

$2XY<m,$

and

$a{y}_1-x_1\equiv a{y}_2-x_2\equiv 0(\mathrm{mod}m)$,

with

$\left|x_1\right|<X,\left|y_1\right|<Y,$

and

$\left|x_2\right|<X,\left|y_2\right|<Y,$

then

$\frac{x_1}{y_1}=\frac{x_2}{y_2}.$

This result is the basis for rational reconstruction, which allows using modular arithmetic for computing rational numbers for which one knows bounds for numerators and denominators.Template:Sfn

The proof is rather easy: by multiplying each congruence by the other Template:Math and subtracting, one gets

$y_2{x}_1-y_1{x}_2\equiv 0(\mathrm{mod}m).$

The hypotheses imply that each term has an absolute value lower than Template:Math, and thus that the absolute value of their difference is lower than Template:Mvar. This implies that $y_2{x}_1-y_1{x}_2=0$, hence the result.

Computing solutions

The original proof of Thue's lemma is not efficient, in the sense that it does not provide any fast method for computing the solution. The extended Euclidean algorithm, allows us to provide a proof that leads to an efficient algorithm that has the same computational complexity of the Euclidean algorithm.Template:Sfn

More precisely, given the two integers Template:Mvar and Template:Mvar appearing in Thue's lemma, the extended Euclidean algorithm computes three sequences of integers Template:Math, Template:Math and Template:Math such that

$t_{i}m+y_{i}a=x_i\text{for }i=0,1,...,$

where the Template:Math are non-negative and strictly decreasing. The desired solution is, up to the sign, the first pair Template:Math such that Template:Math.

See also

• Padé approximant, a similar theory, for approximating Taylor series by rational functions