Arithmétique dans l'ensemble des entiers relatifs

L'arithmétique est la plus ancienne des mathématiques, et sans doute la plus déroutante : ses énoncés se comprennent en une phrase, ses démonstrations demandent souvent une idée. Ce chapitre étudie les entiers relatifs sous l'angle de la multiplication : qui divise qui, comment fabriquer les diviseurs communs de deux entiers, comment reconnaître deux entiers qui n'en partagent aucun, comment résoudre des équations dont on n'accepte que les solutions entières. C'est un changement de point de vue complet par rapport aux chapitres d'analyse : dans $\mathbb{R}$, l'équation $3x=7$ a une solution et l'affaire est close ; dans $\mathbb{Z}$, elle n'en a pas, et c'est précisément cette rigidité qui rend le sujet intéressant.

Tout ce chapitre repose sur un unique théorème, celui de la division euclidienne : deux entiers étant donnés, on peut diviser le premier par le second en s'arrêtant à un reste, et ce reste est unique. Ce résultat, que l'on croit connaître depuis l'école primaire, est en réalité l'outil qui engendre tout le reste. L'algorithme d'Euclide n'est qu'une suite de divisions euclidiennes, la relation de Bézout se démontre par une division euclidienne, le lemme de Gauss se déduit de Bézout, et le théorème fondamental de l'arithmétique, que nous verrons dans la seconde partie du chapitre, se déduit de Gauss. Chaque fois que vous serez bloqué sur un exercice d'arithmétique, la première question à vous poser sera donc : puis-je faire une division euclidienne ici ?

La seconde particularité du chapitre est sa dimension algorithmique : les démonstrations ne se contentent pas d'affirmer l'existence d'un objet, elles disent comment le calculer. L'algorithme d'Euclide fournit le PGCD, sa version étendue fournit des coefficients de Bézout, et ces coefficients résolvent effectivement les équations diophantiennes. Vous devrez donc savoir à la fois démontrer les théorèmes et mener les calculs à la main, proprement, sans erreur de signe.

Les notations suivantes sont fixées une fois pour toutes. Les lettres $a$, $b$, $c$, $d$, $k$, $m$, $n$, $q$, $r$, $u$, $v$ désignent toujours des entiers relatifs, c'est-à-dire des éléments de $\mathbb{Z}$, sauf mention contraire ; $\mathbb{N}$ est l'ensemble des entiers naturels, ${\mathbb{N}}^{\ast }$ celui des entiers naturels non nuls et ${\mathbb{Z}}^{\ast }$ celui des entiers relatifs non nuls. La divisibilité se note $a\mid b$ (« $a$ divise $b$ »), et sa négation $a\nmid b$. Le plus grand commun diviseur de $a$ et $b$ se note $a\wedge b$, synonyme de $\mathrm{pgcd}(a,b)$ ; le plus petit commun multiple se note $a\vee b$, synonyme de $\mathrm{ppcm}(a,b)$. La valeur absolue de $a$ est notée $\mathrm{\mid }a\mathrm{\mid }$, la partie entière d'un réel $x$ est notée $\lfloor x\rfloor$. Enfin, $\mathcal{D}(a)$ désignera l'ensemble des diviseurs de $a$ et $\mathcal{D}(a,b)$ celui des diviseurs communs à $a$ et $b$. La seconde partie du chapitre ajoutera trois notations : $\mathcal{P}$ pour l'ensemble des nombres premiers, $v_p(a)$ pour la valuation $p$-adique de $a$, et $a\equiv b[n]$ pour la congruence modulo $n$. Attention à ne pas confondre les symboles $\wedge$ et $\vee$ avec les connecteurs logiques « et » et « ou » : dans tout ce chapitre, ils désignent exclusivement le PGCD et le PPCM.

Divisibilité dans Z

Définition et premiers exemples

Tout part d'une définition d'une simplicité désarmante, qu'il faut lire avec attention : elle ne parle pas de fraction, ni de quotient exact, mais de l'existence d'un entier.

Deux entiers jouent un rôle à part, et méritent d'être traités séparément une bonne fois pour toutes : $0$ et $\pm 1$. Ce sont eux qui produisent le plus d'erreurs en début d'année, parce que l'intuition de la division apprise à l'école ne s'y applique pas.

Démonstration. Pour le point 1, il suffit d'écrire $a=1\times a$ et $a=(-1)\times (-a)$, ce qui exhibe dans les deux cas un entier convenable. Pour le point 2, on écrit $0=a\times 0$ : l'entier $k=0$ convient, quel que soit $a$.

Pour le point 3, supposons $0\mid a$ : il existe $k\in \mathbb{Z}$ tel que $a=0\times k=0$, donc $a=0$. Réciproquement, $0\mid 0$ d'après le point 2.

Pour le point 4, supposons $a\mid b$ et écrivons $b=ak$. Alors $-b=a\times (-k)$ et $b=(-a)\times (-k)$, ce qui donne $a\mid -b$ et $-a\mid b$. Les réciproques s'obtiennent en appliquant ce que l'on vient de démontrer à $-b$ ou $-a$. Comme $\mathrm{\mid }a\mathrm{\mid }$ vaut $a$ ou $-a$, et de même pour $\mathrm{\mid }b\mathrm{\mid }$, la dernière équivalence en découle. $\mathrm{\square }$

Propriétés de la divisibilité

Passons aux propriétés que l'on utilisera constamment. La troisième, la stabilité par combinaison linéaire, est de très loin la plus rentable en exercice : c'est elle qui permet de fabriquer, à partir de deux informations de divisibilité, une troisième information souvent bien plus exploitable.

Démonstration. Point 1. L'égalité $a=a\times 1$ donne immédiatement $a\mid a$.

Point 2. Supposons $a\mid b$ et $b\mid c$. Il existe donc $k\in \mathbb{Z}$ tel que $b=ak$, et $\mathrm{\ell }\in \mathbb{Z}$ tel que $c=b\mathrm{\ell }$. En substituant, $c=(ak)\mathrm{\ell }=a(k\mathrm{\ell })$, et $k\mathrm{\ell }$ est un entier : donc $a\mid c$.

Point 3. Supposons $a\mid b$ et $a\mid c$ : écrivons $b=ak$ et $c=a\mathrm{\ell }$ avec $k,\mathrm{\ell }\in \mathbb{Z}$. Soient $u,v\in \mathbb{Z}$. Alors

$$bu+cv=aku+a\mathrm{\ell }v=a(ku+\mathrm{\ell }v),$$

et $ku+\mathrm{\ell }v$ est un entier comme somme de produits d'entiers. Donc $a\mid (bu+cv)$.

Point 4. Si $b=ak$, alors $bc=(ac)k$, donc $ac\mid bc$.

Point 5. Supposons $a\mid b$ et $b\mid a$. Si $a=0$, alors de $a\mid b$ on tire $b=0\times k=0$, donc $a=b$ et la conclusion est vraie. Supposons donc $a\mathrm{\ne }0$ ; alors $b\mathrm{\ne }0$, car sinon $b\mid a$ donnerait $a=0$. Écrivons $b=ak$ et $a=b\mathrm{\ell }$ avec $k,\mathrm{\ell }\in \mathbb{Z}$. En substituant, $a=ak\mathrm{\ell }$, et comme $a\mathrm{\ne }0$ on peut simplifier : $k\mathrm{\ell }=1$. Or les seuls couples d'entiers de produit $1$ sont $(1,1)$ et $(-1,-1)$ : en effet $\mathrm{\mid }k\mathrm{\mid }\times \mathrm{\mid }\mathrm{\ell }\mathrm{\mid }=1$ avec $\mathrm{\mid }k\mathrm{\mid }$ et $\mathrm{\mid }\mathrm{\ell }\mathrm{\mid }$ entiers naturels non nuls impose $\mathrm{\mid }k\mathrm{\mid }=\mathrm{\mid }\mathrm{\ell }\mathrm{\mid }=1$, et le signe du produit impose $k$ et $\mathrm{\ell }$ de même signe. Donc $k=\pm 1$, c'est-à-dire $b=\pm a$. $\mathrm{\square }$

Vient maintenant le résultat le plus utile du chapitre pour majorer un diviseur. Il traduit une idée simple : un diviseur ne peut pas être plus gros que ce qu'il divise, à condition que ce dernier ne soit pas nul.

Démonstration. Supposons $a\mid b$ et écrivons $b=ak$ avec $k\in \mathbb{Z}$. Comme $b\mathrm{\ne }0$, on a nécessairement $k\mathrm{\ne }0$ (sinon $b$ serait nul), donc $\mathrm{\mid }k\mathrm{\mid }⩾1$ puisque $\mathrm{\mid }k\mathrm{\mid }$ est un entier naturel non nul. En passant aux valeurs absolues dans $b=ak$ :

$$\mathrm{\mid }b\mathrm{\mid }=\mathrm{\mid }a\mathrm{\mid }\times \mathrm{\mid }k\mathrm{\mid }⩾\mathrm{\mid }a\mathrm{\mid }\times 1=\mathrm{\mid }a\mathrm{\mid },$$

la première inégalité étant licite car $\mathrm{\mid }a\mathrm{\mid }⩾0$. D'où $\mathrm{\mid }a\mathrm{\mid }⩽\mathrm{\mid }b\mathrm{\mid }$. $\mathrm{\square }$

L'ensemble des diviseurs d'un entier

Démonstration. Soit $d\in \mathcal{D}(n)$. Alors $d\mathrm{\ne }0$ : sinon $0\mid n$ donnerait $n=0$, exclu. De plus $n\mathrm{\ne }0$, donc la propriété précédente s'applique et donne $\mathrm{\mid }d\mathrm{\mid }⩽\mathrm{\mid }n\mathrm{\mid }$, c'est-à-dire $-\mathrm{\mid }n\mathrm{\mid }⩽d⩽\mathrm{\mid }n\mathrm{\mid }$ avec $d\mathrm{\ne }0$. L'ensemble $\mathcal{D}(n)$ est donc inclus dans un ensemble fini de $2\mathrm{\mid }n\mathrm{\mid }$ entiers, ce qui prouve sa finitude. L'égalité $\mathcal{D}(n)=\mathcal{D}(-n)=\mathcal{D}(\mathrm{\mid }n\mathrm{\mid })$ et la symétrie découlent du point 4 de la première propriété de cette section. $\mathrm{\square }$

Deux méthodes fondamentales

Division euclidienne

Nous arrivons au théorème central du chapitre. Son énoncé est celui de la division apprise à l'école primaire, mais il est ici démontré, et surtout étendu aux entiers négatifs, ce qui réserve une petite surprise.

