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, utilise le principe des tiroirs. 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² + 1 ≡ 0 mod m, ce lemme fournit une expression de m comme somme de deux carrés premiers entre eux.

É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, puis l'applique à X = Y = 1 + ⌊√m⌋, pour m non carré.

LeVeque préfère appliquer la variante suivante à X = √m : 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$. 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² + 1 et X = Y = a + 1 ≥ 2, on a deux solutions (x, y) = (1, a), (a, –1).

Sous d'autres hypothèses — 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 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)$.

Démonstrations

• Preuve du théorème de Brauer et Reynolds.
  Notons $\mu _{j}$ le plus petit 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 :

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}}$.

Articles connexes

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