Thue's lemma

Last updated October 07, 2022

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.

The first known proof is attributed to AxelThue ( 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 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.^[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), ...$ , provided that $X$ and $Y$ are not too small. Therefore, one may only hope for uniqueness for the rational number $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}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

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$ , 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.^[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$ .

Related Research Articles

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

<span class="mw-page-title-main">Quadratic reciprocity</span> Gives conditions for the solvability of quadratic equations modulo prime numbers

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:

Fermat's little theorem states that if $p$ is a prime number, then for any integer $a$ , the number $a p - a$ is an integer multiple of $p$ . In the notation of modular arithmetic, this is expressed as

In number theory, Euler's theorem states that, if $n$ and $a$ are coprime positive integers, and $is Euler's totient function, then a raised to the power is congruent to 1 modulo n; that is$

<span class="mw-page-title-main">Factorization</span> (Mathematical) decomposition into a product

In mathematics, factorization or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, $3 \times 5$ is a factorization of the integer $15$ , and $(x - 2)(x + 2)$ is a factorization of the polynomial $x 2 - 4$ .

This article collects together a variety of proofs of Fermat's little theorem, which states that

In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,

In modular arithmetic, a number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$ . That is, $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$ , there is some integer $k$ for which $g$ ^$k$ ≡ $a$ . Such a value $k$ is called the index or discrete logarithm of $a$ to the base $g$ modulo $n$ . So $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$ .

In mathematics, p-adic analysis is a branch of number theory that deals with the mathematical analysis of functions of p-adic numbers.

<span class="mw-page-title-main">Cube (algebra)</span> Number raised to the third power

In arithmetic and algebra, the cube of a number $n$ is its third power, that is, the result of multiplying three instances of $n$ together. The cube of a number or any other mathematical expression is denoted by a superscript 3, for example 2³ = 8 or $(x + 1) 3$ .

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number $p$ , then this root can be lifted to a unique root modulo any higher power of $p$ . More generally, if a polynomial factors modulo $p$ into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of $p$ .

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:

In algebraic number theory, the narrow class group of a number field K is a refinement of the class group of K that takes into account some information about embeddings of K into the field of real numbers.

In number theory, the law of quadratic reciprocity, like the Pythagorean theorem, has lent itself to an unusually large number of proofs. Several hundred proofs of the law of quadratic reciprocity have been published.

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer $a$ is an integer $x$ such that the product $ax$ is congruent to 1 with respect to the modulus $m$ . In the standard notation of modular arithmetic this congruence is written as

Pocklington's algorithm is a technique for solving a congruence of the form

In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation $, where and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia.$

Coppersmith's attack describes a class of cryptographic attacks on the public-key cryptosystem RSA based on the Coppersmith method. Particular applications of the Coppersmith method for attacking RSA include cases when the public exponent e is small or when partial knowledge of a prime factor of the secret key is available.

In algebraic number theory Eisenstein's reciprocity law is a reciprocity law that extends the law of quadratic reciprocity and the cubic reciprocity law to residues of higher powers. It is one of the earliest and simplest of the higher reciprocity laws, and is a consequence of several later and stronger reciprocity laws such as the Artin reciprocity law. It was introduced by Eisenstein (1850), though Jacobi had previously announced a similar result for the special cases of 5th, 8th and 12th powers in 1839.

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Shoup, theorem 2.33

[2] Thue, A. (1902), "Et par antydninger til en taltheoretisk metode", Kra. Vidensk. Selsk. Forh., 7: 57–75

[clark-3] Clark, Pete L. "Thue's Lemma and Binary Forms". CiteSeerX 10.1.1.151.636 .{{cite journal}}: Cite journal requires |journal= (help)

[4] Löndahl, Carl (2011-03-22). "Lecture on sums of squares" (PDF). Retrieved 26 February 2016.{{cite journal}}: Cite journal requires |journal= (help)

[5] Ore, Oystein (1948), Number Theory and its History, pp. 262–263

[6] Shoup, section 4.6

[7] Shoup, section 4.5

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Thue's lemma

Contents

Uniqueness

Computing solutions

See also

Related Research Articles

References