Le théorème

Démonstration. Existence. Considérons l'ensemble

$$S=\{a-bk;k\in \mathbb{Z}\}\cap \mathbb{N},$$

c'est-à-dire l'ensemble des valeurs positives ou nulles prises par $a-bk$ lorsque $k$ parcourt $\mathbb{Z}$.

Montrons d'abord que $S$ n'est pas vide. Posons $\epsilon =1$ si $b>0$ et $\epsilon =-1$ si $b<0$, de sorte que $b\epsilon =\mathrm{\mid }b\mathrm{\mid }$. Choisissons $k=-\mathrm{\mid }a\mathrm{\mid }\epsilon$. Alors

$$a-bk=a+\mathrm{\mid }a\mathrm{\mid }b\epsilon =a+\mathrm{\mid }a\mathrm{\mid }\mathrm{\mid }b\mathrm{\mid }⩾a+\mathrm{\mid }a\mathrm{\mid }⩾0,$$

où l'on a utilisé $\mathrm{\mid }b\mathrm{\mid }⩾1$ (car $b$ est un entier non nul) et $\mathrm{\mid }a\mathrm{\mid }⩾-a$. Donc $S\mathrm{\ne }\mathrm{\varnothing }$.

Ainsi $S$ est une partie non vide de $\mathbb{N}$ : elle admet un plus petit élément, que l'on note $r$. Par définition de $S$, il existe $q\in \mathbb{Z}$ tel que $r=a-bq$, c'est-à-dire $a=bq+r$, et l'on a $r⩾0$.

Montrons enfin que $r<\mathrm{\mid }b\mathrm{\mid }$. Supposons par l'absurde $r⩾\mathrm{\mid }b\mathrm{\mid }$. Alors

$$r-\mathrm{\mid }b\mathrm{\mid }=a-bq-b\epsilon =a-b(q+\epsilon )⩾0,$$

donc $r-\mathrm{\mid }b\mathrm{\mid }$ appartient à $S$. Mais $\mathrm{\mid }b\mathrm{\mid }>0$, donc $r-\mathrm{\mid }b\mathrm{\mid }<r$ : cela contredit la minimalité de $r$. On a donc bien $0⩽r<\mathrm{\mid }b\mathrm{\mid }$.

Unicité. Soient $(q,r)$ et $(q^{\mathrm{\prime }},r^{\mathrm{\prime }})$ deux couples vérifiant les conditions. De $bq+r=b{q}^{\mathrm{\prime }}+r^{\mathrm{\prime }}$ on tire

$$b(q-q^{\mathrm{\prime }})=r^{\mathrm{\prime }}-r\mathrm{.}$$

Comme $0⩽r<\mathrm{\mid }b\mathrm{\mid }$ et $0⩽r^{\mathrm{\prime }}<\mathrm{\mid }b\mathrm{\mid }$, la différence $r^{\mathrm{\prime }}-r$ vérifie $-\mathrm{\mid }b\mathrm{\mid }<r^{\mathrm{\prime }}-r<\mathrm{\mid }b\mathrm{\mid }$, c'est-à-dire $\mathrm{\mid }{r}^{\mathrm{\prime }}-r\mathrm{\mid }<\mathrm{\mid }b\mathrm{\mid }$. En passant aux valeurs absolues dans l'égalité ci-dessus :

$$\mathrm{\mid }b\mathrm{\mid }\times \mathrm{\mid }q-q^{\mathrm{\prime }}\mathrm{\mid }=\mathrm{\mid }{r}^{\mathrm{\prime }}-r\mathrm{\mid }<\mathrm{\mid }b\mathrm{\mid }\mathrm{.}$$

En divisant par $\mathrm{\mid }b\mathrm{\mid }>0$, il vient $\mathrm{\mid }q-q^{\mathrm{\prime }}\mathrm{\mid }<1$. Or $\mathrm{\mid }q-q^{\mathrm{\prime }}\mathrm{\mid }$ est un entier naturel : donc $\mathrm{\mid }q-q^{\mathrm{\prime }}\mathrm{\mid }=0$, c'est-à-dire $q=q^{\mathrm{\prime }}$. En reportant, $r^{\mathrm{\prime }}-r=0$, donc $r=r^{\mathrm{\prime }}$. Le couple est bien unique. $\mathrm{\square }$

Lorsque le diviseur est positif, le quotient s'exprime à l'aide de la partie entière, ce qui est commode pour le calcul comme pour la programmation.

Démonstration. Par définition de la partie entière d'un réel $x$, l'entier $\lfloor x\rfloor$ est l'unique entier $m$ tel que $m⩽x<m+1$. Appliquons cela à $x={\displaystyle \frac{a}{b}}$ et posons $q=\lfloor {\displaystyle \frac{a}{b}}\rfloor$ ; alors

$$q⩽{\displaystyle \frac{a}{b}}<q+1.$$

En multipliant par $b>0$, ce qui préserve le sens des inégalités, on obtient $bq⩽a<bq+b$, soit encore

$$0⩽a-bq<b=\mathrm{\mid }b\mathrm{\mid }\mathrm{.}$$

Le couple $(q,a-bq)$ vérifie donc les deux conditions du théorème ; par unicité, c'est le couple de la division euclidienne. $\mathrm{\square }$

Le cas des dividendes négatifs

C'est l'endroit où presque tout le monde se trompe au moins une fois. La règle est mécanique : le reste doit atterrir dans $\{0,1,\dots ,\mathrm{\mid }b\mathrm{\mid }-1\}$, donc le quotient « descend » d'un cran par rapport à ce que suggère la calculatrice.

Divisibilité et reste nul

Le lien entre la division euclidienne et la divisibilité tient en une équivalence, que l'on utilisera sans cesse.

Démonstration. $(⟸)$ Si $r=0$, alors $a=bq$ avec $q\in \mathbb{Z}$, donc $b\mid a$ par définition.

$(⟹)$ Supposons $b\mid a$ : il existe $k\in \mathbb{Z}$ tel que $a=bk$. Le couple $(k,0)$ vérifie alors $a=bk+0$ avec $0⩽0<\mathrm{\mid }b\mathrm{\mid }$ : c'est donc le couple de la division euclidienne de $a$ par $b$, par unicité. Ainsi $q=k$ et $r=0$. $\mathrm{\square }$

Écrire un entier selon son reste

Voici l'usage le plus fréquent de la division euclidienne dans les exercices : elle fournit une disjonction de cas exhaustive, en un nombre fini de cas, sur un ensemble pourtant infini d'entiers.

Démonstration. C'est exactement le théorème de la division euclidienne appliqué au diviseur $b=n>0$, pour lequel $\mathrm{\mid }b\mathrm{\mid }=n$ : le reste $r$ vérifie $0⩽r<n$, donc appartient à $\{0,1,\dots ,n-1\}$, et le couple $(q,r)$ est unique. $\mathrm{\square }$

PGCD et algorithme d'Euclide

Définition du PGCD

Deux entiers ont toujours au moins un diviseur commun, à savoir $1$. La question est de savoir s'il en existe un plus grand, et lequel. Toute la difficulté de la définition consiste à justifier proprement l'existence de ce plus grand élément.

Démonstration (existence). L'ensemble $\mathcal{D}(a,b)$ est une partie de $\mathbb{Z}$ non vide, car $1$ divise $a$ et $b$. Montrons qu'elle est majorée. Comme $a$ et $b$ ne sont pas tous les deux nuls, l'un au moins est non nul ; quitte à échanger les rôles, supposons $a\mathrm{\ne }0$. Soit $d\in \mathcal{D}(a,b)$ : alors $d\mid a$ avec $a\mathrm{\ne }0$, donc $\mathrm{\mid }d\mathrm{\mid }⩽\mathrm{\mid }a\mathrm{\mid }$, et en particulier $d⩽\mathrm{\mid }a\mathrm{\mid }$. L'ensemble $\mathcal{D}(a,b)$ est donc une partie non vide et majorée de $\mathbb{Z}$ : elle admet un plus grand élément. $\mathrm{\square }$

Démonstration. Point 1. Comme $1\in \mathcal{D}(a,b)$ et que $a\wedge b$ est le plus grand élément de cet ensemble, $a\wedge b⩾1$.

Point 2. L'ensemble $\mathcal{D}(a,b)$ est défini symétriquement en $a$ et $b$, d'où la première égalité. La seconde vient de $\mathcal{D}(a)=\mathcal{D}(\mathrm{\mid }a\mathrm{\mid })$.

Point 3. Tout entier divise $0$, donc $\mathcal{D}(a,0)=\mathcal{D}(a)$, dont le plus grand élément est $\mathrm{\mid }a\mathrm{\mid }$ : en effet $\mathrm{\mid }a\mathrm{\mid }$ divise $a$, et tout diviseur $d$ de $a\mathrm{\ne }0$ vérifie $d⩽\mathrm{\mid }d\mathrm{\mid }⩽\mathrm{\mid }a\mathrm{\mid }$. Pour la seconde égalité, $\mathcal{D}(a,1)=\mathcal{D}(a)\cap \{-1,1\}\subset \{-1,1\}$, de plus grand élément $1$.

Point 4. Si $b\mid a$, alors tout diviseur de $b$ divise $a$ par transitivité, donc $\mathcal{D}(a,b)=\mathcal{D}(b)$, dont le plus grand élément est $\mathrm{\mid }b\mathrm{\mid }$ car $b\mathrm{\ne }0$. Réciproquement, si $a\wedge b=\mathrm{\mid }b\mathrm{\mid }$, alors $\mathrm{\mid }b\mathrm{\mid }$ est un diviseur commun, donc $\mathrm{\mid }b\mathrm{\mid }\mid a$, donc $b\mid a$. $\mathrm{\square }$

Le lemme fondamental

Comment calculer $a\wedge b$ sans lister tous les diviseurs, ce qui serait impraticable pour de grands nombres ? La réponse tient dans le lemme suivant, qui remplace le couple $(a,b)$ par un couple plus petit ayant exactement le même PGCD. Sa démonstration est un modèle du genre : on ne compare pas les PGCD, on montre que les deux ensembles de diviseurs communs sont égaux.

Démonstration. Écrivons $a=bq+r$ avec $q\in \mathbb{Z}$ et $0⩽r<\mathrm{\mid }b\mathrm{\mid }$. Procédons par double inclusion.

$(\subset )$ Soit $d\in \mathcal{D}(a,b)$, c'est-à-dire $d\mid a$ et $d\mid b$. Par stabilité par combinaison linéaire, $d$ divise $a\times 1+b\times (-q)=a-bq=r$. Comme de plus $d\mid b$, on a $d\in \mathcal{D}(b,r)$.

