Thue's lemma

In modular arithmetic, Thue's lemma roughly states that every modular integer may be represented by a "modular fraction" such the numerator and the denominator have absolute values not greater than the square root of the modulus.

More precisely for every pair of integer $(a, m)$ with $m > 1$ , given two positive integers $X$ and $Y$ such that $X \leq m < XY$ , there are two integers $x$ and $y$ such that

ay\equiv x{\pmod {m}}

and

|x|<X,\quad 0<y<Y.

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² + 1 = 0 mod p. (Such an "a" is guaranteed for "p" by Wilson's Theorem.^[5])

Uniqueness

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

2a+1\equiv -a+2\equiv 0{\pmod {5}}

However, for $X$ and $Y$ small enough, if a solution exists, it is unique. More precisely, with above notation, if

2XY<m,

and

ay_{1}-x_{1}\equiv ay_{2}-x_{2}\equiv 0{\pmod {m}}

with

\left|x_{1}\right|<X,\quad \left|y_{1}\right|<Y,

and

\left|x_{2}\right|<X,\quad \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.^[6]

The proof is rather easy: by multiplying each congruence by the other $y i$ and subtracting, one gets

y_{2}x_{1}-y_{1}x_{2}\equiv 0{\pmod {m}}.

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 $y_{2}x_{1}-y_{1}x_{2}=0$ , and thus 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.^[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

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

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$ .

References

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.
↑ Löndahl, Carl (2011-03-22). "Lecture on sums of squares" (PDF). Retrieved 26 February 2016.
↑ Ore, Oystein (1948), Number Theory and its History, pp. 262–263
↑ Shoup, section 4.6
↑ Shoup, section 4.5

This article is issued from Wikipedia - version of the 9/9/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Thue's lemma

Uniqueness

Computing solutions

See also

References