En aritmética modular , el lema de Thue establece aproximadamente que cada entero modular puede ser representado por una "fracción modular" de manera 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 enteros ( a , m ) con m > 1 , dados dos números enteros positivos X y de Y tal que X ≤ m < XY , hay dos números enteros x e y tales que
y
Por lo general, se toma X e Y iguales al número 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 (abajo) 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] [4] Se puede usar 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 2 + 1 = 0 mod p . (Tal " a " está garantizada para " p " por el teorema de Wilson . [5] )
Unicidad
En general, la solución cuya existencia afirma el lema de Thue no es única. Por ejemplo, cuando a = 1 suele haber 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 la unicidad del número racional X/y, A la que una es congruentes módulo m si y y m son primos entre sí . Sin embargo, este número racional no tiene por qué ser único; por ejemplo, si m = 5 , a = 2 y X = Y = 3 , uno tiene las dos soluciones
- .
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
y
- ,
con
y
luego
Este resultado es la base para la reconstrucción racional , que permite utilizar aritmética modular para calcular números racionales para los que se conocen límites para numeradores y denominadores. [6]
La demostración es bastante fácil: multiplicando cada congruencia por la otra y i y restando, se obtiene
Las hipótesis implican que cada término tiene un valor absoluto menor que XY < metro/2, y por lo tanto, el valor absoluto de su diferencia es menor que m . Esto implica que, de ahí el resultado.
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 del algoritmo euclidiano . [7]
Más precisamente, dados los dos números enteros m y una que aparece en el lema de Thue, el algoritmo de Euclides extendido calcula tres secuencias de números enteros ( t i ) , ( x i ) y ( Y i ) tal que
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 .
Ver también
- Aproximante de Padé , una teoría similar, para aproximar series de Taylor mediante funciones racionales
Referencias
- Shoup, Víctor (2005). Una introducción computacional a la teoría de números y el álgebra (PDF) . Prensa de la Universidad de Cambridge . Consultado el 26 de febrero de 2016 .
- ^ Shoup, teorema 2.33
- ^ Thue, A. (1902), "Et par antydninger til en taltheoretisk metode", Kra. Vidensk. Selsk. Para H. , 7 : 57–75
- ^ Clark, Pete L. "Lema de Thue y formas binarias". CiteSeerX 10.1.1.151.636 . Cite journal requiere
|journal=
( ayuda ) - ^ Löndahl, Carl (22 de marzo de 2011). "Conferencia sobre sumas de cuadrados" (PDF) . Consultado el 26 de febrero de 2016 . Cite journal requiere
|journal=
( ayuda ) - ^ Ore, Oystein (1948), Teoría de números y su historia , págs. 262-263
- ^ Shoup, sección 4.6
- ^ Shoup, sección 4.5