Arithmétique

L'arithmétique, la science des nombres entiers, est la plus ancienne branche des mathématiques : vers 300 avant notre ère, les Éléments d'Euclide contiennent déjà l'algorithme de calcul du PGCD qui porte son nom et la démonstration, toujours enseignée aujourd'hui, de l'infinité des nombres premiers. Au XVIIe siècle, Pierre de Fermat relance la discipline en énonçant, dans les marges de ses lectures, des résultats profonds sur les nombres premiers, dont le « petit théorème » qui clôt ce chapitre. Longtemps considérée comme la plus pure des disciplines, sans la moindre application, l'arithmétique est devenue au XXe siècle le cœur de la cryptographie qui protège nos communications : les théorèmes que nous allons démontrer sont exécutés chaque seconde par des milliards de machines.

Divisibilité dans Z

Tout ce chapitre se déroule dans $\mathbb{Z}$, l'ensemble des entiers relatifs. La notion fondatrice est celle de divisibilité : elle formalise l'idée qu'un entier « tombe juste » dans un autre.

Exemples.

Remarques.

• Tout entier $a$ divise $0$, puisque $0=0\times a$. En revanche, $0$ ne divise que $0$.
• Les entiers $1$ et $-1$ divisent tous les entiers, et tout entier $a$ est divisible par $1$, $-1$, $a$ et $-a$.
• Si $a\mid b$, alors $-a\mid b$ également : les diviseurs d'un entier vont donc par paires opposées. Ainsi, l'ensemble des diviseurs de $12$ est $\{\pm 1;\pm 2;\pm 3;\pm 4;\pm 6;\pm 12\}$.

Démonstration. Écrivons $b=ka$ avec $k$ entier. Comme $b\mathrm{\ne }0$, on a $k\mathrm{\ne }0$, donc $\mathrm{\mid }k\mathrm{\mid }⩾1$, et ainsi $\mathrm{\mid }b\mathrm{\mid }=\mathrm{\mid }k\mathrm{\mid }\times \mathrm{\mid }a\mathrm{\mid }⩾\mathrm{\mid }a\mathrm{\mid }$. Les diviseurs de $b$ sont donc tous compris entre $-\mathrm{\mid }b\mathrm{\mid }$ et $\mathrm{\mid }b\mathrm{\mid }$ : il n'y en a qu'un nombre fini. $\mathrm{\square }$

Les deux propriétés suivantes sont les outils de travail quotidiens de l'arithmétique : la seconde, en particulier, servira dans presque toutes les démonstrations du chapitre.

Démonstration. Pour la transitivité : si $b=ka$ et $c=k^{\mathrm{\prime }}b$ avec $k$ et $k^{\mathrm{\prime }}$ entiers, alors $c=k^{\mathrm{\prime }}ka$, et $k^{\mathrm{\prime }}k$ est un entier, donc $a\mid c$.

Pour les combinaisons linéaires : si $d\mid a$ et $d\mid b$, il existe des entiers $k$ et $k^{\mathrm{\prime }}$ tels que $a=dk$ et $b=d{k}^{\mathrm{\prime }}$. Alors, pour tous entiers $u$ et $v$ :

$$au+bv=dku+d{k}^{\mathrm{\prime }}v=d(ku+k^{\mathrm{\prime }}v),$$

et $ku+k^{\mathrm{\prime }}v$ est un entier relatif, donc $d\mid au+bv$. Les cas particuliers s'obtiennent avec $(u;v)=(1;1)$ et $(u;v)=(1;-1)$. $\mathrm{\square }$

Division euclidienne

Lorsque $b$ ne divise pas $a$, tout n'est pas perdu : on peut toujours effectuer la division « avec reste » apprise à l'école primaire. Le théorème suivant, pilier du chapitre, affirme que cette division est toujours possible et que son résultat est unique.

Démonstration. Existence. Considérons l'ensemble $E=\{k\in \mathbb{Z};bk⩽a\}$ des entiers dont le produit par $b$ ne dépasse pas $a$.

