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 a^2 + 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${\displaystyle 0<Y\leq m<XY}$,il existe des entiers x et y tels que${\displaystyle ax\equiv y{\pmod {m}},\quad 1\leq x<X\quad {\text{et}}\quad |y|<Y.}$

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 ${\displaystyle 1<X<m}$, il existe des entiers x et y tels que ${\displaystyle ax\equiv y{\pmod {m}},\quad 1\leq x<X\quad {\text{et}}\quad |y|\leq m/X}$[6]. Cette variante se déduit de l'énoncé ci-dessus, appliqué à un réel ${\displaystyle Y>m/X}$ suffisamment proche de ${\displaystyle m/X}$.

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 = a^2 + 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 ${\displaystyle x,y}$ par s inconnues ${\displaystyle x_{1},\dots ,x_{s}}$ et la congruence linéaire ${\displaystyle ax\equiv y{\pmod {m}}}$ par le système homogène de r congruences associé à une matrice ${\displaystyle A=(a_{i,j})}$ à coefficients entiers à r lignes et s colonnes :

Si ${\displaystyle r<s}$ alors, pour tous réels positifs ${\displaystyle \lambda _{1},\dots ,\lambda _{s}}$ tels que ${\displaystyle \lambda _{1}\dots \lambda _{s}>m^{r}}$, il existe des entiers ${\displaystyle x_{1},\dots ,x_{s}}$ tels que ${\displaystyle \sum _{j=1}^{s}a_{i,j}x_{j}\equiv 0{\pmod {m}}\quad (i=1,\dots ,r),\quad |x_{j}|<\lambda _{j}\quad (j=1,\dots ,s)\quad {\text{et}}\quad (x_{1},\dots ,x_{s})\neq (0,\dots ,0)}$[9].

Démonstrations

• Preuve du théorème de Brauer et Reynolds.
  Notons ${\displaystyle \mu _{j}}$ le plus grand entier strictement inférieur à ${\displaystyle \lambda _{j}}$, c'est-à-dire que ${\displaystyle 1+\mu _{j}}$ est la partie entière par excès de ${\displaystyle \lambda _{j}}$. On a donc${\displaystyle 0\leq \mu _{j}<\lambda _{j}\leq 1+\mu _{j}.}$Le nombre ${\displaystyle l}$ des s-uplets ${\displaystyle x=(x_{1},\dots ,x_{s})}$ d'entiers tels que ${\displaystyle 0\leq x_{j}\leq \mu _{j}\quad (j=1,\dots ,s)}$ vérifie :${\displaystyle l=\prod _{j=1}^{s}(1+\mu _{j})\geq \prod _{j=1}^{s}\lambda _{j}>m^{r}.}$Il est donc strictement supérieur au nombre des valeurs possibles des r-uplets images, dans ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{r}}$, par ${\displaystyle x\mapsto Ax}$. 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 ${\displaystyle x}$ annoncée.
• Preuve du lemme de Thue.
  Appliquons le théorème de Brauer et Reynolds au cas particulier ${\displaystyle s=2,r=1,A=(a,-1)}$, en notant ${\displaystyle (x,y)}$ l'inconnue ${\displaystyle (x_{1},x_{2})}$ et ${\displaystyle (X,Y)}$ son majorant ${\displaystyle (\lambda _{1},\lambda _{2})}$. Les hypothèses ${\displaystyle Y>0}$ et ${\displaystyle XY>m}$ (donc ${\displaystyle X>0}$) assurent l'existence d'un couple d'entiers ${\displaystyle (x,y)\neq (0,0)}$ tel que ${\displaystyle ax\equiv y{\pmod {m}}}$, ${\displaystyle |x|<X}$ et ${\displaystyle |y|<Y}$. Puisque de plus ${\displaystyle Y\leq m}$, on a ${\displaystyle |y|<m}$ donc ${\displaystyle x}$ n'est pas nul (sinon, ${\displaystyle y}$ le serait aussi, puisqu'il serait congru à ${\displaystyle 0}$ mod ${\displaystyle m}$). Enfin, quitte à remplacer si nécessaire ${\displaystyle (x,y)}$ par son opposé, ${\displaystyle x}$ 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 ${\displaystyle -1\equiv a^{2}{\pmod {m}}}$ alors il existe des entiers ${\displaystyle u,v>0}$ premiers entre eux tels que ${\displaystyle au\equiv v{\pmod {m}}}$ et ${\displaystyle m=u^{2}+v^{2}}$.

