# 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 make the unicity theorem (below) easier to state.^{[1]}

The first known proof is attributed to Axel Thue (1902),^{[2]} who used a pigeonhole argument,^{[3]}^{[4]} it can be used to prove Fermat's theorem on sums of two squares by taking *m* to be a prime *p* that is 1 mod 4 and taking *a* to satisfy *a*^{2} + 1 = 0 mod *p*. (Such an "a" is guaranteed for "p" by Wilson's Theorem.^{[5]})

## Uniqueness[edit]

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), ..., providing that *X* and *Y* are not too small. Therefore, one may only hope unicity for the rational number *x*/*y*, to which a is congruent modulo m if *y* and *m* are coprime. Nevertheless, this rational number needs not to 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

- ,

with

and

then

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.^{[6]}

The proof is rather easy: by multiplying each congruence by the other *y _{i}* and subtracting, one gets

The hypotheses imply that each term has an absolute value lower than *XY* < *m*/2, and thus that the absolute value of their difference is lower than m. This implies that , and thus the result.

## Computing solutions[edit]

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.^{[7]}

More precisely, given the two integers m and a appearing in Thue's lemma, the extended Euclidean algorithm computes three sequences of integers (*t*_{i}), (*x*_{i}) and (*y*_{i}) such that

where the *x*_{i} are non-negative and strictly decreasing. The desired solution is, up to the sign, the first pair (*x*_{i}, *y*_{i}) such that *x*_{i} < *X*.

## See also[edit]

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

## References[edit]

- Shoup, Victor (2005).
*A Computational Introduction to Number Theory and Algebra*(PDF). Cambridge University Press. Retrieved 26 February 2016.

**^**Shoup, theorem 2.33**^**Thue, A. (1902), "Et par antydninger til en taltheoretisk metode",*Kra. Vidensk. Selsk. Forh.*,**7**: 57–75**^**Clark, Pete L. "Thue's Lemma and Binary Forms". Retrieved 25 February 2016. Cite journal requires`|journal=`

(help)**^**Löndahl, Carl (2011-03-22). "Lecture on sums of squares" (PDF). Retrieved 26 February 2016. Cite journal requires`|journal=`

(help)**^**Ore, Oystein (1948),*Number Theory and its History*, pp. 262–263**^**Shoup, section 4.6**^**Shoup, section 4.5