• $E$ est non vide : si $a⩾0$, alors $0\in E$ ; si $a<0$, alors $ba⩽a$ (car $b⩾1$ et $a<0$), donc $a\in E$.
• $E$ est majoré : soit $k\in E$. Si $k>0$, alors $k⩽bk⩽a⩽\mathrm{\mid }a\mathrm{\mid }$ ; si $k⩽0$, alors $k⩽0⩽\mathrm{\mid }a\mathrm{\mid }$. Dans tous les cas, $k⩽\mathrm{\mid }a\mathrm{\mid }$.

L'ensemble $E$, partie non vide et majorée de $\mathbb{Z}$, admet donc un plus grand élément, que nous notons $q$. Par définition de $q$ : $bq⩽a$, et $q+1\mathrm{\notin }E$, c'est-à-dire $b(q+1)>a$. Posons $r=a-bq$. Alors $a=bq+r$ par construction, $r⩾0$ car $bq⩽a$, et

$$r=a-bq<b(q+1)-bq=b,$$

d'où $0⩽r<b$ : le couple $(q;r)$ convient.

Unicité. Supposons $a=bq+r=b{q}^{\mathrm{\prime }}+r^{\mathrm{\prime }}$ avec $0⩽r<b$ et $0⩽r^{\mathrm{\prime }}<b$. En soustrayant les deux écritures :

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

donc $b$ divise $r^{\mathrm{\prime }}-r$. Or les encadrements de $r$ et $r^{\mathrm{\prime }}$ donnent $-b<r^{\mathrm{\prime }}-r<b$, et le seul multiple de $b$ strictement compris entre $-b$ et $b$ est $0$. Ainsi $r^{\mathrm{\prime }}=r$, puis $b(q-q^{\mathrm{\prime }})=0$ avec $b\mathrm{\ne }0$, d'où $q=q^{\mathrm{\prime }}$. $\mathrm{\square }$

Remarque. Le reste est nul si et seulement si $b$ divise $a$ : la division euclidienne contient donc la divisibilité comme cas particulier, et fournit un test concret de divisibilité.

Congruences

Bien souvent, seul le reste d'une division nous intéresse : quelle heure sera-t-il dans $1000$ heures, quel est le chiffre des unités de $7^{50}$ ? La notion de congruence, introduite par Gauss en 1801, permet de calculer directement sur les restes, avec une souplesse remarquable.

Exemples.

La définition par la divisibilité est la plus commode pour les démonstrations, mais l'intuition « même reste » reste la bonne, comme le confirme la caractérisation suivante.

Démonstration. Écrivons les divisions euclidiennes de $a$ et $b$ par $n$ : $a=nq+r$ et $b=n{q}^{\mathrm{\prime }}+r^{\mathrm{\prime }}$ avec $0⩽r<n$ et $0⩽r^{\mathrm{\prime }}<n$. Alors

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

Si $r=r^{\mathrm{\prime }}$, alors $a-b=n(q-q^{\mathrm{\prime }})$ est divisible par $n$, donc $a\equiv b[n]$. Réciproquement, si $n\mid a-b$, alors $r-r^{\mathrm{\prime }}=(a-b)-n(q-q^{\mathrm{\prime }})$ est divisible par $n$ comme combinaison linéaire de $a-b$ et de $n$. Or $-n<r-r^{\mathrm{\prime }}<n$, et le seul multiple de $n$ dans cet intervalle est $0$ : donc $r=r^{\mathrm{\prime }}$. $\mathrm{\square }$

Remarque. On vérifie immédiatement à partir de la définition que la congruence se comporte comme une égalité : $a\equiv a[n]$ ; si $a\equiv b[n]$ alors $b\equiv a[n]$ ; et si $a\equiv b[n]$ et $b\equiv c[n]$, alors $a\equiv c[n]$ (car $n$ divise $(a-b)+(b-c)=a-c$).

Voici maintenant la propriété qui fait toute la puissance des congruences : elles sont compatibles avec les opérations. On peut additionner, soustraire et multiplier des congruences membre à membre, exactement comme des égalités.

