Lema de Thue

Representación de números enteros modulares mediante fracciones “pequeñas”

En aritmética modular , el lema de Thue establece aproximadamente que todo entero modular puede representarse mediante una "fracción modular" tal que el numerador y el denominador tengan valores absolutos no mayores que la raíz cuadrada del módulo.

Más precisamente, para cada par de números enteros ( a , m ) con m > 1 , dados dos números enteros positivos X e Y tales que X ≤ m < XY , hay dos números enteros x e y tales que

${\displaystyle ay\equiv x{\pmod {m}}}$

y

${\displaystyle |x|<X,\quad 0<y<Y.}$

Generalmente, se toma X e Y iguales al entero más pequeño mayor que la raíz cuadrada de m , pero la forma general a veces es útil y hace que el teorema de unicidad (a continuación) sea más fácil de enunciar. ^[1]

La primera prueba conocida se atribuye a Axel Thue  (1902) ^[2], quien utilizó un argumento de casillero . ^[3] Puede utilizarse para demostrar el teorema de Fermat sobre sumas de dos cuadrados tomando m como un primo p que es congruente con 1 módulo 4 y tomando a para satisfacer a ² + 1 ≡ 0 mod p . (Tal " a " está garantizado para " p " por el teorema de Wilson . ^[4] )

Unicidad

En general, la solución cuya existencia afirma el lema de Thue no es única. Por ejemplo, cuando a = 1 , normalmente hay varias soluciones ( x , y ) = (1, 1), (2, 2), (3, 3), ... , siempre que X e Y no sean demasiado pequeñas. Por lo tanto, solo se puede esperar que el número racional sea único .incógnita/y⁠ , con el que a es congruente módulo m si y y m son coprimos . Sin embargo, este número racional no necesita ser único; por ejemplo, si m = 5 , a = 2 y X = Y = 3 , se tienen las dos soluciones

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

Sin embargo, para X e Y lo suficientemente pequeños, si existe una solución, es única. Más precisamente, con la notación anterior, si

${\displaystyle 2XY<m,}$

y

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

con

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

y

${\displaystyle \left|x_{2}\right|<X,\quad \left|y_{2}\right|<Y,}$

entonces

${\displaystyle {\frac {x_{1}}{y_{1}}}={\frac {x_{2}}{y_{2}}}.}$

Este resultado es la base para la reconstrucción racional , que permite utilizar la aritmética modular para calcular números racionales para los que se conocen los límites de los numeradores y denominadores. ^[5]

La prueba es bastante fácil: multiplicando cada congruencia por la otra y _i y restando, se obtiene

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

Las hipótesis implican que cada término tiene un valor absoluto menor que XY < ⁠metro/2⁠ , y por lo tanto que el valor absoluto de su diferencia es menor que m . Esto implica que, de ahí el resultado. ${\displaystyle y_{2}x_{1}-y_{1}x_{2}=0}$

Soluciones informáticas

La prueba original del lema de Thue no es eficiente, en el sentido de que no proporciona ningún método rápido para calcular la solución. El algoritmo euclidiano extendido nos permite proporcionar una prueba que conduce a un algoritmo eficiente que tiene la misma complejidad computacional que el algoritmo euclidiano . ^[6]

Más precisamente, dados los dos números enteros m y a que aparecen en el lema de Thue, el algoritmo euclidiano extendido calcula tres secuencias de números enteros ( t _i ) , ( x _i ) y ( y _i ) tales que

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

donde las x _i son no negativas y estrictamente decrecientes. La solución deseada es, hasta el signo, el primer par ( x _i , y _i ) tal que x _i < X .

Véase también

• Aproximación de Padé , una teoría similar, para aproximar la serie de Taylor mediante funciones racionales

Referencias

1. Shoup, Victor (2005). Introducción computacional a la teoría de números y al álgebra (PDF) . Cambridge University Press . Consultado el 26 de febrero de 2016 .Teorema 2.33.
2. Martes, A. (1902). "Et par antydninger til en taltheoretisk metode". Kra. Vidensk. Selsk. Forh . 7 : 57–75.
3. Aigner, Martin ; Ziegler, Günter M. (2018). Pruebas de EL LIBRO (6.ª ed.). Springer. pág. 21. doi :10.1007/978-3-662-57265-8. ISBN 978-3-662-57265-8.
4. Ore, Oystein (1948). Teoría de números y su historia . págs. 262–263.
5. Shoup 2005, Sección 4.6.
6. Shoup 2005, Sección 4.5.