Lemme de Thue
En arithmétique modulaire, le lemme de Thue établit que tout entier modulo m peut être représenté par une « fraction modulaire » dont le numérateur et le dénominateur sont, en valeur absolue, majorés par la racine carrée de m. La première démonstration, attribuée à Axel Thue[1], utilise le principe des tiroirs[2]. Appliqué à un entier m modulo lequel –1 est un carré (en particulier à un nombre premier m congru à 1 modulo 4) et à un entier a tel que a2 + 1 ≡ 0 mod m, ce lemme fournit une expression de m comme somme de deux carrés premiers entre eux[3].
Énoncé
Soient m > 1 et a deux entiers.
Pour tous réels X et Y tels que,il existe des entiers x et y tels que
Shoup démontre cet énoncé dans le cas particulier où X et Y sont entiers[4], puis l'applique à X = Y = 1 + ⌊√m⌋, pour m non carré[5].
LeVeque préfère appliquer la variante suivante à X = √m[3] : pour tout réel X tel que , il existe des entiers x et y tels que [6]. Cette variante se déduit de l'énoncé ci-dessus, appliqué à un réel suffisamment proche de .
- Remarque
- En général, la solution (x, y) dont ce lemme garantit l'existence n'est pas unique et le rationnel x⁄y lui-même ne l'est pas : par exemple, si m = a2 + 1 et X = Y = a + 1 ≥ 2, on a deux solutions (x, y) = (1, a), (a, –1).
- Sous d'autres hypothèses[7] — incompatibles cependant avec celles du lemme de Thue — l'éventuelle solution est unique.
Théorème de Brauer et Reynolds
Le lemme de Thue se généralise[8] en remplaçant les deux inconnues par s inconnues et la congruence linéaire par le système homogène de r congruences associé à une matrice à coefficients entiers à r lignes et s colonnes :
Si alors, pour tous réels positifs tels que , il existe des entiers tels que [9].
- Preuve du théorème de Brauer et Reynolds.
Notons le plus grand entier strictement inférieur à , c'est-à-dire que est la partie entière par excès de . On a doncLe nombre des s-uplets d'entiers tels que vérifie :Il est donc strictement supérieur au nombre des valeurs possibles des r-uplets images, dans , par . Par conséquent (d'après le principe des tiroirs), il existe deux s-uplets distincts ayant même image. Leur différence est la solution annoncée. - Preuve du lemme de Thue.
Appliquons le théorème de Brauer et Reynolds au cas particulier , en notant l'inconnue et son majorant . Les hypothèses et (donc ) assurent l'existence d'un couple d'entiers tel que , et . Puisque de plus , on a donc n'est pas nul (sinon, le serait aussi, puisqu'il serait congru à mod ). Enfin, quitte à remplacer si nécessaire par son opposé, est positif.
Application aux sommes de deux carrés
Le lemme de Thue permet par exemple de démontrer la proposition suivante, utile dans le théorème des deux carrés[3] :
Si alors il existe des entiers premiers entre eux tels que et .
En appliquant le lemme de Thue à puis en choisissant ou (selon le signe de ), on obtient et .
On remarque alors que ou est strictement inférieur à , même si est un carré. En effet, si pour un entier (nécessairement impair), on montre facilement que .
On en déduit que (puisque et ).
Enfin, et sont premiers entre eux car si divise et alors donc .
Réciproquement, si avec et premiers entre eux (donc premiers avec m) alors –1 est le carré modulo m de l'entier défini modulo m par .
Références
- ↑ En 1917 ou 1902 :
- (no) A. Thue, « Et bevis for at lignigen A3 + B3 = С3 er remulig i hele fra nul forsk jellige tal A, B og С », Archiv. for Math. og Naturvid, vol. 34, no 15, 1917, selon (en) Alfred Brauer et R. L. Reynolds, « On a theorem of Aubry-Thue », Canad. J. Math., vol. 3, , p. 367-374 (DOI 10.4153/CJM-1951-042-6) et (en) William J. LeVeque, Fundamentals of Number Theory, Dover, (1re éd. 1977) (lire en ligne), p. 180 ;
- (no) A. Thue, « Et par antydninger til en taltheoretisk metode », Kra. Vidensk. Selsk. Forh., vol. 7, , p. 57-75, selon (en) Pete L. Clark, « Thue's Lemma and Binary Forms », .
- ↑ (en) Carl Löndahl, « Lecture on sums of squares », .
- ↑ a b et c LeVeque 2014, p. 182, aperçu sur Google Livres.
- ↑ (en) Victor Shoup, A Computational Introduction to Number Theory and Algebra, CUP, (lire en ligne), p. 43, theorem 2.33.
- ↑ Shoup 2005, p. 43, theorem 2.34.
- ↑ Dans la version de LeVeque 2014, p. 180 de ce lemme, l'hypothèse pourtant indispensable est remplacée par , et l'hypothèse additionnelle de LeVeque ne suffit pas à garantir la condition supplémentaire qu'il énonce dans sa conclusion.
- ↑ Shoup 2005, p. 90.
- ↑ Brauer et Reynolds 1951, transcrit dans LeVeque 2014, p. 179, aperçu sur Google Livres.
- ↑ Si l'on suppose de plus , on a donc même
Articles connexes
Arithmétique et théorie des nombres