Démonstration (produit et puissances). Pour le produit, l'astuce consiste à intercaler le terme $bc$ :

$$ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)\mathrm{.}$$

Par hypothèse, $n$ divise $a-b$ et $c-d$ : la propriété des combinaisons linéaires assure alors que $n$ divise $c(a-b)+b(c-d)=ac-bd$, c'est-à-dire $ac\equiv bd[n]$.

Pour les puissances, on raisonne par récurrence sur $k$. Pour $k=0$, on a bien $1\equiv 1[n]$. Supposons $a^k\equiv b^k[n]$ pour un entier naturel $k$. En appliquant la compatibilité avec le produit aux congruences $a\equiv b[n]$ et $a^k\equiv b^k[n]$, on obtient $a^{k+1}\equiv b^{k+1}[n]$, ce qui achève la récurrence. La compatibilité avec la somme et la différence se démontre de même, directement par combinaison linéaire. $\mathrm{\square }$

Remarque (mise en garde). On ne peut pas simplifier une congruence par un facteur commun : $2\times 3\equiv 2\times 0[6]$ est vraie, mais $3\equiv 0[6]$ est fausse. La « division » des congruences n'existe pas en général ; le théorème de Gauss, plus loin, précisera dans quel cas une simplification est légitime.

Critères de divisibilité

Les congruences expliquent enfin les critères de divisibilité appris au collège, et en fournissent de nouveaux. Notons qu'un entier naturel $N$ d'écriture décimale $\overline{a_k{a}_{k-1}\dots a_1{a}_0}$ (où $a_0$ est le chiffre des unités) s'écrit

$$N=a_k\times {10}^k+a_{k-1}\times {10}^{k-1}+\cdots +a_1\times 10+a_0\mathrm{.}$$

PGCD et algorithme d'Euclide

Après l'étude des diviseurs d'un entier, intéressons-nous aux diviseurs communs à deux entiers, et au plus grand d'entre eux.

Ces propriétés découlent directement de la définition : un entier et son opposé ont les mêmes diviseurs, tout entier divise $0$, et si $b\mid a$ alors $\mathrm{\mid }b\mathrm{\mid }$ est un diviseur commun à $a$ et $b$ qui est le plus grand possible parmi les diviseurs de $b$.

Calculer un PGCD en dressant la liste des diviseurs devient vite impraticable : quels sont les diviseurs de $8051$ ? Le lemme suivant, cœur de l'algorithme d'Euclide, permet de remplacer ce problème par un problème strictement plus petit.

Démonstration. Écrivons $a=bq+r$. Montrons que les couples $(a;b)$ et $(b;r)$ ont exactement les mêmes diviseurs communs ; leurs plus grands éléments seront alors égaux.

Soit $d$ un diviseur commun à $a$ et $b$. Comme $r=a-bq$ est une combinaison linéaire de $a$ et $b$, on a $d\mid r$ : donc $d$ est un diviseur commun à $b$ et $r$.

Réciproquement, soit $d$ un diviseur commun à $b$ et $r$. Comme $a=bq+r$ est une combinaison linéaire de $b$ et $r$, on a $d\mid a$ : donc $d$ est un diviseur commun à $a$ et $b$.

Les deux ensembles de diviseurs communs coïncident, donc les PGCD sont égaux. $\mathrm{\square }$

L'algorithme se programme en quelques lignes : l'opérateur % de Python renvoie précisément le reste de la division euclidienne.

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(pgcd(252, 198))  # affiche 18

Entiers premiers entre eux

Le cas où le PGCD vaut $1$ est si important qu'il mérite un nom : c'est lui qui gouverne les théorèmes de Bézout et de Gauss.

Remarque. Ne pas confondre « premiers entre eux » et « nombres premiers » : $8$ et $15$ sont premiers entre eux (aucun diviseur commun autre que $\pm 1$), alors qu'aucun des deux n'est un nombre premier. Inversement, deux nombres premiers distincts sont toujours premiers entre eux.

La propriété suivante affirme qu'en divisant deux entiers par leur PGCD, on « épuise » tout ce qu'ils ont en commun : c'est elle qui garantit que toute fraction se simplifie en une fraction irréductible.

