Chapitre extrait du Tome 5 — Arithmétique du livre « Objectif Olympiades de Mathématiques » de Mohammed Aassila. Réservé aux élèves se préparant aux concours d'olympiades de niveau lycée.

2.2 Nombres premiers entre eux

Définition

Soient $n\in {\mathbb{N}}^{\ast }$ et $(x_1,x_2,\dots ,x_n)\in ({\mathbb{Z}}^{\ast }{)}^n$.

1. On dit que $x_1,x_2,\dots ,x_n$ sont premiers entre eux dans leur ensemble si $\text{pgcd}(x_1,x_2,\dots ,x_n)=1$.
2. On dit que $x_1,x_2,\dots ,x_n$ sont premiers entre eux deux à deux si et seulement si : $\forall (i,j)\in [[1,n{]]}^2$, $(i\ne j\Rightarrow x_i\wedge x_j=1)$.

Remarques :

• Si $x_1,x_2,\dots ,x_n$ sont premiers entre eux deux à deux, alors $x_1,x_2,\dots ,x_n$ sont premiers entre eux dans leur ensemble, car alors : $\text{pgcd}(x_1,x_2,\dots ,x_n)=\text{pgcd}(x_1\wedge x_2,x_3,\dots ,x_n)=\text{pgcd}(1,x_3,\dots ,x_n)=1$.
• La réciproque est fausse : il se peut (si $n\ge 3$) que $x_1,x_2,\dots ,x_n$ soient premiers entre eux dans leur ensemble sans être premiers entre eux deux à deux. Par exemple pour $n=3$, et $x_1=6,x_2=10,x_3=15$.
• Pour tout $(x_1,x_2,\dots ,x_n)\in ({\mathbb{Z}}^{\ast }{)}^n$, en notant $\delta =\text{pgcd}(x_1,x_2,\dots ,x_n)$, il existe $(x_1^{\prime },x_2^{\prime },\dots ,x_n^{\prime })\in ({\mathbb{Z}}^{\ast }{)}^n$ tel que : $\forall i\in [[1,n]]$, $x_i=\delta x_i^{\prime }$, et $x_1^{\prime },x_2^{\prime },\dots ,x_n^{\prime }$ sont premiers entre eux dans leur ensemble car : $\delta \text{pgcd}(x_1^{\prime },x_2^{\prime },\dots ,x_n^{\prime })=\text{pgcd}(\delta x_1^{\prime },\delta x_2^{\prime },\dots ,\delta x_n^{\prime })=\delta$.

Proposition

Pour tout $(a,b,c)\in ({\mathbb{Z}}^{\ast }{)}^3$ on a :