$(\supset )$ Soit $d\in \mathcal{D}(b,r)$, c'est-à-dire $d\mid b$ et $d\mid r$. Par combinaison linéaire, $d$ divise $b\times q+r\times 1=bq+r=a$. Comme de plus $d\mid b$, on a $d\in \mathcal{D}(a,b)$.

Les deux ensembles sont donc égaux. Ils sont tous les deux non vides et majorés (car $b\mathrm{\ne }0$ apparaît dans les deux couples), donc ils ont le même plus grand élément : $a\wedge b=b\wedge r$. $\mathrm{\square }$

L'algorithme d'Euclide

Le lemme précédent, appliqué en boucle, donne une méthode de calcul effective : à chaque étape, on remplace le couple par (diviseur, reste), et les restes décroissent strictement, donc le processus s'arrête.

Démonstration. Terminaison. Notons $r_0=\mathrm{\mid }b\mathrm{\mid }$, puis $r_1,r_2,\dots$ les restes successifs. Tant qu'ils sont non nuls, la définition de la division euclidienne impose

$$0⩽r_{k+1}<r_k$$

pour tout $k$ : la suite des restes est une suite d'entiers naturels strictement décroissante. Une telle suite ne peut être infinie : par récurrence immédiate, $r_k⩽r_0-k$, donc $r_k<0$ dès que $k>r_0$, ce qui est absurde. Il existe donc un rang $n$ tel que $r_n\mathrm{\ne }0$ et $r_{n+1}=0$.

Valeur. Par le lemme d'Euclide appliqué à chaque étape,

$$a\wedge b=\mathrm{\mid }a\mathrm{\mid }\wedge \mathrm{\mid }b\mathrm{\mid }=r_0\wedge r_1=r_1\wedge r_2=\cdots =r_{n-1}\wedge r_n=r_n\wedge r_{n+1}=r_n\wedge 0=r_n,$$

la dernière égalité venant du point 3 de la propriété du PGCD ($d\wedge 0=\mathrm{\mid }d\mathrm{\mid }$ pour $d\mathrm{\ne }0$) et de $r_n>0$. Le dernier reste non nul est bien le PGCD. $\mathrm{\square }$

Propriétés du PGCD

Démonstration. Comme le PGCD ne dépend pas des signes et que $\mathrm{\mid }ka\mathrm{\mid }=\mathrm{\mid }k\mathrm{\mid }\mathrm{\mid }a\mathrm{\mid }$, on peut supposer $a⩾0$, $b⩾0$ et $k>0$.

Premier cas : $b=0$ (donc $a>0$). Alors $(ka)\wedge 0=ka=k(a\wedge 0)$, d'après le point 3 de la propriété du PGCD.

Deuxième cas : $b>0$ et $b\mid a$. L'algorithme s'arrête dès la première division : $a\wedge b=b$, et de $kb\mid ka$ on tire $(ka)\wedge (kb)=kb=k(a\wedge b)$.

Troisième cas : $b>0$ et $b\nmid a$. Déroulons l'algorithme d'Euclide pour le couple $(a,b)$ :

$$\begin{array}{rlrl}{\displaystyle a}& {\displaystyle =b{q}_1+r_1,}& {\displaystyle \text{avec }0}& {\displaystyle ⩽r_1<b,}\\ {\displaystyle b}& {\displaystyle =r_1{q}_2+r_2,}& {\displaystyle \text{avec }0}& {\displaystyle ⩽r_2<r_1,}\\ {\displaystyle }& {\displaystyle \mathrm{⋮}}& {\displaystyle }& {\displaystyle }\\ {\displaystyle r_{n-1}}& {\displaystyle =r_n{q}_{n+1}+0,}& {\displaystyle }& {\displaystyle }\end{array}$$

le dernier reste non nul étant $r_n=a\wedge b$. Multiplions chacune de ces égalités par $k>0$ :

$$ka=(kb)q_1+k{r}_1,kb=(k{r}_1)q_2+k{r}_2,\dots$$

Les encadrements sont préservés : de $0⩽r_{j+1}<r_j$ on tire $0⩽k{r}_{j+1}<k{r}_j$ puisque $k>0$. Chaque ligne obtenue est donc exactement une division euclidienne, et la suite de ces lignes est précisément l'algorithme d'Euclide appliqué au couple $(ka,kb)$. Son dernier reste non nul est $k{r}_n$, donc

$$(ka)\wedge (kb)=k{r}_n=k(a\wedge b)=\mathrm{\mid }k\mathrm{\mid }(a\wedge b),$$

la dernière égalité venant de la réduction initiale au cas $k>0$. $\mathrm{\square }$

Le résultat suivant est le plus important de la section : il dit que les diviseurs communs de $a$ et $b$ ne sont pas seulement majorés par $a\wedge b$, mais qu'ils le divisent tous. C'est une information beaucoup plus forte, et c'est elle qui servira partout.

Nous admettons provisoirement ce résultat : sa démonstration, immédiate une fois la relation de Bézout établie, est donnée juste après celle-ci, dans la section « Entiers premiers entre eux, Bézout et Gauss ». Il n'y a aucun cercle vicieux, car la démonstration de la relation de Bézout n'utilise que la division euclidienne et la définition du PGCD, jamais cette caractérisation.

PGCD de plusieurs entiers

Démonstration. Il suffit de montrer que les trois nombres ont le même ensemble de diviseurs, puisqu'ils sont alors le plus grand élément d'un même ensemble. Soit $d\in \mathbb{Z}$. D'après la caractérisation des diviseurs communs (admise ci-dessus), on a la chaîne d'équivalences

$$d\mid [(a\wedge b)\wedge c]⟺(d\mid (a\wedge b)\text{ et }d\mid c)⟺(d\mid a\text{ et }d\mid b\text{ et }d\mid c)\mathrm{.}$$

La dernière condition est symétrique en $a$, $b$, $c$ : elle caractérise donc aussi les diviseurs de $a\wedge (b\wedge c)$, et les diviseurs communs à $a$, $b$ et $c$, dont le plus grand élément est $a\wedge b\wedge c$. Les trois entiers, tous positifs, ont donc les mêmes diviseurs, et en particulier se divisent mutuellement : ils sont égaux. $\mathrm{\square }$

Entiers premiers entre eux, Bézout et Gauss

La relation de Bézout

Nous savons calculer $a\wedge b$. Le théorème suivant affirme bien davantage : ce PGCD s'écrit en fonction de $a$ et $b$, à coefficients entiers. C'est le résultat le plus puissant du chapitre.

Démonstration. Considérons l'ensemble des valeurs strictement positives prises par les combinaisons linéaires entières de $a$ et $b$ :

$$S=\{au+bv;(u,v)\in {\mathbb{Z}}^2\}\cap {\mathbb{N}}^{\ast }\mathrm{.}$$

L'ensemble $S$ est non vide. En effet, le choix $u=a$ et $v=b$ donne $a^2+b^2$, qui est un entier naturel, et qui est non nul car $a$ et $b$ ne sont pas tous les deux nuls. Donc $a^2+b^2\in S$.

Ainsi $S$ est une partie non vide de ${\mathbb{N}}^{\ast }$ : elle admet un plus petit élément, que nous notons $d$. Par définition de $S$, il existe $(u_0,v_0)\in {\mathbb{Z}}^2$ tel que

$$d=a{u}_0+b{v}_0,d⩾1.$$

Montrons que $d$ divise $a$. Effectuons la division euclidienne de $a$ par $d$ (licite car $d\mathrm{\ne }0$) : $a=dq+r$ avec $0⩽r<d$. Alors

$$r=a-dq=a-q(a{u}_0+b{v}_0)=a(1-q{u}_0)+b(-q{v}_0)\mathrm{.}$$

L'entier $r$ est donc lui aussi une combinaison linéaire entière de $a$ et $b$. Si l'on avait $r>0$, alors $r$ appartiendrait à $S$ tout en vérifiant $r<d$, ce qui contredirait la minimalité de $d$. Donc $r=0$, c'est-à-dire $d\mid a$. Le même raisonnement avec $b$ à la place de $a$ donne $d\mid b$. Ainsi $d$ est un diviseur commun de $a$ et $b$.

Montrons que $d=a\wedge b$. Posons $g=a\wedge b$. D'une part, $d$ est un diviseur commun, donc $d⩽g$ par définition du plus grand élément. D'autre part, $g\mid a$ et $g\mid b$, donc par combinaison linéaire $g\mid (a{u}_0+b{v}_0)=d$ ; comme $d\mathrm{\ne }0$, il vient $\mathrm{\mid }g\mathrm{\mid }⩽\mathrm{\mid }d\mathrm{\mid }$, c'est-à-dire $g⩽d$ puisque $g$ et $d$ sont positifs. Des deux inégalités, $d=g$. $\mathrm{\square }$

Nous pouvons maintenant honorer la dette contractée à la section précédente.

Démonstration (caractérisation des diviseurs communs). Soient $a$, $b$ non tous les deux nuls, $g=a\wedge b$ et $d\in \mathbb{Z}$.

$(⟸)$ Si $d\mid g$ : comme $g$ est un diviseur commun de $a$ et $b$, la transitivité donne $d\mid a$ et $d\mid b$.

$(⟹)$ Si $d\mid a$ et $d\mid b$ : la relation de Bézout fournit $(u_0,v_0)$ tel que $g=a{u}_0+b{v}_0$, et la stabilité par combinaison linéaire donne $d\mid g$. $\mathrm{\square }$

L'algorithme d'Euclide étendu

La démonstration précédente prouve l'existence de $(u,v)$ mais ne les calcule pas. Pour les obtenir, on remonte les lignes de l'algorithme d'Euclide, de la dernière à la première, en exprimant à chaque étape le reste en fonction des deux nombres de la ligne.

Entiers premiers entre eux

Démonstration. $(⟹)$ Si $a\wedge b=1$, la relation de Bézout fournit directement $(u,v)$ tel que $au+bv=a\wedge b=1$.

$(⟸)$ Supposons qu'il existe $(u,v)\in {\mathbb{Z}}^2$ tel que $au+bv=1$. Posons $g=a\wedge b$. Comme $g\mid a$ et $g\mid b$, la stabilité par combinaison linéaire donne $g\mid (au+bv)$, c'est-à-dire $g\mid 1$. Donc $\mathrm{\mid }g\mathrm{\mid }⩽1$, et comme $g⩾1$, on conclut $g=1$. $\mathrm{\square }$