Démonstration. Comme $d$ divise $a$ et $b$, on peut écrire $a=d{a}^{\mathrm{\prime }}$ et $b=d{b}^{\mathrm{\prime }}$ avec $a^{\mathrm{\prime }}$ et $b^{\mathrm{\prime }}$ entiers relatifs. Posons $k=\gcd (a^{\mathrm{\prime }};b^{\mathrm{\prime }})$ : c'est un entier naturel supérieur ou égal à $1$, et $k$ divise $a^{\mathrm{\prime }}$ et $b^{\mathrm{\prime }}$. Alors $dk$ divise $d{a}^{\mathrm{\prime }}=a$ et $d{b}^{\mathrm{\prime }}=b$ : c'est un diviseur commun positif de $a$ et $b$. Par définition du PGCD, $dk⩽d$, donc $k⩽1$, et finalement $k=1$. $\mathrm{\square }$

Théorème de Bézout

L'algorithme d'Euclide fait mieux que calculer le PGCD : lu à l'envers, il exprime ce PGCD comme combinaison linéaire des deux entiers de départ. Cette lecture à rebours est appelée la remontée de l'algorithme.

Ce que l'exemple montre est général : chaque reste de l'algorithme s'écrit comme combinaison linéaire des deux termes qui le précèdent, donc, de proche en proche, comme combinaison linéaire de $a$ et $b$. Le dernier reste non nul, c'est-à-dire le PGCD, s'écrit ainsi $au+bv$. C'est l'identité de Bézout.

Dans le cas d'entiers premiers entre eux, cette identité admet une réciproque : c'est le théorème de Bézout proprement dit.

Démonstration. Sens direct. Si $\gcd (a;b)=1$, l'identité de Bézout fournit directement des entiers $u$ et $v$ tels que $au+bv=1$.

Sens réciproque. Supposons qu'il existe des entiers $u$ et $v$ tels que $au+bv=1$, et soit $d$ un diviseur commun positif de $a$ et $b$. Par la propriété des combinaisons linéaires, $d$ divise $au+bv=1$, donc $d=1$. Le seul diviseur commun positif de $a$ et $b$ est $1$, c'est-à-dire $\gcd (a;b)=1$. $\mathrm{\square }$

Remarque (mise en garde). L'équivalence ne vaut que pour le second membre $1$. Si $au+bv=c$ avec $c\mathrm{\ne }1$, on peut seulement affirmer que $\gcd (a;b)$ divise $c$, pas qu'il lui est égal : par exemple $2\times 3+4\times 0=6$, alors que $\gcd (2;4)=2\mathrm{\ne }6$.

Le théorème de Bézout est l'outil roi pour montrer que deux entiers dépendant d'un paramètre sont premiers entre eux : inutile de calculer le moindre PGCD, il suffit d'exhiber une combinaison linéaire égale à $1$.

Théorème de Gauss

Nous avons signalé qu'on ne peut pas simplifier une congruence ou une divisibilité sans précaution. Le théorème de Gauss donne la condition exacte sous laquelle la simplification est permise : c'est le résultat le plus utilisé du chapitre, notamment pour résoudre les équations diophantiennes.

Démonstration. Comme $\gcd (a;b)=1$, le théorème de Bézout fournit des entiers $u$ et $v$ tels que $au+bv=1$. Multiplions cette égalité par $c$ :

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

Or $a$ divise $acu$ (évident) et $a$ divise $bcv$ (car $a\mid bc$ par hypothèse) : par combinaison linéaire, $a$ divise $acu+bcv=c$. $\mathrm{\square }$

Remarque. L'hypothèse $\gcd (a;b)=1$ est indispensable : $6$ divise $4\times 3=12$, mais $6$ ne divise ni $4$ ni $3$.

Démonstration. Premier point. Comme $b\mid a$, écrivons $a=bk$ avec $k$ entier. Alors $c$ divise $a=bk$, et $c$ est premier avec $b$ : le théorème de Gauss donne $c\mid k$, donc $k=c{k}^{\mathrm{\prime }}$ avec $k^{\mathrm{\prime }}$ entier, et $a=bc{k}^{\mathrm{\prime }}$, c'est-à-dire $bc\mid a$.