$$\{\begin{array}{l}a\wedge b=1\\ c|b\end{array}\Rightarrow a\wedge c=1.$$

Preuve : Supposons $a\wedge b=1$ et $c|b$. Pour tout $d\in {\mathbb{N}}^{\ast }$, si $(d|a$ et $d|c)$, alors $(d|a$ et $d|b)$, donc $d=1$. On conclut que $a\wedge c=1$.

Théorème de Bézout

Soient $n\in {\mathbb{N}}^{\ast }$ et $(x_1,x_2,\dots ,x_n)\in ({\mathbb{Z}}^{\ast }{)}^n$. Pour que $x_1,x_2,\dots ,x_n$ soient premiers entre eux dans leur ensemble, il faut et il suffit qu'il existe $(u_1,u_2,\dots ,u_n)\in {\mathbb{Z}}^n$ tel que :

$$x_1{u}_1+x_2{u}_2+\cdots +x_n{u}_n=1.$$

Démonstration

• Si $x_1,x_2,\dots ,x_n$ sont premiers entre eux dans leur ensemble, alors : $\sum _{i=1}^n{x}_i\mathbb{Z}=\text{pgcd}(x_1,x_2,\dots ,x_n)\mathbb{Z}=\mathbb{Z}$. Comme $1\in \mathbb{Z}$, il existe donc $(u_1,u_2,\dots ,u_n)\in {\mathbb{Z}}^n$ tel que $x_1{u}_1+x_2{u}_2+\cdots +x_n{u}_n=1$.
• Réciproquement, s'il existe $(u_1,u_2,\dots ,u_n)\in {\mathbb{Z}}^n$ tel que $x_1{u}_1+x_2{u}_2+\cdots +x_n{u}_n=1$, alors : $1\in \sum _{i=1}^n{x}_i\mathbb{Z}=\text{pgcd}(x_1,x_2,\dots ,x_n)\mathbb{Z}$ d'où $\text{pgcd}(x_1,x_2,\dots ,x_n)=1$.

Corollaire

Si $a\in {\mathbb{N}}^{\ast }$ et $b\in {\mathbb{N}}^{\ast }$ sont premiers entre eux, alors il existe $m\in {\mathbb{N}}^{\ast }$ et $n\in {\mathbb{N}}^{\ast }$ tels que : $am-bn=1$.

Preuve : Choisissons $x,y\in \mathbb{Z}$ tels que $ax+by=1$. Pour tous les entiers $t$ on a : $a(x+bt)-b(at-y)=1$, donc il suffit de montrer qu'on peut trouver $t$ tel que $x+bt$ et $at-y$ soient des entiers strictement positifs. On peut choisir simplement $t>\max (-x,y)$.

Proposition

Soit $(a,b)\in ({\mathbb{Z}}^{\ast }{)}^2$ tel que $a\wedge b=1$. Il existe $(u,v)\in {\mathbb{Z}}^2$ tel que :

$$au+bv=1,|u|<|b|,|v|\le |a|.$$

On peut trouver $u,v$ « de Bézout » assez petits.

Théorème

Si $\text{pgcd}(a,b)=1$, alors on peut trouver un entier $x$ tel que : $ax\equiv 1(\mathrm{mod}b)$. De plus, deux tels entiers $x$ sont congrus modulo $b$.

Démonstration : Comme nous l'avons déjà observé, seule la deuxième affirmation a besoin d'une preuve. Si $x$ et $x^{\prime }$ sont deux tels entiers, alors $ax\equiv 1\equiv a{x}^{\prime }(\mathrm{mod}b)$, et par suite : $x^{\prime }\equiv ax{x}^{\prime }=(a{x}^{\prime })x\equiv x(\mathrm{mod}b)$, ce qui termine la preuve.

Remarques :

• La réciproque de ce théorème est aussi vraie, car si $ax\equiv 1(\mathrm{mod}b)$, alors on peut écrire $ax-1=by$ pour un certain entier $y$, donc tout diviseur commun à $a$ et à $b$ divise $1$.
• D'après le théorème ci-dessus, tous les nombres $x$ vérifiant $ax\equiv 1(\mathrm{mod}b)$ donnent le même reste lorsqu'ils sont divisés par $b$. Ce reste est appelé l'inverse de $a$ modulo $b$, et est noté $a^{-1}(\mathrm{mod}b)$.
• Le théorème précédent possède plusieurs applications, en particulier le théorème suivant :

Théorème de Gauss

Pour tout $(a,b,c)\in ({\mathbb{Z}}^{\ast }{)}^3$, on a :

$$\{\begin{array}{l}a|bc\\ a\wedge b=1\end{array}\Rightarrow a|c.$$

Démonstration : Supposons $a|bc$ et $a\wedge b=1$. D'après le théorème de Bézout, il existe $(u,v)\in {\mathbb{Z}}^2$ tel que $au+bv=1$. D'où, $c=acu+bcv$. Comme $a|acu$ et $a|bcv$, on conclut que $a|c$.

Écrivons le théorème de Gauss en termes de congruence :

Corollaire

1. Si $ab\equiv ac(\mathrm{mod}n)$, alors $b\equiv c(\mathrm{mod}\frac{n}{a\wedge n})$.
2. En particulier, si $\text{pgcd}(a,n)=1$, alors : $ab\equiv ac(\mathrm{mod}n)\Rightarrow b\equiv c(\mathrm{mod}n)$.

Preuve : Soit $d=\text{pgcd}(a,n)$, alors $a=du,n=dv$ avec $\text{pgcd}(u,v)=1$. Donc $ab\equiv ac(\mathrm{mod}n)$ est équivalente à : $v|u(b-c)$. D'après le théorème de Gauss c'est équivalent à : $v|b-c$, i.e., $b\equiv c(\mathrm{mod}v)$.

Proposition

Soient $a,b$ et $c$ des entiers tels que $a|c$, $b|c$ et $\text{pgcd}(a,b)=1$. Alors : $ab|c$. En d'autres termes, si un entier est un multiple de deux nombres premiers entre eux, alors il est multiple de leur produit.

Preuve : On peut écrire $c=ad$ pour un certain entier $d$. Puisque $b|c$ et $\text{pgcd}(a,b)=1$, alors par le théorème de Gauss on a : $b|d$. Par conséquent, $ab|ad=c$, ce qui termine la preuve.

Proposition

Soient $n\in {\mathbb{N}}^{\ast }$ et $a,x_1,x_2,\dots ,x_n\in {\mathbb{Z}}^{\ast }$. Si $x_i|a$ pour tout $i\in [[1,n]]$, et si $x_1,x_2,\dots ,x_n$ sont premiers entre eux deux à deux, alors $x_1{x}_2\cdots x_n$ divise $a$.

Proposition

Soient $n\in {\mathbb{N}}^{\ast }$ et $a,x_1,x_2,\dots ,x_n\in {\mathbb{Z}}^{\ast }$. Alors on a :

$$(\forall i\in [[1,n]],a\wedge x_i=1)\iff a\wedge (x_1{x}_2\cdots x_n)=1.$$

Proposition

Pour tout $(a,b)\in ({\mathbb{Z}}^{\ast }{)}^2$ et pour tout $(k,l)\in ({\mathbb{N}}^{\ast }{)}^2$ on a : $a\wedge b=1\iff a^k\wedge b^l=1$.

Corollaire

Pour tout $(a,b)\in ({\mathbb{Z}}^{\ast }{)}^2$ et pour tout $k\in {\mathbb{N}}^{\ast }$ on a : $a^k\wedge b^k=(a\wedge b{)}^k$.

Corollaire

Soient $n\in {\mathbb{N}}^{\ast }$ et $(x_1,x_2,\dots ,x_n)\in ({\mathbb{Z}}^{\ast }{)}^n$. Si $x_1,x_2,\dots ,x_n$ sont premiers entre eux deux à deux, alors :

$$\text{ppcm}(x_1,x_2,\dots ,x_n)=|x_1{x}_2\cdots x_n|.$$

Proposition

Pour tout $(a,b)\in ({\mathbb{Z}}^{\ast }{)}^2$ on a : $(a\wedge b)\cdot (a\vee b)=|ab|$.

Corollaire

Si $a,b$ sont des entiers et $a^n|b^n$ pour un entier $n\ge 1$, alors $a|b$.

Preuve : Si $a=0$ ou $b=0$ le résultat est immédiat. Supposons dans la suite que $a$ et $b$ sont non nuls. Soit $d=\text{pgcd}(a,b)$, et écrivons $a=du,b=dv$ avec $\text{pgcd}(u,v)=1$. Alors $d^n{u}^n|d^n{v}^n$, d'où $u^n|v^n$. D'après ce qu'on a vu ci-haut $\text{pgcd}(u,v^n)=1$, et comme $u$ divise $v^n$ (car $u|u^n|v^n$), on déduit que $u|1$ et par suite $u=\pm 1$. Par conséquent $a=\pm d$ et il divise clairement $b=dv$.

Proposition

Soient $a,b$ et $m,n$ des entiers strictement positifs. Si $\text{pgcd}(a,b)=1$, alors :

$$\text{pgcd}(a^m-b^m,a^n-b^n)=a^{\text{pgcd}(m,n)}-b^{\text{pgcd}(m,n)}.$$

Preuve : En remplaçant $a,b,m,n$ par $a^{\text{pgcd}(m,n)},b^{\text{pgcd}(m,n)},\frac{m}{\text{pgcd}(m,n)}$ et $\frac{n}{\text{pgcd}(m,n)}$ respectivement, on peut supposer que $\text{pgcd}(m,n)=1$. Comme $a\equiv b(\mathrm{mod}a-b)$, on a : $a^k\equiv b^k(\mathrm{mod}a-b)$ pour tout $k\ge 1$. Donc, $a-b$ divise $\text{pgcd}(a^m-b^m,a^n-b^n)$. Réciproquement, soit $d=\text{pgcd}(a^m-b^m,a^n-b^n)$, et montrons que $d|a-b$. On a : $a^m\equiv b^m(\mathrm{mod}d)$ et $a^n\equiv b^n(\mathrm{mod}d)$, donc $a^{mk}\equiv b^{mk}(\mathrm{mod}d)$ et $a^{nl}\equiv b^{nl}(\mathrm{mod}d)$ pour tout $k,l\ge 1$. Comme $\text{pgcd}(m,n)=1$, d'après le théorème de Bézout il existe $k,l\ge 1$ tels que $km=ln+1$, par conséquent :

$$a^{ln+1}=a^{mk}\equiv b^{mk}=b^{nl+1}\equiv b\cdot a^{nl}(\mathrm{mod}d),$$

c'est-à-dire $d|a^{nl}(a-b)$. Or comme $\text{pgcd}(a,b)=1$, on a : $\text{pgcd}(a,b^m)=1$ et par suite $\text{pgcd}(a,a^m-b^m)=1$. Puisque $d$ divise $a^m-b^m$, on conclut que $\text{pgcd}(a,d)=1$. D'après le théorème de Gauss on obtient $d|a-b$, le résultat en découle.

Corollaire

Soient $a>b>0$ et $m,n$ des entiers strictement positifs. Si $\text{pgcd}(a,b)=1$, alors $a^m-b^m$ divise $a^n-b^n$ si, et seulement si, $m|n$.

Preuve : Si $m|n$ alors $n=md$ et $a^m-b^m$ divise $a^n-b^n=(a^m{)}^d-(b^m{)}^d$. Réciproquement, on suppose que $a^m-b^m|a^n-b^n$, et soit $n=mq+r$ la division euclidienne de $n$ par $m$ avec $0\le r<m$. On suppose $r>0$, alors :

$$a^n-b^n=a^{mq}(a^r-b^r)+b^r(a^{mq}-b^{mq}).$$

D'après la première étape $a^m-b^m|a^{mq}-b^{mq}$, d'où $a^m-b^m|a^{mq}(a^r-b^r)$. Puisque $\text{pgcd}(a,b)=1$ on a : $\text{pgcd}(a^{mq},a^m-b^m)=1$ et en utilisant le théorème de Gauss on déduit que $a^n-b^n|a^r-b^r$. Or ceci est impossible puisque $0<a^r-b^r<a^m-b^m$ (pour voir que cette dernière est vraie, il suffit de l'écrire sous la forme $a^{r-1}+a^{r-2}b+\cdots +b^{r-1}<a^{m-1}+a^{m-2}b+\cdots +b^{m-1}$).

Proposition (équation diophantienne $ax+by=c$)

Soient $a,b$ et $c$ des entiers non nuls. L'équation diophantienne : $ax+by=c$ admet des solutions entières si, et seulement si, $\text{pgcd}(a,b)|c$. De plus, dans ce cas, si $d=\text{pgcd}(a,b)$, et $(x_0,y_0)$ est une solution entière particulière, alors l'ensemble des solutions entières est donné par :

$$\left\{x=x_0+\frac{b}{d}t,y=y_0-\frac{a}{d}t,t\in \mathbb{Z}\right\}.$$

En particulier, si $ab>0$ et $x,y\in \mathbb{Z}$ est une solution entière, alors on peut supposer que $x>0>y$ ou $x<0<y$.

Preuve

• Supposons qu'il existe $x,y\in \mathbb{Z}$ tels que $ax+by=c$. Puisque $d|a$ et $d|b$, alors $d|(ax+by)$, i.e., $d|c$. Réciproquement, si $c=de$, avec $e\in \mathbb{Z}$, d'après Bézout il existe deux entiers $u$ et $v$ tels que $d=au+bv$, d'où $c=a\cdot eu+b\cdot ev$, donc l'équation diophantienne admet la solution entière $x_0=eu,y_0=ev$.
• On suppose $d|c$, et soit $x=x_0,y=y_0$ une solution particulière de l'équation diophantienne, alors si $x=x_1,y=y_1$ est une autre solution de l'équation on doit avoir $a(x_1-x_0)=b(y_0-y_1)$, c'est-à-dire : $\frac{a}{d}(x_1-x_0)=\frac{b}{d}(y_0-y_1)$. Par suite $\frac{b}{d}|\frac{a}{d}(x_1-x_0)$ et, comme $\text{pgcd}\left(\frac{a}{d},\frac{b}{d}\right)=1$, alors $\frac{b}{d}|(x_1-x_0)$. En posant $x_1-x_0=\frac{b}{d}t$, on obtient $y_0-y_1=\frac{a}{d}t$. Réciproquement, il est facile de voir que $x=x_0+\frac{b}{d}t,y=y_0-\frac{a}{d}t$ est solution de l'équation diophantienne.
• Supposons que $a,b>0$ (le cas $a,b<0$ se traite de la même façon). Alors : $x_0+\frac{b}{d}t>0\iff t>-\frac{d{x}_0}{b}$ et $y_0-\frac{a}{d}t<0\iff t>\frac{d{y}_0}{a}$. Donc, en choisissant $t\in \mathbb{Z}$ tel que $t>\max \left(-\frac{d{x}_0}{b},\frac{d{y}_0}{a}\right)$, et en posant $x_1=x_0+\frac{b}{d}t$ et $y_1=y_0-\frac{a}{d}t$, on a : $x_1>0,y_1<0$ et $a{x}_1+b{y}_1=c$. De manière analogue, on peut montrer qu'on peut prendre une solution entière $x,y$ de l'équation diophantienne avec $x<0<y$.

Théorème chinois

Soient $n\in {\mathbb{N}}^{\ast }$, et $a_1,a_2,\dots ,a_n\in {\mathbb{N}}^{\ast }$ des entiers naturels premiers entre eux deux à deux. Alors, pour tout $(b_1,b_2,\dots ,b_n)\in {\mathbb{Z}}^n$, il existe $\beta \in \mathbb{Z}$ tel que :

$$(\forall i\in [[1,n]],x\equiv b_i(\mathrm{mod}{a}_i))\iff x\equiv \beta (\mathrm{mod}{a}_1{a}_2\cdots a_n).$$

Démonstration : Notons, pour $i\in [[1,n]]$ : $A_i=\frac{a}{a_i}$ où $a=a_1{a}_2\cdots a_n$. Soit $i\in [[1,n]]$, puisque $A_i\wedge a_i=1$, alors il existe, d'après le théorème de Bézout, $c_i\in \mathbb{Z}$ tel que $A_i{c}_i\equiv 1(\mathrm{mod}{a}_i)$. Notons $\beta =\sum _{i=1}^n{A}_i{b}_i{c}_i$. On a pour tout $i\in [[1,n]]$ : $\beta \equiv A_i{b}_i{c}_i\equiv b_i(\mathrm{mod}{a}_i)$.

Méthode

Pour résoudre un système de congruences simultanées à une inconnue on commence par résoudre la première congruence, puis on reporte dans la deuxième, etc.