Démonstration

En appliquant le lemme de Thue à ${\displaystyle X=Y={\sqrt {m+1}}}$ puis en choisissant ${\displaystyle (u,v)=(x,y)}$ ou ${\displaystyle (-y,x)}$ (selon le signe de ${\displaystyle y}$), on obtient ${\displaystyle 1\leq u,v\leq {\sqrt {m}}}$ et ${\displaystyle au\equiv v{\pmod {m}}}$.

On remarque alors que ${\displaystyle u}$ ou ${\displaystyle v}$ est strictement inférieur à ${\displaystyle {\sqrt {m}}}$, même si ${\displaystyle m}$ est un carré. En effet, si ${\displaystyle a^{2}\equiv -1{\pmod {n^{2}}}}$ pour un entier ${\displaystyle n>1}$ (nécessairement impair), on montre facilement que ${\displaystyle an\not \equiv n{\pmod {n^{2}}}}$.

On en déduit que ${\displaystyle u^{2}+v^{2}=m}$ (puisque ${\displaystyle 0<u^{2}+v^{2}<2m}$ et ${\displaystyle u^{2}+v^{2}\equiv 0{\pmod {m}}}$).

Enfin, ${\displaystyle u}$ et ${\displaystyle v}$ sont premiers entre eux car si ${\displaystyle d}$ divise ${\displaystyle u}$ et ${\displaystyle v}$ alors ${\displaystyle md\mid (a^{2}+1)u^{2}+(v-au)(v+au)=u^{2}+v^{2}=m}$ donc ${\displaystyle d\mid 1}$.

Réciproquement, si ${\displaystyle m=u^{2}+v^{2}}$ avec ${\displaystyle u}$ et ${\displaystyle v}$ premiers entre eux (donc premiers avec m) alors –1 est le carré modulo m de l'entier ${\displaystyle a}$ défini modulo m par ${\displaystyle au\equiv v{\pmod {m}}}$.

Références

1. En 1917 ou 1902 :
   • (no) A. Thue, « Et bevis for at lignigen A^3 + B^3 = С^3 er remulig i hele fra nul forsk jellige tal A, B og С », Archiv. for Math. og Naturvid, vol. 34, n^o 15, 1917, selon (en) Alfred Brauer et R. L. Reynolds, « On a theorem of Aubry-Thue », Canad. J. Math., vol. 3,‎ 1951, p. 367-374 (DOI 10.4153/CJM-1951-042-6) et (en) William J. LeVeque, Fundamentals of Number Theory, Dover, 2014 (1^re éd. 1977) (lire en ligne), p. 180 ;
   • (no) A. Thue, « Et par antydninger til en taltheoretisk metode », Kra. Vidensk. Selsk. Forh., vol. 7,‎ 1902, p. 57-75, selon (en) Pete L. Clark, « Thue's Lemma and Binary Forms », 2010.
2. (en) Carl Löndahl, « Lecture on sums of squares », 2011.
3. LeVeque 2014, p. 182, aperçu sur Google Livres.
4. (en) Victor Shoup, A Computational Introduction to Number Theory and Algebra, CUP, 2005 (lire en ligne), p. 43, theorem 2.33.
5. Shoup 2005, p. 43, theorem 2.34.
6. Dans la version de LeVeque 2014, p. 180 de ce lemme, l'hypothèse pourtant indispensable ${\displaystyle X>1}$ est remplacée par ${\displaystyle X>0}$, et l'hypothèse additionnelle ${\displaystyle a\not \equiv 0{\pmod {m}}}$ de LeVeque ne suffit pas à garantir la condition supplémentaire ${\displaystyle y\neq 0}$ qu'il énonce dans sa conclusion.
7. Shoup 2005, p. 90.
8. Brauer et Reynolds 1951, transcrit dans LeVeque 2014, p. 179, aperçu sur Google Livres.
9. Si l'on suppose de plus ${\displaystyle \lambda _{i}\leq m}$, on a donc même ${\displaystyle (x_{1},\dots ,x_{s})\not \equiv (0,\dots ,0){\pmod {m}}.}$

Articles connexes

• Lemme de Siegel
• Théorème de Minkowski