Second point. Supposons $p\nmid a$. Les seuls diviseurs positifs de $p$ sont $1$ et $p$ ; comme $p$ ne divise pas $a$, le seul diviseur positif commun à $p$ et $a$ est $1$, donc $\gcd (p;a)=1$. Puisque $p\mid ab$, le théorème de Gauss donne alors $p\mid b$. On a bien montré : $p\mid a$ ou $p\mid b$. $\mathrm{\square }$

Équations diophantiennes

Diophante d'Alexandrie, au IIIe siècle, étudiait des équations dont on ne cherche que les solutions entières. Nous nous intéressons ici aux équations du premier degré à deux inconnues : étant donnés des entiers $a$, $b$ (non nuls) et $c$, trouver tous les couples d'entiers relatifs $(x;y)$ tels que

$$ax+by=c\mathrm{.}$$

Démonstration. Posons $d=\gcd (a;b)$. Si $(x;y)$ est une solution, alors $d$, qui divise $a$ et $b$, divise la combinaison linéaire $ax+by=c$. Réciproquement, si $d\mid c$, écrivons $c=d{c}^{\mathrm{\prime }}$ avec $c^{\mathrm{\prime }}$ entier. L'identité de Bézout fournit $u$ et $v$ tels que $au+bv=d$ ; en multipliant par $c^{\mathrm{\prime }}$ :

$$a(u{c}^{\mathrm{\prime }})+b(v{c}^{\mathrm{\prime }})=d{c}^{\mathrm{\prime }}=c,$$

donc le couple $(u{c}^{\mathrm{\prime }};v{c}^{\mathrm{\prime }})$ est une solution. $\mathrm{\square }$

Nombres premiers

Les nombres premiers sont les « atomes » de l'arithmétique : tout entier se fabrique en les multipliant, et ce d'une seule façon. Cette section établit leurs trois propriétés fondamentales : un test de primalité efficace, leur infinité, et le théorème de décomposition.

Démonstration. L'ensemble des diviseurs de $n$ supérieurs ou égaux à $2$ est non vide (il contient $n$) : il admet un plus petit élément $d$. Montrons que $d$ est premier. Si $d$ admettait un diviseur $d^{\mathrm{\prime }}$ avec $2⩽d^{\mathrm{\prime }}<d$, alors par transitivité $d^{\mathrm{\prime }}$ diviserait $n$ : ce serait un diviseur de $n$ supérieur ou égal à $2$ et strictement plus petit que $d$, ce qui contredit la minimalité de $d$. Les seuls diviseurs positifs de $d$ sont donc $1$ et $d$, et $d⩾2$ : $d$ est premier. $\mathrm{\square }$

Démonstration. Montrons la contraposée : si $n$ est composé, alors $n$ admet un diviseur premier inférieur ou égal à $\sqrt{n}$. Supposons donc $n$ composé : il s'écrit $n=ab$ avec $2⩽a⩽b$. Alors

$$a^2⩽ab=n,\text{donc}a⩽\sqrt{n}\mathrm{.}$$

D'après la propriété précédente, $a$ admet un diviseur premier $p$, qui vérifie $p⩽a⩽\sqrt{n}$ ; et par transitivité, $p$ divise $n$. $\mathrm{\square }$

Combien y a-t-il de nombres premiers ? La réponse d'Euclide, vieille de vingt-trois siècles, est l'une des plus belles démonstrations des mathématiques — et elle est exigible au baccalauréat.

Démonstration. Raisonnons par l'absurde en supposant qu'il n'existe qu'un nombre fini de nombres premiers, notés $p_1,p_2,\dots ,p_n$. Considérons l'entier

$$N=p_1\times p_2\times \cdots \times p_n+1.$$

Comme $N⩾2$, il admet un diviseur premier $p$. Par hypothèse, $p$ est l'un des $p_i$ : il divise donc le produit $p_1{p}_2\cdots p_n$. Par combinaison linéaire, $p$ divise alors

