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 0 < Y ≤ m < X Y {\displaystyle 0<Y\leq m<XY} ,il existe des entiers x et y tels que a x ≡ y ( mod m ) , 1 ≤ x < X et | y | < Y . {\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 1 < X < m {\displaystyle 1<X<m} , il existe des entiers x et y tels que a x ≡ y ( mod m ) , 1 ≤ x < X et | y | ≤ m / X {\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 Y > m / X {\displaystyle Y>m/X} suffisamment proche de m / X {\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 = 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 x , y {\displaystyle x,y} par s inconnues x 1 , … , x s {\displaystyle x_{1},\dots ,x_{s}} et la congruence linéaire a x ≡ y ( mod m ) {\displaystyle ax\equiv y{\pmod {m}}} par le système homogène de r congruences associé à une matrice A = ( a i , j ) {\displaystyle A=(a_{i,j})} à coefficients entiers à r lignes et s colonnes :

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

Démonstration

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

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

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

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

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

Références

  1. ↑ 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 », .
  2. ↑ (en) Carl Löndahl, « Lecture on sums of squares », .
  3. ↑ a b et c LeVeque 2014, p. 182, aperçu sur Google Livres.
  4. ↑ (en) Victor Shoup, A Computational Introduction to Number Theory and Algebra, CUP, (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 X > 1 {\displaystyle X>1} est remplacée par X > 0 {\displaystyle X>0} , et l'hypothèse additionnelle a ≢ 0 ( mod m ) {\displaystyle a\not \equiv 0{\pmod {m}}} de LeVeque ne suffit pas à garantir la condition supplémentaire y ≠ 0 {\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 λ i ≤ m {\displaystyle \lambda _{i}\leq m} , on a donc même ( x 1 , … , x s ) ≢ ( 0 , … , 0 ) ( mod m ) . {\displaystyle (x_{1},\dots ,x_{s})\not \equiv (0,\dots ,0){\pmod {m}}.}

Articles connexes

  • icône décorative Arithmétique et théorie des nombres