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].

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.
↑ (en) Carl Löndahl, « Lecture on sums of squares », 2011.
1 2 3 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}}.$

Théorème de Brauer et Reynolds

Application aux sommes de deux carrés

Références

Articles connexes

Related Articles