$$N-p_1{p}_2\cdots p_n=1,$$

ce qui est impossible pour un nombre premier ($p⩾2$). Cette contradiction montre que l'hypothèse de départ est fausse : il existe une infinité de nombres premiers. $\mathrm{\square }$

Venons-en au théorème qui justifie le surnom d'« atomes » : tout entier est un produit de nombres premiers, écrit de manière essentiellement unique.

Démonstration de l'existence. On raisonne par récurrence forte. Pour $n⩾2$, notons $P(n)$ la propriété : « $n$ s'écrit comme un produit de nombres premiers » (un produit pouvant ne compter qu'un seul facteur).

Initialisation. $P(2)$ est vraie : $2$ est premier, c'est un produit d'un seul facteur premier.

Hérédité. Soit $n⩾2$ tel que $P(k)$ soit vraie pour tout entier $k$ vérifiant $2⩽k⩽n$. Montrons $P(n+1)$. Si $n+1$ est premier, c'est un produit d'un seul facteur premier, et $P(n+1)$ est vraie. Sinon, $n+1$ est composé : il s'écrit $n+1=ab$ avec $2⩽a⩽n$ et $2⩽b⩽n$. Par hypothèse de récurrence, $a$ et $b$ s'écrivent chacun comme un produit de nombres premiers ; leur produit $n+1$ aussi.

Par récurrence forte, $P(n)$ est vraie pour tout entier $n⩾2$. L'unicité de la décomposition, plus délicate (elle repose sur le corollaire du théorème de Gauss : un nombre premier qui divise un produit divise l'un des facteurs), est admise. $\mathrm{\square }$

La décomposition d'un entier donne un contrôle total sur ses diviseurs, comme le précise la propriété suivante (conséquence de l'unicité de la décomposition).

En effet, chaque exposant ${\beta }_i$ se choisit indépendamment parmi les ${\alpha }_i+1$ valeurs $0,1,\dots ,{\alpha }_i$, et deux choix distincts donnent deux diviseurs distincts par unicité de la décomposition : le principe multiplicatif du dénombrement conclut.

Petit théorème de Fermat

Dans une lettre de 1640, Fermat énonce, « sans la démonstration, de peur d'être trop long », une propriété remarquable des nombres premiers. Elle relie les deux fils conducteurs du chapitre, congruences et nombres premiers, et fournit un raccourci spectaculaire pour calculer les restes de grandes puissances.

Les deux formes sont en réalité équivalentes, et il faut savoir passer de l'une à l'autre.

De la première forme à la seconde. Soit $a$ un entier relatif. Si $p\nmid a$, la première forme donne $a^{p-1}\equiv 1[p]$ ; en multipliant par $a$ (compatibilité avec le produit) : $a^p\equiv a[p]$. Si au contraire $p\mid a$, alors $a\equiv 0[p]$, donc $a^p\equiv 0\equiv a[p]$. Dans tous les cas, $a^p\equiv a[p]$.

De la seconde forme à la première. Soit $a$ non divisible par $p$. La seconde forme s'écrit $p\mid a^p-a=a(a^{p-1}-1)$. Comme $p$ est premier et ne divise pas $a$, on a $\gcd (p;a)=1$, et le théorème de Gauss donne $p\mid a^{p-1}-1$, c'est-à-dire $a^{p-1}\equiv 1[p]$.

Le bilan du chapitre dessine une architecture remarquablement cohérente : la divisibilité et la division euclidienne fondent les congruences ; l'algorithme d'Euclide calcule le PGCD et, par sa remontée, livre l'identité de Bézout ; celle-ci démontre le théorème de Gauss, qui résout les équations diophantiennes ; enfin les nombres premiers, atomes de $\mathbb{Z}$, obéissent au petit théorème de Fermat, qui dompte les puissances gigantesques en quelques lignes. Ces outils, nés de la curiosité pure d'Euclide et de Fermat, sont précisément ceux qui sécurisent aujourd'hui les échanges numériques du monde entier.