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 \equiv 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\leq m<XY$ ,il existe des entiers $x$ et $y$ tels que $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 + ⌊ \sqrt m ⌋$ , pour $m$ non carré[5].

LeVeque préfère appliquer la variante suivante à $X = \sqrt m$ [3] : pour tout réel $X$ tel que $1<X<m$ , il existe des entiers $x$ et $y$ tels que $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$ suffisamment proche de $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 \geq 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$ par s inconnues $x_{1},\dots ,x_{s}$ et la congruence linéaire $ax\equiv y{\pmod {m}}$ par le système homogène de r congruences associé à une matrice $A=(a_{i,j})$ à coefficients entiers à r lignes et s colonnes :

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

Démonstration

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

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

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

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

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

Références

En 1917 ou 1902 :
- (no) A. Thue, « Et bevis for at lignigen A³ + B³ = С³ 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 (DOI 10.1.1.151.636).
(en) Carl Löndahl, « Lecture on sums of squares », 2011.
LeVeque 2014, p. 182, aperçu sur Google Livres.
(en) Victor Shoup, A Computational Introduction to Number Theory and Algebra, CUP, 2005 (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 $X>1$ est remplacée par $X>0$ , et l'hypothèse additionnelle $a\not \equiv 0{\pmod {m}}$ de LeVeque ne suffit pas à garantir la condition supplémentaire $y\neq 0$ 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 $\lambda _{i}\leq m$ , on a donc même $(x_{1},\dots ,x_{s})\not \equiv (0,\dots ,0){\pmod {m}}.$

Articles connexes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.