Démonstration. Comme $g\mid a$ et $g\mid b$, les quotients $a^{\mathrm{\prime }}={\displaystyle \frac{a}{g}}$ et $b^{\mathrm{\prime }}={\displaystyle \frac{b}{g}}$ sont bien des entiers, et ils ne sont pas tous les deux nuls (sinon $a=b=0$). La relation de Bézout donne $(u,v)\in {\mathbb{Z}}^2$ tel que $au+bv=g$, c'est-à-dire $g{a}^{\mathrm{\prime }}u+g{b}^{\mathrm{\prime }}v=g$. Comme $g⩾1$, on peut simplifier par $g$ :

$$a^{\mathrm{\prime }}u+b^{\mathrm{\prime }}v=1.$$

D'après le théorème de Bézout, $a^{\mathrm{\prime }}\wedge b^{\mathrm{\prime }}=1$. $\mathrm{\square }$

Le lemme de Gauss

Démonstration. Comme $a\wedge b=1$, le théorème de Bézout fournit $(u,v)\in {\mathbb{Z}}^2$ tel que $au+bv=1$. Multiplions cette égalité par $c$ :

$$acu+bcv=c\mathrm{.}$$

Examinons les deux termes de gauche. D'une part, $a\mid acu$ de façon évidente. D'autre part, $a\mid bc$ par hypothèse, donc $a\mid bcv$. Par stabilité par combinaison linéaire, $a$ divise la somme $acu+bcv$, c'est-à-dire $c$. $\mathrm{\square }$

Les deux corollaires suivants sont exigibles et servent en permanence.

Démonstration. Point 1. Comme $a\mid c$, écrivons $c=ak$ avec $k\in \mathbb{Z}$. Par hypothèse $b\mid c$, c'est-à-dire $b\mid ak$. Or $b\wedge a=a\wedge b=1$ : le lemme de Gauss (appliqué avec $b$ dans le rôle du diviseur) donne $b\mid k$. Écrivons $k=b{k}^{\mathrm{\prime }}$ avec $k^{\mathrm{\prime }}\in \mathbb{Z}$. Alors

$$c=ak=ab{k}^{\mathrm{\prime }},$$

donc $ab\mid c$.

Point 2. Le théorème de Bézout fournit $(u,v)$ tel que $au+bv=1$, et $(u^{\mathrm{\prime }},v^{\mathrm{\prime }})$ tel que $a{u}^{\mathrm{\prime }}+c{v}^{\mathrm{\prime }}=1$. Multiplions ces deux égalités membre à membre :

$$1=(au+bv)(a{u}^{\mathrm{\prime }}+c{v}^{\mathrm{\prime }})=a\underset{\in \mathbb{Z}}{\underbrace{(au{u}^{\mathrm{\prime }}+uc{v}^{\mathrm{\prime }}+bv{u}^{\mathrm{\prime }})}}+(bc)\underset{\in \mathbb{Z}}{\underbrace{\left(v{v}^{\mathrm{\prime }}\right)}}\mathrm{.}$$

On a donc exhibé une combinaison linéaire entière de $a$ et $bc$ valant $1$ : d'après le théorème de Bézout, $a\wedge (bc)=1$. $\mathrm{\square }$

Premiers entre eux deux à deux

Quand on manipule plus de deux entiers, deux notions distinctes apparaissent, et les confondre est une faute classique.

Démonstration. Supposons les entiers premiers entre eux deux à deux, avec $n⩾2$, et soit $d$ un diviseur commun à tous. En particulier $d\mid a_1$ et $d\mid a_2$, donc $d$ est un diviseur commun de $a_1$ et $a_2$, donc $d\mid (a_1\wedge a_2)=1$ d'après la caractérisation des diviseurs communs. Ainsi $d=\pm 1$, et le plus grand diviseur commun vaut $1$.

Pour la réciproque, il suffit d'un contre-exemple, donné ci-dessous. $\mathrm{\square }$

Équations diophantiennes

Une équation diophantienne est une équation dont on cherche uniquement les solutions entières. Le cas linéaire à deux inconnues, $ax+by=c$, se résout complètement avec les outils que nous venons de construire, et c'est un exercice de concours extrêmement fréquent.

Démonstration. $(⟹)$ Si $(x,y)$ est solution, alors $g\mid a$ et $g\mid b$, donc $g\mid (ax+by)=c$ par combinaison linéaire.

$(⟸)$ Si $g\mid c$, écrivons $c=gm$ avec $m\in \mathbb{Z}$. La relation de Bézout fournit $(u,v)$ tel que $au+bv=g$ ; en multipliant par $m$, on obtient $a(um)+b(vm)=gm=c$, donc $(um,vm)$ est solution. $\mathrm{\square }$

PPCM

Symétriquement au PGCD, on s'intéresse maintenant non plus aux diviseurs communs, mais aux multiples communs. La construction suit exactement le même plan : existence par un argument de plus petit élément, caractérisation par divisibilité, puis lien avec le PGCD.

Définition

Démonstration (existence). Notons $M$ l'ensemble des multiples communs strictement positifs de $a$ et $b$. L'entier $\mathrm{\mid }ab\mathrm{\mid }$ appartient à $M$ : il est strictement positif car $a$ et $b$ sont non nuls, et il est multiple de $a$ (car $\mathrm{\mid }ab\mathrm{\mid }=a\times (\pm b)$) comme de $b$. Donc $M$ est une partie non vide de ${\mathbb{N}}^{\ast }$, et admet à ce titre un plus petit élément. $\mathrm{\square }$

Démonstration. Point 1. Par définition, $a\vee b\in {\mathbb{N}}^{\ast }$ donc $a\vee b⩾1$ ; et comme $\mathrm{\mid }ab\mathrm{\mid }$ est un multiple commun strictement positif, la minimalité donne $a\vee b⩽\mathrm{\mid }ab\mathrm{\mid }$.

Point 2. L'ensemble $M$ est symétrique en $a$ et $b$, et un entier est multiple de $a$ si et seulement s'il est multiple de $\mathrm{\mid }a\mathrm{\mid }$.

Point 3. Si $a\mid b$, alors $\mathrm{\mid }b\mathrm{\mid }$ est un multiple commun strictement positif ; et tout multiple commun strictement positif $m$ est en particulier un multiple non nul de $b$, donc vérifie $\mathrm{\mid }b\mathrm{\mid }⩽m$. Donc $\mathrm{\mid }b\mathrm{\mid }$ est le plus petit : $a\vee b=\mathrm{\mid }b\mathrm{\mid }$. Réciproquement, si $a\vee b=\mathrm{\mid }b\mathrm{\mid }$, alors $\mathrm{\mid }b\mathrm{\mid }$ est un multiple de $a$, donc $a\mid b$.

Point 4. Conséquences immédiates du point 3, avec $a\mid a$ et $1\mid a$. $\mathrm{\square }$

Caractérisation des multiples communs

Comme pour le PGCD, le PPCM ne se contente pas d'être le plus petit : il divise tous les multiples communs. La démonstration est un bel exemple d'utilisation de la division euclidienne pour exploiter une minimalité.

Démonstration. $(⟸)$ Supposons $\mu \mid m$. Comme $a\mid \mu$ et $b\mid \mu$ (le PPCM est un multiple commun), la transitivité donne $a\mid m$ et $b\mid m$.

$(⟹)$ Supposons $a\mid m$ et $b\mid m$. Effectuons la division euclidienne de $m$ par $\mu$ (licite car $\mu ⩾1$) : il existe $q\in \mathbb{Z}$ et $r$ tels que

$$m=\mu q+r,0⩽r<\mu \mathrm{.}$$

Alors $r=m-\mu q$. Or $a\mid m$ et $a\mid \mu$, donc $a\mid r$ par combinaison linéaire ; de même $b\mid r$. Ainsi $r$ est un multiple commun de $a$ et $b$. Si l'on avait $r>0$, alors $r$ serait un multiple commun strictement positif vérifiant $r<\mu$, ce qui contredirait la minimalité de $\mu$. Donc $r=0$, c'est-à-dire $\mu \mid m$. $\mathrm{\square }$

La relation entre PGCD et PPCM

Démonstration. Le PGCD comme le PPCM ne dépendent que des valeurs absolues, et $\mathrm{\mid }ab\mathrm{\mid }=\mathrm{\mid }a\mathrm{\mid }\mathrm{\mid }b\mathrm{\mid }$ : on peut donc supposer $a>0$ et $b>0$.

Posons $g=a\wedge b$, puis $a=g{a}^{\mathrm{\prime }}$ et $b=g{b}^{\mathrm{\prime }}$ avec $a^{\mathrm{\prime }},b^{\mathrm{\prime }}\in {\mathbb{N}}^{\ast }$ ; on sait que $a^{\mathrm{\prime }}\wedge b^{\mathrm{\prime }}=1$. Posons enfin

$$m=g{a}^{\mathrm{\prime }}{b}^{\mathrm{\prime }}={\displaystyle \frac{ab}{g}}>0.$$

L'entier $m$ est un multiple commun de $a$ et $b$. En effet $m=(g{a}^{\mathrm{\prime }})b^{\mathrm{\prime }}=a{b}^{\mathrm{\prime }}$ est multiple de $a$, et $m=a^{\mathrm{\prime }}(g{b}^{\mathrm{\prime }})=a^{\mathrm{\prime }}b$ est multiple de $b$.

Tout multiple commun strictement positif de $a$ et $b$ est supérieur ou égal à $m$. Soit $n$ un tel multiple. Comme $a\mid n$, écrivons $n=ak=g{a}^{\mathrm{\prime }}k$ avec $k\in {\mathbb{N}}^{\ast }$. Comme $b\mid n$, il existe $\mathrm{\ell }\in {\mathbb{N}}^{\ast }$ tel que $g{a}^{\mathrm{\prime }}k=n=g{b}^{\mathrm{\prime }}\mathrm{\ell }$ ; en simplifiant par $g⩾1$, il vient $a^{\mathrm{\prime }}k=b^{\mathrm{\prime }}\mathrm{\ell }$, autrement dit $b^{\mathrm{\prime }}\mid a^{\mathrm{\prime }}k$. Or $b^{\mathrm{\prime }}\wedge a^{\mathrm{\prime }}=1$ : le lemme de Gauss donne $b^{\mathrm{\prime }}\mid k$. Écrivons $k=b^{\mathrm{\prime }}{k}^{\mathrm{\prime }}$ avec $k^{\mathrm{\prime }}\in {\mathbb{N}}^{\ast }$. Alors

$$n=g{a}^{\mathrm{\prime }}{b}^{\mathrm{\prime }}{k}^{\mathrm{\prime }}=m{k}^{\mathrm{\prime }}⩾m,$$

