Lemme de Thue

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

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

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

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

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