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 < X Y$ ,il existe des entiers $x$ et $y$ tels que $a x \equiv y (\mod m), 1 \leq x < X et | 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 $a x \equiv y (\mod m), 1 \leq x < X et | 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 $a x \equiv y (\mod 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 $λ_{1}, \dots, λ_{s}$ tels que $λ_{1} \dots λ_{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 (\mod m) (i = 1, \dots, r), | x_{j} | < λ_{j} (j = 1, \dots, s) et (x_{1}, \dots, x_{s}) \neq (0, \dots, 0)$ ^[9].

Démonstrations

Preuve du théorème de Brauer et Reynolds.
Notons $μ_{j}$ le plus grand entier strictement inférieur à $λ_{j}$ , c'est-à-dire que $1 + μ_{j}$ est la partie entière par excès de $λ_{j}$ . On a donc $0 \leq μ_{j} < λ_{j} \leq 1 + μ_{j} .$ Le nombre $l$ des s-uplets $x = (x_{1}, \dots, x_{s})$ d'entiers tels que $0 \leq x_{j} \leq μ_{j} (j = 1, \dots, s)$ vérifie : $l = \prod_{j = 1}^{s} (1 + μ_{j}) \geq \prod_{j = 1}^{s} λ_{j} > m^{r} .$ Il est donc strictement supérieur au nombre des valeurs possibles des r-uplets images, dans $(ℤ / m ℤ)^{r}$ , par $x \mapsto A x$ . 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 $(λ_{1}, λ_{2})$ . Les hypothèses $Y > 0$ et $X Y > m$ (donc $X > 0$ ) assurent l'existence d'un couple d'entiers $(x, y) \neq (0, 0)$ tel que $a x \equiv y (\mod 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} (\mod m)$ alors il existe des entiers $u, v > 0$ premiers entre eux tels que $a u \equiv v (\mod 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 $a u \equiv v (\mod 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 (\mod n^{2})$ pour un entier $n > 1$ (nécessairement impair), on montre facilement que $a n \equiv̸ n (\mod n^{2})$ .

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

Enfin, $u$ et $v$ sont premiers entre eux car si $d$ divise $u$ et $v$ alors $m d ∣ (a^{2} + 1) u^{2} + (v - a u) (v + a u) = u^{2} + v^{2} = m$ donc $d ∣ 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 $a u \equiv v (\mod 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 \equiv̸ 0 (\mod 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 $λ_{i} \leq m$ , on a donc même $(x_{1}, \dots, x_{s}) \equiv̸ (0, \dots, 0) (\mod m) .$

Articles connexes

Arithmétique et théorie des nombres

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

[mwkg] (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 ;

[mwwg] (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.

[Leveque182-3] 1 2 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 $X > 1$ est remplacée par $X > 0$ , et l'hypothèse additionnelle $a \equiv̸ 0 (\mod m)$ de LeVeque ne suffit pas à garantir la condition supplémentaire $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} \leq m$ , on a donc même $(x_{1}, \dots, x_{s}) \equiv̸ (0, \dots, 0) (\mod m) .$

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]