puisque $k^{\mathrm{\prime }}⩾1$.

L'entier $m$ est donc le plus petit multiple commun strictement positif : $a\vee b=m={\displaystyle \frac{ab}{g}}$. En multipliant par $g$, il vient $(a\wedge b)(a\vee b)=ab=\mathrm{\mid }ab\mathrm{\mid }$. $\mathrm{\square }$

Démonstration. Le théorème précédent donne $(a\wedge b)(a\vee b)=\mathrm{\mid }ab\mathrm{\mid }$, avec $a\wedge b⩾1$ et $a\vee b⩾1$. Si $a\wedge b=1$, on obtient immédiatement $a\vee b=\mathrm{\mid }ab\mathrm{\mid }$. Réciproquement, si $a\vee b=\mathrm{\mid }ab\mathrm{\mid }$, alors $(a\wedge b)\times \mathrm{\mid }ab\mathrm{\mid }=\mathrm{\mid }ab\mathrm{\mid }$, et comme $\mathrm{\mid }ab\mathrm{\mid }\mathrm{\ne }0$ on peut simplifier : $a\wedge b=1$. $\mathrm{\square }$

Nombres premiers

Tout ce qui précède — divisibilité, division euclidienne, PGCD, Bézout, Gauss — décrit des relations entre entiers, mais ne dit rien de la façon dont un entier est fabriqué. Nous abordons maintenant les briques élémentaires de la multiplication : les nombres premiers. Le programme de cette section est simple à énoncer et beaucoup moins simple à démontrer : montrer qu'il y a assez de briques (il en existe une infinité), savoir reconnaître une brique (test de primalité), et surtout établir la propriété qui fait toute leur force, le lemme d'Euclide, dont découlera l'unicité de la décomposition.

Définition et premiers exemples

Un entier $p⩾2$ admet toujours $1$ et $p$ pour diviseurs positifs : la définition demande donc exactement qu'il n'en ait pas d'autre. Dans $\mathbb{Z}$, les diviseurs de $p$ premier sont les quatre entiers $1$, $-1$, $p$ et $-p$ ; on se restreint aux diviseurs positifs pour ne pas alourdir les énoncés, et par convention un nombre premier est toujours un entier naturel.

Démonstration. Puisque $n$ n'est pas premier et que $n⩾2$, il admet un diviseur positif $a$ différent de $1$ et de $n$. Comme $a\mid n$ et $n>0$, on a $1⩽a⩽n$, donc $2⩽a⩽n-1$. Posons $b=n\mathrm{/}a$, qui est un entier puisque $a\mid n$. De $n=ab$ avec $a⩾2$ on tire $b=n\mathrm{/}a⩽n\mathrm{/}2⩽n-1$ (car $n⩾2$), et de $a⩽n-1<n$ on tire $b=n\mathrm{/}a>1$, donc $b⩾2$. $\mathrm{\square }$

Tout entier supérieur ou égal à 2 admet un diviseur premier

Ce lemme est le point de départ de tout le reste : c'est lui qui garantit que les nombres premiers ne sont pas une curiosité rare, mais qu'ils atteignent tous les entiers.

Démonstration. Soit $n⩾2$. Considérons l'ensemble

$$D=\{d\in \mathbb{N}:d⩾2\text{ et }d\mid n\}\mathrm{.}$$

Cet ensemble est une partie de $\mathbb{N}$, et il est non vide puisque $n\in D$ (en effet $n⩾2$ et $n\mid n$). Toute partie non vide de $\mathbb{N}$ admet un plus petit élément : notons $p=\min D$.

Montrons que $p$ est premier. D'abord $p⩾2$ par définition de $D$. Soit ensuite $d$ un diviseur positif de $p$ tel que $d\mathrm{\ne }1$ et $d\mathrm{\ne }p$. Alors $d⩾2$, et par transitivité de la divisibilité, $d\mid p$ et $p\mid n$ entraînent $d\mid n$ : donc $d\in D$. Or $d\mid p$ avec $p>0$ et $d\mathrm{\ne }p$ donne $d<p$, ce qui contredit la minimalité de $p$. Un tel $d$ n'existe donc pas : les seuls diviseurs positifs de $p$ sont $1$ et $p$, et $p$ est premier.

Comme $p\mid n$, l'entier $n$ admet bien un diviseur premier. $\mathrm{\square }$

L'infinité des nombres premiers

Démonstration. Raisonnons par l'absurde et supposons $\mathcal{P}$ fini. Cet ensemble est non vide (il contient $2$), on peut donc écrire

$$\mathcal{P}=\{p_1,p_2,\dots ,p_r\}$$

avec $r⩾1$. Posons

$$N=p_1{p}_2\cdots p_r+1.$$

Chaque $p_i$ vaut au moins $2$, donc $N⩾2+1=3$, et en particulier $N⩾2$. D'après le lemme précédent, $N$ admet un diviseur premier $q$. Comme $q\in \mathcal{P}$, il existe un indice $i$ tel que $q=p_i$, donc $q$ divise le produit $p_1{p}_2\cdots p_r$.

Ainsi $q$ divise $N$ et $q$ divise $p_1{p}_2\cdots p_r$ : il divise donc leur différence, c'est-à-dire

$$q\mid N-p_1{p}_2\cdots p_r=1.$$

Un diviseur positif de $1$ vaut $1$, donc $q=1$, ce qui contredit $q⩾2$. L'hypothèse « $\mathcal{P}$ est fini » est donc absurde. $\mathrm{\square }$

Reconnaître un nombre premier

Tester si $n$ est premier en essayant tous les entiers de $2$ à $n-1$ est possible mais absurdement long. Deux observations divisent radicalement le travail : il suffit de tester des diviseurs premiers, et il suffit de les tester jusqu'à $\sqrt{n}$.

Démonstration. Comme $n$ est composé, on peut écrire $n=ab$ avec $2⩽a⩽n-1$ et $2⩽b⩽n-1$. Quitte à échanger les rôles de $a$ et $b$, supposons $a⩽b$. Alors

$$a^2⩽ab=n,$$

et comme $a>0$, on en déduit $a⩽\sqrt{n}$ par croissance de la fonction racine carrée sur ${\mathbb{R}}_{+}$.

L'entier $a$ vérifie $a⩾2$, il admet donc un diviseur premier $p$. Comme $p\mid a$ et $a>0$, on a $p⩽a⩽\sqrt{n}$, et par transitivité $p\mid a$ et $a\mid n$ donnent $p\mid n$. $\mathrm{\square }$

Le crible d'Ératosthène

Pour dresser la liste de tous les nombres premiers inférieurs à un entier $N$, il est plus économique de procéder par élimination que de tester les entiers un par un. Le principe, dû à Ératosthène, est le suivant : on écrit les entiers de $2$ à $N$ ; on entoure le plus petit entier non barré (c'est $2$), et on barre tous ses multiples stricts ; on recommence avec le plus petit entier ni barré ni entouré, et ainsi de suite. D'après le test précédent, on peut s'arrêter dès que le nombre entouré dépasse $\sqrt{N}$ : tous les entiers restants sont alors premiers. On peut de plus commencer le barrage à $p^2$, car un multiple $kp$ avec $k<p$ a déjà été barré lors du traitement d'un facteur premier de $k$.

Le lemme d'Euclide

Voici la propriété qui distingue vraiment les nombres premiers des autres entiers. Elle repose entièrement sur le lemme de Gauss, établi dans la première partie.

Démonstration. Posons $d=p\wedge a$. Par définition, $d$ est un diviseur positif de $p$, donc $d=1$ ou $d=p$ puisque $p$ est premier. Si $d=p$, alors $p=d$ divise $a$ (car $d\mid a$). Sinon $d=1$, c'est-à-dire $p\wedge a=1$. $\mathrm{\square }$

Démonstration. Supposons $p\mid ab$ et $p\nmid a$. D'après la propriété précédente, $p\wedge a=1$. Le lemme de Gauss appliqué à $p\mid ab$ avec $p\wedge a=1$ donne alors $p\mid b$. On a donc bien « $p\mid a$ ou $p\mid b$ ».

Démontrons la généralisation par récurrence sur $n⩾1$. Notons $H(n)$ la proposition : « pour tous entiers $a_1,\dots ,a_n$, si $p\mid a_1\cdots a_n$ alors $p$ divise l'un des $a_i$ ».

Initialisation. $H(1)$ est immédiate : si $p\mid a_1$, alors $p$ divise $a_1$.

Hérédité. Soit $n⩾1$ tel que $H(n)$ soit vraie, et soient $a_1,\dots ,a_{n+1}$ des entiers tels que $p\mid a_1\cdots a_{n+1}$. Écrivons ce produit sous la forme $(a_1\cdots a_n)\times a_{n+1}$ : le cas de deux facteurs donne $p\mid a_1\cdots a_n$ ou $p\mid a_{n+1}$. Dans le second cas, c'est terminé. Dans le premier, l'hypothèse de récurrence fournit un indice $i\in \{1,\dots ,n\}$ tel que $p\mid a_i$. Donc $H(n+1)$ est vraie.

Conclusion. Par récurrence, $H(n)$ est vraie pour tout $n⩾1$.

Pour la conséquence, il suffit d'appliquer la généralisation à $a_1=a_2=\cdots =a_n=a$ : si $p\mid a^n$, alors $p$ divise l'un des facteurs, qui vaut $a$. $\mathrm{\square }$

Décomposition en produit de facteurs premiers

Nous disposons maintenant de tout ce qu'il faut pour démontrer le théorème central de l'arithmétique : les nombres premiers sont les briques de la multiplication, et l'assemblage d'un entier à partir de ces briques est unique.

Démonstration. Nous démontrons d'abord que tout entier $n⩾2$ est un produit de nombres premiers (éventuellement répétés), puis l'unicité d'un tel produit à l'ordre près ; le regroupement des facteurs égaux et leur rangement dans l'ordre croissant donnent alors exactement l'énoncé.

Existence, par récurrence forte. Pour $n⩾2$, notons $E(n)$ la proposition : « $n$ s'écrit comme un produit d'un nombre fini de nombres premiers ». Soit $n⩾2$, et supposons $E(m)$ vraie pour tout entier $m$ tel que $2⩽m<n$.

• Si $n$ est premier, alors $n$ est un produit d'un seul facteur premier, et $E(n)$ est vraie.
• Sinon, $n$ est composé et s'écrit $n=ab$ avec $2⩽a⩽n-1$ et $2⩽b⩽n-1$. Les entiers $a$ et $b$ vérifient donc $2⩽a<n$ et $2⩽b<n$ : par hypothèse de récurrence, $a$ et $b$ sont des produits de nombres premiers, disons $a=q_1\cdots q_s$ et $b=q_1^{\mathrm{\prime }}\cdots q_t^{\mathrm{\prime }}$. Alors

$$n=q_1\cdots q_s{q}_1^{\mathrm{\prime }}\cdots q_t^{\mathrm{\prime }}$$

est un produit de nombres premiers, et $E(n)$ est vraie.

Par récurrence forte, $E(n)$ est vraie pour tout $n⩾2$.

Unicité, par récurrence forte. Notons $U(n)$ la proposition : « si $n=p_1{p}_2\cdots p_s=q_1{q}_2\cdots q_t$ où les $p_i$ et les $q_j$ sont premiers, rangés dans l'ordre croissant au sens large, alors $s=t$ et $p_i=q_i$ pour tout $i\in \{1,\dots ,s\}$ ». Soit $n⩾2$, supposons $U(m)$ vraie pour tout $m$ tel que $2⩽m<n$, et donnons-nous deux telles écritures de $n$.

Le nombre premier $p_1$ divise $n=q_1{q}_2\cdots q_t$. D'après la généralisation du lemme d'Euclide, il existe un indice $j$ tel que $p_1\mid q_j$. Or $q_j$ est premier et $p_1⩾2$ : le seul diviseur de $q_j$ supérieur ou égal à $2$ est $q_j$ lui-même, donc $p_1=q_j⩾q_1$ (les $q$ étant rangés dans l'ordre croissant). En échangeant les rôles des deux écritures, on obtient de même $q_1⩾p_1$. Donc

$$p_1=q_1\mathrm{.}$$

Posons $m=n\mathrm{/}{p}_1$, qui est un entier puisque $p_1\mid n$. En simplifiant les deux écritures par $p_1=q_1$ (licite car $p_1\mathrm{\ne }0$), il vient

$$m=p_2\cdots p_s=q_2\cdots q_t\mathrm{.}$$

• Si $m=1$ : un produit de nombres premiers, tous supérieurs ou égaux à $2$, ne peut valoir $1$ que s'il est vide. Donc $s-1=0$ et $t-1=0$, c'est-à-dire $s=t=1$, et l'égalité $p_1=q_1$ conclut.
• Si $m⩾2$ : comme $p_1⩾2$, on a $m=n\mathrm{/}{p}_1⩽n\mathrm{/}2<n$, donc $2⩽m<n$ et l'hypothèse de récurrence $U(m)$ s'applique aux deux écritures de $m$ : elle donne $s-1=t-1$ et $p_i=q_i$ pour tout $i\in \{2,\dots ,s\}$. Avec $p_1=q_1$, on obtient $s=t$ et $p_i=q_i$ pour tout $i$.

Par récurrence forte, $U(n)$ est vraie pour tout $n⩾2$. $\mathrm{\square }$

Valuation p-adique

La valuation $v_p(a)$ mesure donc « combien de fois $p$ entre dans $a$ ». Les propriétés suivantes en font un outil de calcul, et non une simple notation.

Démonstration. Point 1. Si $k⩽v$, alors $p^k\mid p^v$ et $p^v\mid a$ (car $v\in E$), donc $p^k\mid a$ par transitivité. Réciproquement, si $p^k\mid a$, alors $k\in E$, donc $k⩽\max E=v$.

Point 2. Comme $p^v\mid a$, il existe $b\in \mathbb{Z}$ tel que $a=p^{v}b$. Si l'on avait $p\mid b$, on pourrait écrire $b=p{b}^{\mathrm{\prime }}$, d'où $a=p^{v+1}{b}^{\mathrm{\prime }}$ et donc $p^{v+1}\mid a$ : le point 1 donnerait $v+1⩽v$, ce qui est absurde. Donc $p\nmid b$.

Point 3. Supposons $a=p^{k}c$ avec $p\nmid c$. D'une part $p^k\mid a$, donc $k⩽v$ d'après le point 1. D'autre part, si l'on avait $k<v$, alors $p^{k+1}\mid a=p^{k}c$, et en simplifiant par $p^k$ (qui est non nul) on obtiendrait $p\mid c$, ce qui est exclu. Donc $k=v$.

Point 4. $v_p(a)=0$ signifie que $1$ est la plus grande puissance de $p$ divisant $a$, c'est-à-dire que $p^1\nmid a$, soit $p\nmid a$. Enfin, si $p\mid a$ alors $p⩽\mathrm{\mid }a\mathrm{\mid }$ : seuls les nombres premiers inférieurs ou égaux à $\mathrm{\mid }a\mathrm{\mid }$ peuvent avoir une valuation non nulle, et ils sont en nombre fini.

Point 5. Fixons $i$ et posons $m={\prod }_{j\mathrm{\ne }i}{p}_j^{{\alpha }_j}$, de sorte que $n=p_i^{{\alpha }_i}m$. Si l'on avait $p_i\mid m$, la généralisation du lemme d'Euclide fournirait un indice $j\mathrm{\ne }i$ tel que $p_i\mid p_j$, donc $p_i=p_j$ (deux nombres premiers dont l'un divise l'autre sont égaux), ce qui contredit $p_1<\cdots <p_r$. Donc $p_i\nmid m$, et le point 3 donne $v_{p_i}(n)={\alpha }_i$. Si maintenant $p$ est un premier distinct de tous les $p_j$, le même argument montre que $p\nmid n$, donc $v_p(n)=0$ d'après le point 4. L'égalité $n={\prod }_p{p}^{v_p(n)}$ n'est alors qu'une réécriture de la décomposition primaire. $\mathrm{\square }$

Démonstration. Produit. Posons $\alpha =v_p(a)$ et $\beta =v_p(b)$. D'après le point 2 de la propriété précédente, on peut écrire $a=p^{\alpha }{a}^{\mathrm{\prime }}$ et $b=p^{\beta }{b}^{\mathrm{\prime }}$ avec $p\nmid a^{\mathrm{\prime }}$ et $p\nmid b^{\mathrm{\prime }}$. Alors

$$ab=p^{\alpha +\beta }{a}^{\mathrm{\prime }}{b}^{\mathrm{\prime }}\mathrm{.}$$

Or $p\nmid a^{\mathrm{\prime }}{b}^{\mathrm{\prime }}$ : dans le cas contraire, le lemme d'Euclide donnerait $p\mid a^{\mathrm{\prime }}$ ou $p\mid b^{\mathrm{\prime }}$, ce qui est exclu. Le point 3 de la propriété précédente s'applique donc et donne $v_p(ab)=\alpha +\beta$.

La formule $v_p(a^n)=n{v}_p(a)$ s'en déduit par récurrence sur $n$. Elle est vraie pour $n=0$ car $v_p(1)=0$ ($p\nmid 1$). Si elle est vraie au rang $n$, alors $v_p(a^{n+1})=v_p(a^n\times a)=v_p(a^n)+v_p(a)=n{v}_p(a)+v_p(a)=(n+1)v_p(a)$.

Somme. Notons encore $\alpha =v_p(a)$, $\beta =v_p(b)$ et $m=\min (\alpha ,\beta )$. Comme $m⩽\alpha$ et $m⩽\beta$, le point 1 donne $p^m\mid a$ et $p^m\mid b$, donc $p^m\mid a+b$, et le point 1 appliqué à $a+b$ donne $m⩽v_p(a+b)$ : c'est l'inégalité annoncée.

Supposons maintenant $\alpha \mathrm{\ne }\beta$, par exemple $\alpha <\beta$ (le cas $\beta <\alpha$ est identique en échangeant $a$ et $b$). Écrivons $a=p^{\alpha }{a}^{\mathrm{\prime }}$ avec $p\nmid a^{\mathrm{\prime }}$, et $b=p^{\beta }{b}^{\mathrm{\prime }}=p^{\alpha }\left(p^{\beta -\alpha }{b}^{\mathrm{\prime }}\right)$, ce qui a un sens car $\beta -\alpha ⩾1$. Alors

$$a+b=p^{\alpha }(a^{\mathrm{\prime }}+p^{\beta -\alpha }{b}^{\mathrm{\prime }})\mathrm{.}$$

Posons $c=a^{\mathrm{\prime }}+p^{\beta -\alpha }{b}^{\mathrm{\prime }}$. Comme $\beta -\alpha ⩾1$, $p$ divise $p^{\beta -\alpha }{b}^{\mathrm{\prime }}$. Si $p$ divisait $c$, il diviserait la différence $c-p^{\beta -\alpha }{b}^{\mathrm{\prime }}=a^{\mathrm{\prime }}$, ce qui est faux. Donc $p\nmid c$, et le point 3 donne $v_p(a+b)=\alpha =\min (\alpha ,\beta )$. $\mathrm{\square }$

Les valuations transforment les questions de divisibilité en questions d'inégalités entre entiers naturels, ce qui est beaucoup plus maniable.

Démonstration. Point 1. Si $a\mid b$, écrivons $b=ac$ avec $c⩾1$. Alors, pour tout premier $p$, $v_p(b)=v_p(a)+v_p(c)⩾v_p(a)$ car $v_p(c)⩾0$. Réciproquement, supposons $v_p(a)⩽v_p(b)$ pour tout $p$, et posons

$$c=\prod _{p\in \mathcal{P}}{p}^{v_p(b)-v_p(a)}\mathrm{.}$$

Les exposants sont des entiers naturels par hypothèse, et ils sont nuls sauf pour un nombre fini de $p$ : $c$ est donc un entier supérieur ou égal à $1$ bien défini. Alors

$$ac=\prod _p{p}^{v_p(a)}\times \prod _p{p}^{v_p(b)-v_p(a)}=\prod _p{p}^{v_p(b)}=b,$$

donc $a\mid b$.

Point 2. Posons $d={\prod }_p{p}^{\min (v_p(a),v_p(b))}$ (produit fini, comme ci-dessus). Pour tout premier $p$, $v_p(d)=\min (v_p(a),v_p(b))⩽v_p(a)$ et $⩽v_p(b)$, donc $d\mid a$ et $d\mid b$ d'après le point 1 : $d$ est un diviseur commun de $a$ et $b$. Soit maintenant $c⩾1$ un diviseur commun quelconque : pour tout $p$, $v_p(c)⩽v_p(a)$ et $v_p(c)⩽v_p(b)$, donc $v_p(c)⩽\min (v_p(a),v_p(b))=v_p(d)$, et le point 1 donne $c\mid d$, donc $c⩽d$. Ainsi $d$ est le plus grand des diviseurs communs : $d=a\wedge b$.

Le raisonnement pour le PPCM est symétrique : en posant $m={\prod }_p{p}^{\max (v_p(a),v_p(b))}$, on obtient $a\mid m$ et $b\mid m$, et tout multiple commun $M⩾1$ vérifie $v_p(M)⩾\max (v_p(a),v_p(b))=v_p(m)$ pour tout $p$, donc $m\mid M$ et $m⩽M$ : $m$ est le plus petit des multiples communs strictement positifs, c'est-à-dire $a\vee b$.

Point 3. Pour tous réels $x$ et $y$, $\min (x,y)+\max (x,y)=x+y$. Donc, pour tout premier $p$,

$$v_p((a\wedge b)(a\vee b))=\min (v_p(a),v_p(b))+\max (v_p(a),v_p(b))=v_p(a)+v_p(b)=v_p(ab)\mathrm{.}$$

Deux entiers supérieurs ou égaux à $1$ ayant les mêmes valuations pour tout premier sont égaux (chacun divise l'autre d'après le point 1), d'où $(a\wedge b)(a\vee b)=ab$. Enfin $a\wedge b=1$ équivaut à $\min (v_p(a),v_p(b))=0$ pour tout $p$, c'est-à-dire à l'absence de facteur premier commun. $\mathrm{\square }$

Démonstration. Point 1. Soit $d⩾1$. D'après la caractérisation de la divisibilité par les valuations, $d\mid n$ équivaut à : $v_p(d)⩽v_p(n)$ pour tout premier $p$. Or $v_p(n)=0$ si $p\mathrm{\notin }\{p_1,\dots ,p_r\}$ : la condition impose alors $v_p(d)=0$, c'est-à-dire que $d$ n'a pas d'autre facteur premier que les $p_i$. Et pour $p=p_i$, la condition s'écrit $v_{p_i}(d)⩽{\alpha }_i$. Donc $d\mid n$ équivaut à $d={\prod }_i{p}_i^{{\beta }_i}$ avec $0⩽{\beta }_i⩽{\alpha }_i$.

Deux familles d'exposants distinctes $({\beta }_i)$ et $({\beta }_i^{\mathrm{\prime }})$ donnent deux diviseurs distincts, puisque les exposants se retrouvent à partir du diviseur par ${\beta }_i=v_{p_i}(d)$. Compter les diviseurs revient donc à compter les familles $({\beta }_1,\dots ,{\beta }_r)$ : il y a ${\alpha }_1+1$ valeurs possibles pour ${\beta }_1$, ${\alpha }_2+1$ pour ${\beta }_2$, et ainsi de suite, les choix étant indépendants. Le nombre de diviseurs positifs de $n$ est donc ${\prod }_{i=1}^r({\alpha }_i+1)$.

Point 2. Si $n=m^2$ avec $m⩾1$, alors $v_p(n)=2v_p(m)$ pour tout $p$ : toutes les valuations sont paires. Réciproquement, si toutes les valuations de $n$ sont paires, posons $m={\prod }_p{p}^{v_p(n)\mathrm{/}2}$, qui est bien un entier (les exposants $v_p(n)\mathrm{/}2$ sont des entiers naturels presque tous nuls). Alors $m^2={\prod }_p{p}^{v_p(n)}=n$. $\mathrm{\square }$

Congruences

Les valuations regardent un entier par ses facteurs. Les congruences le regardent par son reste : on décide de ne plus distinguer deux entiers qui ont le même reste dans la division par $n$. C'est l'outil le plus rentable du chapitre, parce qu'il transforme des calculs gigantesques en calculs sur quelques valeurs.

Démonstration. Point 1. Écrivons les divisions euclidiennes $a=n{q}_1+r_1$ et $b=n{q}_2+r_2$ avec $0⩽r_1⩽n-1$ et $0⩽r_2⩽n-1$. Alors

$$b-a=n(q_2-q_1)+(r_2-r_1)\mathrm{.}$$

Comme $n$ divise $n(q_2-q_1)$, on a $n\mid b-a$ si et seulement si $n\mid r_2-r_1$. Or $-(n-1)⩽r_2-r_1⩽n-1$, donc $\mathrm{\mid }{r}_2-r_1\mathrm{\mid }<n$ : le seul multiple de $n$ dans cet intervalle est $0$. Ainsi $n\mid b-a$ équivaut à $r_2=r_1$.

Point 2. De $a=nq+r$ on tire $r-a=-nq$, donc $n\mid r-a$, c'est-à-dire $a\equiv r[n]$.

Point 3. L'existence vient du point 2. Pour l'unicité, si $a\equiv r[n]$ et $a\equiv r^{\mathrm{\prime }}[n]$ avec $r,r^{\mathrm{\prime }}\in \{0,\dots ,n-1\}$, alors $n\mid r^{\mathrm{\prime }}-r$ et $\mathrm{\mid }{r}^{\mathrm{\prime }}-r\mathrm{\mid }<n$, donc $r=r^{\mathrm{\prime }}$.

Point 4. C'est la définition avec $b=0$ : $n\mid 0-a$ équivaut à $n\mid a$. $\mathrm{\square }$

Démonstration. Réflexivité. $a-a=0=0\times n$, donc $n\mid a-a$.

Symétrie. Si $n\mid b-a$, écrivons $b-a=kn$ ; alors $a-b=(-k)n$, donc $n\mid a-b$.

Transitivité. Si $b-a=kn$ et $c-b=k^{\mathrm{\prime }}n$, alors, en additionnant, $c-a=(k+k^{\mathrm{\prime }})n$, donc $n\mid c-a$. $\mathrm{\square }$

C'est la propriété suivante qui rend les congruences réellement utiles : elles se comportent comme des égalités vis-à-vis de l'addition et de la multiplication.

Démonstration. Par hypothèse, il existe $u,v\in \mathbb{Z}$ tels que $b-a=un$ et $d-c=vn$.

Point 1. $(b+d)-(a+c)=(b-a)+(d-c)=(u+v)n$, donc $n\mid (b+d)-(a+c)$. De même $(b-d)-(a-c)=(u-v)n$.

Point 2. Le calcul consiste à faire apparaître les deux différences en insérant un terme intermédiaire :

$$bd-ac=bd-bc+bc-ac=b(d-c)+c(b-a)=bvn+cun=(bv+cu)n\mathrm{.}$$

Donc $n\mid bd-ac$, c'est-à-dire $ac\equiv bd[n]$.

Point 3. Récurrence sur $k$. Pour $k=0$, $a^0=1=b^0$ et $1\equiv 1[n]$. Supposons $a^k\equiv b^k[n]$ ; en appliquant le point 2 aux congruences $a^k\equiv b^k[n]$ et $a\equiv b[n]$, on obtient $a^k\times a\equiv b^k\times b[n]$, soit $a^{k+1}\equiv b^{k+1}[n]$.

Point 4. C'est le point 2 appliqué à $c=d=\lambda$, la congruence $\lambda \equiv \lambda [n]$ étant vraie par réflexivité. $\mathrm{\square }$

Il existe cependant une règle de simplification correcte, et elle a une hypothèse précise.

Démonstration. Supposons $ca\equiv cb[n]$, c'est-à-dire $n\mid cb-ca=c(b-a)$. Comme $n\wedge c=1$, le lemme de Gauss donne $n\mid b-a$, c'est-à-dire $a\equiv b[n]$. $\mathrm{\square }$

Calculer le reste d'une grande puissance

Critères de divisibilité

Les critères appris au collège ne sont pas des recettes : ce sont des congruences déguisées, et leur démonstration tient en deux lignes une fois l'écriture décimale posée.

Démonstration. On a $10=9+1\equiv 1[9]$, donc ${10}^k\equiv 1^k\equiv 1[9]$ pour tout $k$ par compatibilité avec les puissances. En multipliant par $a_k$, il vient $a_k{10}^k\equiv a_k[9]$. La compatibilité avec l'addition, étendue à une somme de $m+1$ termes par une récurrence immédiate sur le nombre de termes, donne alors

$$n=\sum _{k=0}^m{a}_k{10}^k\equiv \sum _{k=0}^m{a}_k[9]\mathrm{.}$$

Le raisonnement est identique modulo $3$, puisque $10\equiv 1[3]$.

Modulo $11$, on a $10=11-1\equiv -1[11]$, donc ${10}^k\equiv (-1{)}^k[11]$, puis $a_k{10}^k\equiv (-1{)}^k{a}_k[11]$ et enfin $n\equiv {\sum }_k(-1{)}^k{a}_k[11]$.

Les critères s'en déduisent : $n$ est divisible par $9$ si et seulement si $n\equiv 0[9]$, c'est-à-dire si et seulement si $\sum a_k\equiv 0[9]$, par transitivité. $\mathrm{\square }$

Congruences linéaires

Résoudre $ax\equiv b[n]$, c'est chercher tous les entiers $x$ vérifiant cette congruence. Le lien avec la première partie est direct : cette congruence signifie qu'il existe $k\in \mathbb{Z}$ tel que $ax-b=kn$, c'est-à-dire que $(x,-k)$ est solution de l'équation diophantienne $ax-kn=b$.

Démonstration. Point 1. Comme $a\wedge n=1$, le théorème de Bézout fournit deux entiers $u$ et $v$ tels que $au+nv=1$. Alors $au-1=-nv$, donc $n\mid au-1$, c'est-à-dire $au\equiv 1[n]$.

Pour l'unicité modulo $n$ : si $au\equiv 1[n]$ et $a{u}^{\mathrm{\prime }}\equiv 1[n]$, alors $au\equiv a{u}^{\mathrm{\prime }}[n]$ par symétrie et transitivité ; comme $a\wedge n=1$, la règle de simplification donne $u\equiv u^{\mathrm{\prime }}[n]$.

Point 2. Supposons $ax\equiv b[n]$. En multipliant par $u$ (compatibilité avec la multiplication), $uax\equiv ub[n]$. Or $ua\equiv 1[n]$, donc $uax\equiv x[n]$, et par transitivité $x\equiv ub[n]$.

Réciproquement, si $x\equiv ub[n]$, alors en multipliant par $a$ : $ax\equiv aub[n]$, et comme $au\equiv 1[n]$ on obtient $aub\equiv b[n]$, d'où $ax\equiv b[n]$ par transitivité. $\mathrm{\square }$

Démonstration. L'équation $ax\equiv b[n]$ équivaut à l'existence d'un entier $k$ tel que $ax-nk=b$. D'après l'étude des équations diophantiennes de la première partie, cette équation a des solutions si et seulement si $(a\wedge n)\mid b$, c'est-à-dire $d\mid b$, d'où le premier point.

Supposons $d\mid b$ et écrivons $a=d{a}^{\mathrm{\prime }}$, $b=d{b}^{\mathrm{\prime }}$, $n=d{n}^{\mathrm{\prime }}$ ; on sait que $a^{\mathrm{\prime }}\wedge n^{\mathrm{\prime }}=1$. Alors, pour $x\in \mathbb{Z}$,

$$n\mid ax-b⟺d{n}^{\mathrm{\prime }}\mid d(a^{\mathrm{\prime }}x-b^{\mathrm{\prime }})⟺n^{\mathrm{\prime }}\mid a^{\mathrm{\prime }}x-b^{\mathrm{\prime }},$$

la dernière équivalence venant de la simplification par $d\mathrm{\ne }0$ dans la relation de divisibilité. On est ramené à $a^{\mathrm{\prime }}x\equiv b^{\mathrm{\prime }}[n^{\mathrm{\prime }}]$ avec $a^{\mathrm{\prime }}\wedge n^{\mathrm{\prime }}=1$, dont la propriété précédente donne les solutions : $x\equiv u{b}^{\mathrm{\prime }}[n^{\mathrm{\prime }}]$ où $u$ est un inverse de $a^{\mathrm{\prime }}$ modulo $n^{\mathrm{\prime }}$. $\mathrm{\square }$

Petit théorème de Fermat

Ce théorème donne gratuitement l'exposant que l'on cherchait « à la main » dans la méthode des grandes puissances, à condition que le module soit premier. Sa démonstration repose sur une propriété des coefficients binomiaux, que nous établissons d'abord.

Démonstration. Partons de la relation entre coefficients binomiaux, valable pour $1⩽k⩽p$ :

$$k\left(\genfrac{}{}{0px}{}{p}{k}\right)=k\times {\displaystyle \frac{p!}{k!(p-k)!}}={\displaystyle \frac{p!}{(k-1)!(p-k)!}}=p\times {\displaystyle \frac{(p-1)!}{(k-1)!((p-1)-(k-1))!}}=p\left(\genfrac{}{}{0px}{}{p-1}{k-1}\right),$$

où l'on a utilisé $(p-1)-(k-1)=p-k$. Il en résulte que $p$ divise $k\left(\genfrac{}{}{0px}{}{p}{k}\right)$.

Soit maintenant $k\in \{1,\dots ,p-1\}$. Comme $1⩽k⩽p-1<p$ et $k⩾1$, l'entier $p$ ne divise pas $k$ (un multiple non nul de $p$ est de valeur absolue supérieure ou égale à $p$). D'après la propriété « $p\mid a$ ou $p\wedge a=1$ » établie au début de la section « Le lemme d'Euclide », $p$ premier et $p\nmid k$ entraînent $p\wedge k=1$. Le lemme de Gauss appliqué à $p\mid k\left(\genfrac{}{}{0px}{}{p}{k}\right)$ avec $p\wedge k=1$ donne alors

$$p\mid \left(\genfrac{}{}{0px}{}{p}{k}\right)\mathrm{.}\mathrm{\square }$$

Démonstration. Étape 1 : le cas $a\in \mathbb{N}$, par récurrence. Notons $F(a)$ la proposition « $a^p\equiv a[p]$ ».

Initialisation. $0^p=0\equiv 0[p]$ (rappelons que $p⩾2$, donc $0^p$ a bien un sens et vaut $0$). Donc $F(0)$ est vraie.

Hérédité. Soit $a\in \mathbb{N}$ tel que $F(a)$ soit vraie. La formule du binôme de Newton donne

$$(a+1{)}^p=\sum _{k=0}^p\left(\genfrac{}{}{0px}{}{p}{k}\right)a^k=a^p+\sum _{k=1}^{p-1}\left(\genfrac{}{}{0px}{}{p}{k}\right)a^k+1.$$

Chaque terme de la somme centrale est divisible par $p$ d'après le lemme précédent, donc cette somme est elle-même divisible par $p$ : elle est congrue à $0$ modulo $p$. Par compatibilité de la congruence avec l'addition,

$$(a+1{)}^p\equiv a^p+0+1\equiv a^p+1[p]\mathrm{.}$$

L'hypothèse de récurrence donne $a^p\equiv a[p]$, donc $a^p+1\equiv a+1[p]$, et par transitivité

$$(a+1{)}^p\equiv a+1[p]\mathrm{.}$$

Donc $F(a+1)$ est vraie.

Conclusion partielle. Par récurrence, $a^p\equiv a[p]$ pour tout $a\in \mathbb{N}$.

Étape 2 : le cas $a<0$. Écrivons $a=-b$ avec $b\in \mathbb{N}$, de sorte que $b^p\equiv b[p]$ d'après l'étape 1.

• Si $p$ est impair, alors $a^p=(-b{)}^p=-b^p$, et de $b^p\equiv b[p]$ on tire $-b^p\equiv -b[p]$ (compatibilité avec la multiplication par $-1$), c'est-à-dire $a^p\equiv a[p]$.
• Si $p=2$, alors $a^2-a=a(a-1)$ est le produit de deux entiers consécutifs, donc l'un des deux est pair et le produit aussi : $2\mid a^2-a$, c'est-à-dire $a^2\equiv a[2]$. (Cet argument vaut d'ailleurs pour tout $a\in \mathbb{Z}$.)

Dans tous les cas, $a^p\equiv a[p]$ pour tout $a\in \mathbb{Z}$ : le premier point est démontré.

Étape 3 : passage à la seconde forme. Supposons $p\nmid a$. De $a^p\equiv a[p]$ on tire $p\mid a^p-a=a(a^{p-1}-1)$. Comme $p$ est premier et $p\nmid a$, on a $p\wedge a=1$, et le lemme de Gauss donne

$$p\mid a^{p-1}-1,\text{c’est-}\grave{\text{a}}\text{-dire}{a}^{p-1}\equiv 1[p]\mathrm{.}\mathrm{\square }$$

Les réflexes du chapitre

L'arithmétique se reconnaît à ceci que chaque type de question a un outil attitré. Voici les associations à avoir en tête ; elles couvrent la très grande majorité des exercices.

1. Montrer qu'un entier variable en divise un autre. On fait apparaître une combinaison linéaire à coefficients entiers pour éliminer l'inconnue. Pour trouver tous les $n$ tels que $(n+3)\mid (n^2+1)$, on écrit $n^2+1=(n+3)(n-3)+10$, donc $(n+3)\mid 10$ : il reste huit valeurs possibles pour $n+3$, et l'on obtient $n\in \{-13,-8,-5,-4,-2,-1,2,7\}$.

2. Calculer le PGCD de deux expressions dépendant de $n$. Même geste : $a\wedge b=b\wedge (a-qb)$ permet de remplacer $a$ par un reste plus simple, exactement comme dans l'algorithme d'Euclide.

3. Montrer que deux entiers sont premiers entre eux. On exhibe une relation de Bézout $au+bv=1$. C'est la seule preuve courte : chercher les diviseurs communs est presque toujours plus long.

4. Montrer que $ab\mid c$ à partir de $a\mid c$ et $b\mid c$. On utilise Gauss, après avoir vérifié que $a\wedge b=1$. Sans cette hypothèse, c'est faux : $2\mid 12$ et $4\mid 12$, mais $8\nmid 12$.

5. Résoudre une équation $ax+by=c$ en entiers. Trois temps : condition d'existence $(a\wedge b)\mid c$, solution particulière par la remontée de l'algorithme d'Euclide, puis forme générale obtenue par Gauss.

6. Résoudre une congruence $ax\equiv b[n]$. Si $a\wedge n=1$, on calcule un inverse de $a$ modulo $n$ par Bézout et l'on multiplie. Sinon, on divise l'équation et le module par $d=a\wedge n$, après avoir vérifié que $d\mid b$. Pour un système de deux congruences, on substitue $x=a+mk$ dans la seconde et l'on se ramène à ce cas.

7. Calculer le reste d'une puissance à exposant énorme. On passe aux congruences, on cherche un exposant $t$ tel que $a^t\equiv \pm 1$, puis on divise l'exposant par $t$. Si le module est premier et ne divise pas la base, Fermat fournit directement $t=p-1$.

8. Montrer qu'un entier fixe divise une expression pour tout $n$. On décompose cet entier en facteurs premiers deux à deux distincts, on traite chaque facteur par Fermat ou par disjonction de cas, puis on recolle par Gauss. C'est la démonstration de $42\mid n^7-n$.

9. Montrer qu'une expression n'est jamais divisible par un entier. On discute selon le reste de $n$ modulo cet entier, en dressant une petite table. Par exemple $n\equiv 0,1,2[3]$ donne $n^2\equiv 0,1,1[3]$, donc $n^2+1\equiv 1,2,2[3]$ : jamais nul, donc $3\nmid n^2+1$ pour tout $n$.

10. Montrer qu'une équation n'a pas de solution entière. On la réduit modulo un entier bien choisi, souvent $3$, $4$, $8$ ou $9$. Ainsi $x^2+y^2=2023$ n'a pas de solution : les carrés sont congrus à $0$ ou $1$ modulo $4$, donc $x^2+y^2\equiv 0$, $1$ ou $2[4]$, alors que $2023\equiv 3[4]$.

11. Reconnaître un carré parfait, une puissance $k$-ième. On passe aux valuations : toutes doivent être divisibles par $k$. C'est aussi la façon la plus rapide de trouver par quoi multiplier un entier pour le rendre carré.

12. Démontrer une irrationalité du type $\sqrt{n}$. On suppose $\sqrt{n}=a\mathrm{/}b$, on élève au carré pour obtenir $a^2=n{b}^2$, puis on compare les valuations des deux membres pour un facteur premier de $n$ d'exposant impair : l'une est paire, l'autre impaire.

13. Comparer deux entiers dont on connaît la décomposition. Divisibilité, PGCD et PPCM se lisent premier par premier : $⩽$, $\min$ et $\max$ sur les valuations. C'est le moyen le plus sûr de ne pas confondre PGCD et PPCM.

14. Compter les diviseurs d'un entier. On décompose et l'on applique $\prod ({\alpha }_i+1)$. Si l'énoncé demande la liste, on l'organise par puissances croissantes du plus petit facteur premier pour n'en oublier aucun.

15. Tester la primalité d'un entier concret. On teste les diviseurs premiers inférieurs ou égaux à $\sqrt{n}$, et rien d'autre. Pour dresser une liste complète de nombres premiers, on utilise le crible d'Ératosthène plutôt que des tests individuels.