Arithmétique dans ℤ

Étudier divisibilité, congruences et théorèmes fondamentaux (série C / spécialité).

Mathématiques Terminale Chapitre 18 / 19 ⏱ 11 h

Ce que tu sauras faire à la fin

Résoudre une équation diophantienne ax + by = c
Utiliser les congruences pour un problème de reste
Appliquer Bézout et Gauss dans une démonstration

Compter, partager, coder : trois activités aussi vieilles que les mathématiques, et qui reposent toutes les trois sur une seule notion, la divisibilité dans $\mathbb{Z}$ , l'ensemble des entiers relatifs. Quand un commerçant de Bamako répartit équitablement des sacs de céréales entre plusieurs paniers, quand ta carte bancaire vérifie en un instant qu'un numéro de compte est valide, quand un site internet protège un mot de passe avant de l'envoyer sur le réseau, ce sont des restes de division et des nombres premiers qui travaillent en coulisses. Ce chapitre te donne les clés pour comprendre, démontrer et utiliser ces mécanismes.

Tu manies la division depuis le primaire, et les mots « multiple » et « diviseur » te sont familiers depuis longtemps. Ce qui change en Terminale, c'est le passage de la pratique à la preuve : chaque propriété que tu utilisais « parce que ça marche » va désormais être démontrée à partir d'une poignée de définitions précises. Tu vas aussi découvrir deux outils entièrement nouveaux — le théorème de Bézout et le théorème de Gauss — qui permettent de résoudre complètement des équations où seules les solutions entières nous intéressent : les équations diophantiennes.

Une notion neuve structure tout le chapitre : la congruence. Écrire $a \equiv b \pmod{n}$ revient à dire que $a$ et $b$ laissent le même reste dans la division par $n$ — une idée d'une grande simplicité, mais d'une puissance immense : critères de divisibilité, calendriers perpétuels, clés de contrôle des numéros bancaires ou des ISBN, chiffrement des messages... la congruence est l'outil discret qui fait fonctionner une bonne partie du monde numérique.

La progression du chapitre suit une logique de construction, brique après brique : la division euclidienne (§1) fournit le reste sur lequel repose l'algorithme d'Euclide (§2) ; celui-ci permet de démontrer le théorème de Bézout (§3), qui entraîne à son tour le théorème de Gauss (§4) ; ces deux théorèmes éclairent la structure des nombres premiers (§5) et donnent tout son sens aux congruences (§6), pour déboucher sur des applications bien concrètes (§7). Prends le temps d'assimiler chaque section avant de passer à la suivante : c'est un chapitre où tout s'enchaîne.

1Divisibilité et division euclidienne

Toute l'arithmétique repose sur une opération que tu pratiques depuis l'école primaire : la division. Il est temps d'en donner une définition précise et d'en démontrer les propriétés.

1.1 Multiples et diviseurs

Définition

Soient $a$ et $b$ deux entiers relatifs. On dit que $b$ divise $a$ , ou que $b$ est un diviseur de $a$ , ou encore que $a$ est un multiple de $b$ , lorsqu'il existe un entier $k \in \mathbb{Z}$ tel que :

$a = bk$

On note alors $b \mid a$ (lire « $b$ divise $a$ »).

L'ensemble des multiples d'un entier $b$ se note $b\mathbb{Z} = \{\, bk \mid k \in \mathbb{Z} \,\}$ . Par exemple $3\mathbb{Z} = \{ \ldots, -6, -3, 0, 3, 6, 9, \ldots \}$ .

Exemple — reconnaître une divisibilité

$5 \mid 20$ car $20 = 5 \times 4$
$(-3) \mid 12$ car $12 = (-3) \times (-4)$
$7 \nmid 10$ aucun entier $k$ ne vérifie $10 = 7k$
$n \mid 0$ pour tout entier $n$ car $0 = n \times 0$

Attention

Ne confonds pas les rôles : dans « $b \mid a$ », c'est $b$ le diviseur et $a$ le multiple. L'écriture $a \mid b$ et l'écriture $b \mid a$ n'ont en général rien à voir. Par ailleurs, $0$ ne divise que lui-même : $0 \mid a$ équivaut à $a = 0$ , puisque $0 \times k = 0$ quel que soit $k$ .

1.2 Propriétés de la divisibilité

Propriété

Soient $a, b, c$ des entiers relatifs.

Réflexivité : $a \mid a$ ; et $1 \mid a$ pour tout $a$ .
Transitivité : si $a \mid b$ et $b \mid c$ , alors $a \mid c$ .
Combinaison linéaire : si $a \mid b$ et $a \mid c$ , alors pour tous entiers $u, v$ : $a \mid (bu + cv)$ .

Démonstration

Transitivité. Par hypothèse, il existe $k \in \mathbb{Z}$ tel que $b = ak$ , et il existe $k' \in \mathbb{Z}$ tel que $c = bk'$ .

$c = bk' = (ak)k'$
$=$ $a(kk')$ $kk' \in \mathbb{Z}$

Donc $a \mid c$ .

Combinaison linéaire. Par hypothèse, $b = ak$ et $c = ak'$ pour deux entiers $k, k'$ . Pour tous entiers $u, v$ :

$bu + cv = aku + ak'v$
$=$ $a(ku + k'v)$ $ku + k'v \in \mathbb{Z}$

Donc $a \mid (bu+cv)$ . C.Q.F.D.

Cette dernière propriété est utilisée en permanence : elle affirme que l'ensemble des diviseurs communs à deux nombres reste stable par combinaison — c'est exactement le principe caché derrière l'algorithme d'Euclide de la section suivante.

Exemple — combiner des divisibilités

On sait que $6 \mid 90$ et $6 \mid 24$ . Montrons que $6 \mid (5 \times 90 - 3 \times 24)$ .

$5 \times 90 - 3 \times 24 = 450 - 72$
$=$ $378$
$6 \mid 378$ propriété de combinaison linéaire, ou directement $378 = 6 \times 63$

1.3 Division euclidienne

Quand $b$ ne divise pas $a$ , la division « ne tombe pas juste » : il reste quelque chose. La division euclidienne organise ce reste de façon unique.

Théorème — existence et unicité

Soit $a \in \mathbb{Z}$ et $b \in \mathbb{N}^{*}$ . Il existe un unique couple d'entiers $(q, r)$ tel que :

$a = bq + r \quad \text{avec} \quad 0 \leqslant r < b$

$q$ s'appelle le quotient et $r$ le reste de la division euclidienne de $a$ par $b$ .

Démonstration

Existence. On admet la propriété d'Archimède : pour tout réel $x$ , il existe un unique entier $q$ tel que $q \leqslant x < q+1$ (la partie entière de $x$ ). Appliquée à $x = \dfrac{a}{b}$ , elle donne un unique entier $q$ tel que :

$q \leqslant \dfrac{a}{b} < q + 1$
$\Rightarrow$ $bq \leqslant a < bq + b$ on multiplie par $b > 0$ , qui conserve l'ordre

Posons $r = a - bq$ . L'encadrement précédent donne exactement $0 \leqslant r < b$ , et par construction $a = bq + r$ . L'existence est établie.

Unicité. Supposons $a = bq + r = bq' + r'$ avec $0 \leqslant r < b$ et $0 \leqslant r' < b$ . Alors :

$b(q - q') = r' - r$
$-b < r' - r < b$ car $0 \leqslant r < b$ et $0 \leqslant r' < b$
$\Rightarrow$ $\left| b(q-q') \right| < b$
$\Rightarrow$ $\left| q - q' \right| < 1$ on divise par $b > 0$

Or $q - q'$ est un entier : le seul entier de valeur absolue strictement inférieure à $1$ est $0$ . Donc $q = q'$ , puis $r = a - bq = a - bq' = r'$ . C.Q.F.D.

Exemple — division euclidienne, cas positif

Effectuons la division euclidienne de $875$ par $23$ .

$23 \times 38 = 874$
$875 = 23 \times 38 + 1$
$0 \leqslant 1 < 23$ le reste convient

Le quotient est $q = 38$ et le reste est $r = 1$ .

Attention — le piège du dividende négatif

Quand $a$ est négatif, on ne « tronque » jamais vers zéro : il faut absolument que $0 \leqslant r < b$ . Cherchons la division euclidienne de $a = -7$ par $b = 3$ .

écriture incorrecte : $-7 = 3 \times (-2) - 1$ le reste $-1$ est négatif : interdit !
écriture correcte : $-7 = 3 \times (-3) + 2$
$0 \leqslant 2 < 3$ le reste convient

Le quotient de $-7$ par $3$ est donc $q = -3$ et le reste est $r = 2$ , et non $-1$ . En cas de doute, ajoute des multiples de $b$ jusqu'à obtenir un reste dans $[0\,;\,b[$ .

2PGCD, PPCM, algorithme d'Euclide

Deux entiers ont toujours des diviseurs communs (au moins $1$ ) et des multiples communs (au moins leur produit). Cette section organise ces diviseurs et multiples communs autour de deux nombres privilégiés : le plus grand des uns, le plus petit des autres.

2.1 Le PGCD

Définition

Soient $a$ et $b$ deux entiers, non tous les deux nuls. L'ensemble des diviseurs communs positifs de $a$ et $b$ est une partie finie et non vide de $\mathbb{N}^{*}$ (elle contient $1$ ) : elle possède donc un plus grand élément, appelé plus grand commun diviseur de $a$ et $b$ , noté $\operatorname{pgcd}(a,b)$ .

Exemple — calcul direct par les diviseurs

Cherchons $\operatorname{pgcd}(18, 24)$ .

diviseurs de $18$ : $\{1, 2, 3, 6, 9, 18\}$
diviseurs de $24$ : $\{1, 2, 3, 4, 6, 8, 12, 24\}$
diviseurs communs : $\{1, 2, 3, 6\}$
$\Rightarrow$ $\operatorname{pgcd}(18, 24) = 6$

Cette méthode par liste devient vite impraticable pour de grands nombres : c'est pour cela que les mathématiciens grecs ont inventé un algorithme bien plus rapide.

2.2 L'algorithme d'Euclide

Propriété fondamentale

Soient $a \in \mathbb{Z}$ et $b \in \mathbb{N}^{*}$ . Si $r$ est le reste de la division euclidienne de $a$ par $b$ , alors :

$\operatorname{pgcd}(a, b) = \operatorname{pgcd}(b, r)$

Démonstration

On a $a = bq + r$ pour un certain entier $q$ . Montrons que $a$ et $b$ ont exactement les mêmes diviseurs communs que $b$ et $r$ .

Soit $d$ un diviseur commun de $a$ et $b$ : $d \mid a$ et $d \mid b$ . Comme $r = a - bq$ est une combinaison linéaire de $a$ et $b$ , la propriété de la section 1 donne $d \mid r$ . Donc $d$ est un diviseur commun de $b$ et $r$ .

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

Les couples $(a,b)$ et $(b,r)$ ont donc le même ensemble de diviseurs communs — en particulier le même plus grand, d'où $\operatorname{pgcd}(a,b) = \operatorname{pgcd}(b,r)$ . C.Q.F.D.

Méthode — calculer un PGCD par l'algorithme d'Euclide

On répète les divisions euclidiennes en remplaçant à chaque étape le couple $(a,b)$ par $(b,r)$ , jusqu'à obtenir un reste nul. Le PGCD est alors le dernier reste non nul. L'algorithme s'arrête toujours : la suite des restes est strictement décroissante dans $\mathbb{N}$ , elle ne peut décroître indéfiniment.

Figure 1 — L'algorithme d'Euclide : à chaque étape, on remplace le couple

(a,b)

par

(b,r)

où

r

est le reste de la division de

a

par

b

; le PGCD est le dernier reste non nul.

Exemple — un second calcul, pour t'entraîner

Calculons $\operatorname{pgcd}(120, 45)$ par l'algorithme d'Euclide.

$120 = 45 \times 2 + 30$
$45 = 30 \times 1 + 15$
$30 = 15 \times 2 + 0$
$\Rightarrow$ $\operatorname{pgcd}(120, 45) = 15$ dernier reste non nul

Math & Co — Le plus vieil algorithme du monde

L'algorithme que tu viens d'apprendre apparaît, décrit avec une précision remarquable, dans le Livre VII des Éléments d'Euclide, rédigés à Alexandrie vers $-300$ . Euclide le présente sous forme géométrique, comme un procédé de « soustractions successives » de segments, et l'utilise pour démontrer que deux nombres premiers entre eux n'ont pas d'autre diviseur commun que $1$ .

Vingt-trois siècles plus tard, cet algorithme est toujours enseigné tel quel, et sa version rapide reste l'un des algorithmes les plus utilisés en informatique : il intervient par exemple dans les logiciels de cryptographie, dont le système RSA que tu découvriras en fin de chapitre.

2.3 Nombres premiers entre eux

Définition

Deux entiers $a$ et $b$ sont dits premiers entre eux lorsque $\operatorname{pgcd}(a,b) = 1$ , c'est-à-dire lorsque leur seul diviseur positif commun est $1$ .

Attention

« $a$ et $b$ premiers entre eux » ne signifie pas que $a$ ou $b$ est un nombre premier ! Par exemple, $8$ et $15$ sont premiers entre eux ( $\operatorname{pgcd}(8,15)=1$ ) bien qu'aucun des deux ne soit un nombre premier.

2.4 PPCM et relation avec le PGCD

Définition

Soient $a$ et $b$ deux entiers non nuls. L'ensemble des multiples strictement positifs communs à $a$ et $b$ est une partie non vide de $\mathbb{N}^{*}$ (elle contient $|ab|$ ) : elle possède donc un plus petit élément, appelé plus petit commun multiple de $a$ et $b$ , noté $\operatorname{ppcm}(a,b)$ .

Propriété

Pour tous entiers non nuls $a$ et $b$ :

$\operatorname{pgcd}(a,b) \times \operatorname{ppcm}(a,b) = |a \times b|$

En particulier, si $a$ et $b$ sont premiers entre eux, $\operatorname{ppcm}(a,b) = |ab|$ .

Cette relation, admise à ce stade, se justifie très naturellement à l'aide de la décomposition en facteurs premiers que tu découvriras en section 5 ; nous y reviendrons brièvement à ce moment-là.

Exemple — utiliser la relation PGCD × PPCM

On a vu que $\operatorname{pgcd}(120, 45) = 15$ . Déduisons-en $\operatorname{ppcm}(120,45)$ .

$\operatorname{pgcd}(120,45) \times \operatorname{ppcm}(120,45) = 120 \times 45$
$15 \times \operatorname{ppcm}(120,45) = 5\,400$
$\Rightarrow$ $\operatorname{ppcm}(120,45) = 360$

3Théorème de Bézout

Nous savons calculer $\operatorname{pgcd}(a,b)$ grâce à l'algorithme d'Euclide. Le théorème que voici va beaucoup plus loin : il affirme que ce pgcd peut toujours s'écrire comme une combinaison entière de $a$ et de $b$ . Cette identité, d'apparence modeste, est l'outil le plus puissant du chapitre : elle fonde le théorème de Gauss, la résolution des équations diophantiennes, et de nombreuses applications.

3.1 L'identité de Bézout

Théorème de Bézout

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls, et $d=\operatorname{pgcd}(a,b)$ . Il existe deux entiers relatifs $u$ et $v$ tels que :

$au+bv=d$

Un tel couple $(u,v)$ s'appelle un couple de coefficients de Bézout pour $a$ et $b$ .

Démonstration — par le plus petit élément

Considérons l'ensemble des entiers strictement positifs qui s'écrivent comme combinaison de $a$ et $b$ :

$E=\left\{\, au+bv \;\middle|\; u,v\in\mathbb{Z} \,\right\}\cap\mathbb{N}^{*}$

$E$ est une partie non vide de $\mathbb{N}^{*}$ : elle contient $a\times a+b\times b=a^{2}+b^{2}>0$ (pris avec $u=a$ , $v=b$ ). Elle possède donc un plus petit élément $\delta=au_{0}+bv_{0}$ , avec $u_{0},v_{0}\in\mathbb{Z}$ .

$\delta$ divise $a$ . Effectuons la division euclidienne de $a$ par $\delta$ : $a=\delta q+r$ avec $0\leqslant r<\delta$ .

$r=a-\delta q$
$=$ $a-(au_{0}+bv_{0})q$
$=$ $a(1-u_{0}q)+b(-v_{0}q)$ combinaison de $a$ et $b$

Si $r>0$ , alors $r\in E$ et $r<\delta$ : cela contredit la minimalité de $\delta$ . Donc $r=0$ , c'est-à-dire $\delta\mid a$ . Le même raisonnement, en échangeant les rôles, donne $\delta\mid b$ .

$\delta=d$ . $\delta$ est un diviseur commun de $a$ et $b$ , donc $\delta\leqslant d$ . Réciproquement, $d$ divise $a$ et $b$ , donc $d$ divise toute combinaison $au_{0}+bv_{0}=\delta$ (propriété de la section 1) : ainsi $d\leqslant\delta$ . Donc $\delta=d$ , et $d=au_{0}+bv_{0}$ . C.Q.F.D.

Exemple — vérifier une identité de Bézout

Pour $a=5$ et $b=3$ , on a $\operatorname{pgcd}(5,3)=1$ , et $(u,v)=(-1,2)$ convient :

$5\times(-1)+3\times2=-5+6$
$=$ $1$ bien le pgcd de $5$ et $3$

3.2 Caractérisation des nombres premiers entre eux

Corollaire

Deux entiers $a$ et $b$ sont premiers entre eux si et seulement si il existe deux entiers $u,v$ tels que :

$au+bv=1$

Démonstration

Si $\operatorname{pgcd}(a,b)=1$ , le théorème de Bézout donne directement $u,v$ tels que $au+bv=1$ .

Réciproquement, supposons $au+bv=1$ et notons $d=\operatorname{pgcd}(a,b)$ . Comme $d\mid a$ et $d\mid b$ , $d$ divise la combinaison $au+bv=1$ (propriété de la section 1). Un diviseur positif de $1$ valant nécessairement $1$ , on conclut $d=1$ . C.Q.F.D.

Exemple — retrouver un résultat de la section 2

On avait affirmé, sans le prouver, que $8$ et $15$ sont premiers entre eux :

$8\times2+15\times(-1)=16-15$
$=$ $1$ donc $\operatorname{pgcd}(8,15)=1$ par le corollaire

Attention

Le couple $(u,v)$ donné par Bézout n'est jamais unique : si $au+bv=d$ , alors pour tout entier $k$ , le couple $\left(u+k\dfrac{b}{d},\ v-k\dfrac{a}{d}\right)$ convient aussi (développe pour t'en convaincre). Une identité de Bézout n'est donc qu'un couple parmi une infinité — ce fait reviendra en section 4.3.

3.3 Recherche pratique : la remontée de l'algorithme d'Euclide

Méthode — trouver un couple de Bézout

On effectue l'algorithme d'Euclide pour obtenir $d=\operatorname{pgcd}(a,b)$ , puis on remonte les égalités une à une, de la dernière division utile jusqu'à la première, pour exprimer $d$ comme combinaison de $a$ et $b$ .

Exemple — coefficients de Bézout pour 252 et 198

La section 2 a donné (Figure 1) : $252=198\times1+54$ ; $198=54\times3+36$ ; $54=36\times1+\mathbf{18}$ ; $36=18\times2+0$ , donc $\operatorname{pgcd}(252,198)=18$ . Remontons à partir de l'avant-dernière ligne :

$18=54-36\times1$
$36=198-54\times3$ on réinjecte cette égalité
$\Rightarrow$ $18=54-(198-54\times3)\times1$
$=$ $54\times4-198\times1$
$54=252-198\times1$ on réinjecte une seconde fois
$\Rightarrow$ $18=(252-198)\times4-198$
$=$ $252\times4-198\times5$

Vérification : $252\times4-198\times5=1\,008-990=18$ . Le couple $(u,v)=(4,-5)$ convient.

3.4 Une première application : l'équation $ax+by=c$

Une équation dont on cherche uniquement les solutions entières s'appelle une équation diophantienne, du nom du mathématicien grec Diophante d'Alexandrie. Le théorème de Bézout répond entièrement à la question de l'existence de solutions pour $ax+by=c$ , d'inconnues $x,y$ .

Théorème — condition d'existence

Soient $a,b$ deux entiers non tous deux nuls, $c$ un entier, et $d=\operatorname{pgcd}(a,b)$ . L'équation $ax+by=c$ , d'inconnues $(x,y)\in\mathbb{Z}^{2}$ , admet au moins une solution si et seulement si $d\mid c$ .

Démonstration

Condition nécessaire. Si $(x,y)$ est solution, $d$ divise $a$ et $b$ , donc divise la combinaison $ax+by=c$ .

Condition suffisante. Si $d\mid c$ , écrivons $c=dk$ avec $k\in\mathbb{Z}$ . Par Bézout, il existe $u,v$ tels que $au+bv=d$ . En multipliant par $k$ :

$a(uk)+b(vk)=dk$
$=$ $c$

Le couple $(x,y)=(uk,vk)$ est donc une solution. C.Q.F.D.

Attention — vérifie toujours

d\mid c

L'équation $4x+6y=7$ n'a aucune solution entière : $\operatorname{pgcd}(4,6)=2$ et $2\nmid7$ ( $4x+6y$ est toujours pair, $7$ est impair). C'est le premier réflexe à avoir face à une équation diophantienne.

Exemple — une solution particulière de

12x+18y=30

$\operatorname{pgcd}(12,18)=6$ par l'algorithme d'Euclide
$30=6\times5$ donc $6\mid30$ : l'équation a des solutions
$12x+18y=30$
$\iff$ $2x+3y=5$ on divise les deux membres par $6$
$2\times(-1)+3\times1=1$ couple de Bézout pour $2$ et $3$
$\Rightarrow$ $2\times(-5)+3\times5=5$ on multiplie par $5$

Le couple $(x_{0},y_{0})=(-5,5)$ est une solution particulière. Reste à décrire toutes les solutions : ce sera l'objet de la section 4.3, avec le théorème de Gauss.

Math & Co — Un nom pour deux mathématiciens

Étienne Bézout (1730-1783), examinateur des élèves de la Marine puis de l'Artillerie royales françaises, établit ce résultat en 1779 dans sa Théorie générale des équations algébriques — pour des polynômes, un cadre bien plus général que celui des entiers. Mais pour les entiers, l'identité était connue plus d'un siècle avant lui : le Français Claude-Gaspard Bachet de Méziriac l'expose dès 1624 dans Problèmes plaisants et délectables qui se font par les nombres, comme méthode de résolution des équations en nombres entiers. L'histoire a retenu le nom de Bézout ; la priorité revient à Bachet.

4Théorème de Gauss

Le théorème de Bézout ouvre la voie à un second résultat, tout aussi central : le théorème de Gauss précise à quelle condition un nombre qui divise un produit est obligé de diviser l'un des deux facteurs. Il permet notamment de décrire toutes les solutions d'une équation diophantienne.

4.1 Énoncé et démonstration

Théorème de Gauss

Soient $a,b,c$ des entiers relatifs. Si $a\mid bc$ et si $\operatorname{pgcd}(a,b)=1$ , alors :

$a\mid c$

Démonstration

Comme $\operatorname{pgcd}(a,b)=1$ , le théorème de Bézout donne deux entiers $u,v$ tels que $au+bv=1$ . Multiplions par $c$ :

$acu+bcv=c$

Or $a\mid acu$ (facteur $a$ apparent), et $a\mid bcv$ car $a\mid bc$ par hypothèse. Donc $a$ divise la somme $acu+bcv$ , c'est-à-dire $a\mid c$ . C.Q.F.D.

Exemple — appliquer le théorème de Gauss

Sachant que $23\mid7n$ pour un entier $n$ , et que $\operatorname{pgcd}(23,7)=1$ (deux nombres premiers distincts), le théorème de Gauss donne directement $23\mid n$ .

Attention — l'hypothèse « premiers entre eux » est indispensable

Sans elle, la conclusion est fausse : $6\mid4\times3=12$ , pourtant $6\nmid4$ et $6\nmid3$ . Ici $\operatorname{pgcd}(6,4)=2\neq1$ : l'hypothèse du théorème n'est pas vérifiée, on n'a donc aucun droit de conclure.

4.2 Corollaires

Corollaire

Soient $a,b,c$ des entiers. Si $a\mid c$ , $b\mid c$ et $\operatorname{pgcd}(a,b)=1$ , alors :

$ab\mid c$

Démonstration

$c=ak$ $k\in\mathbb{Z}$ , car $a\mid c$
$b\mid ak$ car $b\mid c$
$\Rightarrow$ $b\mid k$ théorème de Gauss, $\operatorname{pgcd}(a,b)=1$
$k=bk'$ $k'\in\mathbb{Z}$
$\Rightarrow$ $c=a(bk')$
$=$ $(ab)k'$ donc $ab\mid c$

C.Q.F.D.

Exemple — utiliser le corollaire

On a $4\mid180$ et $9\mid180$ , avec $\operatorname{pgcd}(4,9)=1$ . Le corollaire donne $4\times9=36\mid180$ , ce que l'on vérifie : $180=36\times5$ .

Ce corollaire, combiné à la décomposition en facteurs premiers, justifiera en section 5 la formule liant PGCD et PPCM admise en section 2.

4.3 Résolution complète de l'équation $ax+by=c$

Propriété — simplifier par le pgcd

Si $d=\operatorname{pgcd}(a,b)$ , alors $\dfrac{a}{d}$ et $\dfrac{b}{d}$ sont premiers entre eux. En effet, Bézout donne $au+bv=d$ pour des entiers $u,v$ ; en divisant par $d$ , on obtient $\dfrac{a}{d}u+\dfrac{b}{d}v=1$ , donc $\operatorname{pgcd}\!\left(\dfrac{a}{d},\dfrac{b}{d}\right)=1$ par le corollaire de la section 3.2.

Théorème — solution générale

Soient $a,b$ des entiers non nuls, $d=\operatorname{pgcd}(a,b)$ , $c$ un multiple de $d$ , et $(x_{0},y_{0})$ une solution particulière de $ax+by=c$ . L'ensemble des solutions entières est exactement :

$\left\{\left(x_{0}+k\dfrac{b}{d},\ y_{0}-k\dfrac{a}{d}\right)\;\middle|\;k\in\mathbb{Z}\right\}$

Démonstration

Ces couples sont solutions. Pour tout $k\in\mathbb{Z}$ :

$a\left(x_{0}+k\dfrac{b}{d}\right)+b\left(y_{0}-k\dfrac{a}{d}\right)$
$=$ $ax_{0}+by_{0}+k\dfrac{ab}{d}-k\dfrac{ab}{d}$
$=$ $ax_{0}+by_{0}$
$=$ $c$ car $(x_{0},y_{0})$ est solution

Il n'y en a pas d'autres. Soit $(x,y)$ une solution quelconque. En soustrayant $ax_{0}+by_{0}=c$ à $ax+by=c$ :

$a(x-x_{0})+b(y-y_{0})=0$
$\Rightarrow$ $\dfrac{a}{d}(x-x_{0})=\dfrac{b}{d}(y_{0}-y)$ on divise par $d$ et on réarrange

Comme $\dfrac{a}{d}$ divise $\dfrac{b}{d}(y_{0}-y)$ et que $\dfrac{a}{d}$ et $\dfrac{b}{d}$ sont premiers entre eux (propriété ci-dessus), le théorème de Gauss donne $\dfrac{a}{d}\mid(y_{0}-y)$ : il existe $k\in\mathbb{Z}$ tel que $y_{0}-y=k\dfrac{a}{d}$ , soit $y=y_{0}-k\dfrac{a}{d}$ . En reportant dans l'égalité précédente puis en simplifiant par $\dfrac{a}{d}$ (non nul), on obtient $x-x_{0}=k\dfrac{b}{d}$ , soit $x=x_{0}+k\dfrac{b}{d}$ . C.Q.F.D.

Méthode — résoudre entièrement

ax+by=c

① Calculer $d=\operatorname{pgcd}(a,b)$ par Euclide et vérifier que $d\mid c$ (sinon : aucune solution). ② Simplifier par $d$ pour obtenir $a'x+b'y=c'$ avec $a',b'$ premiers entre eux. ③ Trouver une solution particulière $(x_{0},y_{0})$ par remontée d'Euclide. ④ Écrire la solution générale $x=x_{0}+kb'$ , $y=y_{0}-ka'$ , $k\in\mathbb{Z}$ .

Exemple — solution générale de

2x+3y=5

La section 3.4 a donné la solution particulière $(x_{0},y_{0})=(-5,5)$ , avec $a'=2$ et $b'=3$ déjà premiers entre eux.

$x=-5+3k,\quad y=5-2k,\quad k\in\mathbb{Z}$

Vérification pour $k=2$ : $x=1$ , $y=1$ , et $2\times1+3\times1=5$ . La figure 2 montre ces solutions : des points régulièrement espacés sur la droite d'équation $2x+3y=5$ .

Figure 2 — Les solutions entières de

2x+3y=5

forment une suite de points régulièrement espacés sur la droite : d'une solution à la suivante,

x

augmente de

3

y

diminue de

2

Attention

Le signe « $-$ » devant $k\dfrac{a}{d}$ dans la formule de $y$ n'est pas arbitraire : il vient directement de la démonstration. En cas de doute, redémontre-le au brouillon, ou vérifie ta formule en substituant deux valeurs de $k$ dans l'équation de départ.

5Nombres premiers et décomposition

Les nombres premiers sont les briques élémentaires de l'arithmétique : tout entier s'obtient en les multipliant entre eux, d'une seule façon. Cette section démontre qu'il en existe une infinité, présente un algorithme antique pour les répertorier, et énonce le théorème qui organise autour d'eux tous les entiers.

5.1 Nombres premiers et leur infinité

Définition

Un entier $p\geqslant2$ est premier lorsque ses seuls diviseurs positifs sont $1$ et $p$ . Un entier $n\geqslant2$ non premier est dit composé : il a un diviseur $d$ tel que $1<d<n$ .

Rappelons un fait utile : tout entier $n\geqslant2$ possède au moins un diviseur premier. En effet, l'ensemble de ses diviseurs $\geqslant2$ est non vide (il contient $n$ ) : il admet un plus petit élément $p$ , qui est premier — un diviseur strict de $p$ autre que $1$ diviserait aussi $n$ et serait plus petit que $p$ , contredisant sa minimalité.

Théorème — infinité des nombres premiers

Il existe une infinité de nombres premiers.

Démonstration — Euclide, par l'absurde

Supposons qu'il n'en existe qu'un nombre fini $p_{1},p_{2},\ldots,p_{n}$ . Considérons :

$N=p_{1}\times p_{2}\times\cdots\times p_{n}+1$

$N$ admet un diviseur premier $p$ (fait rappelé ci-dessus). Ce $p$ est nécessairement l'un des $p_{i}$ , puisque la liste est censée être complète. Or $p_{i}$ divise le produit $p_{1}\times\cdots\times p_{n}$ , donc $p_{i}$ diviserait aussi $N-p_{1}\times\cdots\times p_{n}=1$ : impossible pour un nombre premier. Contradiction. C.Q.F.D.

Exemple — tester la primalité de 97

Il suffit de tester les diviseurs premiers $\leqslant\sqrt{97}\approx9{,}8$ , soit $2,3,5,7$ :

$97$ est impair ; $9+7=16$ n'est pas multiple de $3$ ; $97$ ne finit ni par $0$ ni par $5$
$97=7\times13+6$ $7$ ne divise pas $97$
$\Rightarrow$ $97$ est premier

5.2 Le crible d'Ératosthène

Méthode — cribler les nombres premiers jusqu'à

N

On écrit tous les entiers de $2$ à $N$ . On raye les multiples de $2$ (sauf $2$ ), puis les multiples du plus petit nombre restant, et ainsi de suite, en s'arrêtant dès que ce plus petit nombre dépasse $\sqrt{N}$ : au-delà, tout composé restant aurait déjà été rayé. Les nombres jamais rayés sont premiers.

Figure 3 — Après avoir rayé les multiples de

2

3

5

(suffisant car

\sqrt{30}\approx5{,}5

), les

10

nombres entourés sont exactement les nombres premiers inférieurs à

30

5.3 Décomposition en facteurs premiers

Théorème — décomposition (admis)

Tout entier $n\geqslant2$ se décompose, de façon unique à l'ordre des facteurs près, en produit de nombres premiers :

$n=p_{1}^{\alpha_{1}}\times p_{2}^{\alpha_{2}}\times\cdots\times p_{k}^{\alpha_{k}}$

où $p_{1}<p_{2}<\cdots<p_{k}$ sont premiers et $\alpha_{1},\ldots,\alpha_{k}\in\mathbb{N}^{*}$ .

L'existence se démontre par récurrence forte, en extrayant à chaque étape un diviseur premier (section 5.1) puis en recommençant sur le quotient ; l'unicité, plus délicate, s'appuie sur le théorème de Gauss appliqué successivement à chaque facteur. Nous l'admettons.

Exemple — décomposer 504

$504=2\times252$
$=$ $2\times2\times126$
$=$ $2^{3}\times63$
$=$ $2^{3}\times3^{2}\times7$

Propriété — nombre de diviseurs

Si $n=p_{1}^{\alpha_{1}}\times\cdots\times p_{k}^{\alpha_{k}}$ , le nombre de diviseurs positifs de $n$ est $(\alpha_{1}+1)\times\cdots\times(\alpha_{k}+1)$ .

Exemple — diviseurs de 504

$(3+1)\times(2+1)\times(1+1)$
$=$ $4\times3\times2$
$=$ $24$ $504$ possède $24$ diviseurs positifs

Propriété — PGCD, PPCM et décomposition

Pour chaque facteur premier commun, le plus petit exposant donne le pgcd, le plus grand donne le ppcm. Comme $\min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta$ , on retrouve la formule admise en 2.4 : $\operatorname{pgcd}(a,b)\times\operatorname{ppcm}(a,b)=|ab|$ .

Math & Co — Ératosthène, le géomètre de la Terre

Ératosthène de Cyrène (vers $-276$ à $-194$ ), troisième directeur de la bibliothèque d'Alexandrie, n'est pas qu'un cribleur de nombres : vers $-240$ , en comparant l'angle du Soleil à midi entre Alexandrie et Syène (l'actuelle Assouan), il calcule le premier la circonférence de la Terre, avec moins de $2\,\%$ d'erreur. Son crible, décrit par Nicomaque de Gérase au Ier siècle, reste la méthode la plus simple pour dresser à la main une liste de nombres premiers.

6Congruences dans ℤ

Nous voici au cœur du chapitre. La congruence formalise une idée simple : ne retenir d'un nombre que son reste par $n$ , en oubliant le quotient — une simplification étonnamment puissante, comme le montrera la section 7.

6.1 Définition et compatibilité avec les opérations

Définition

Soit $n\in\mathbb{N}^{*}$ . Deux entiers $a$ et $b$ sont congrus modulo $n$ lorsque $n$ divise $a-b$ :

$a\equiv b\pmod n \quad\Longleftrightarrow\quad n\mid(a-b)$

Propriété — caractérisation par le reste

$a\equiv b\pmod n$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$ .

Démonstration

Notons $a=nq+r$ et $b=nq'+r'$ les divisions euclidiennes de $a$ et $b$ par $n$ , avec $0\leqslant r,r'<n$ .

$a-b=n(q-q')+(r-r')$

Si $r=r'$ , $a-b=n(q-q')$ est multiple de $n$ . Réciproquement, si $n\mid(a-b)$ , alors $n\mid(r-r')$ d'après l'égalité ci-dessus ; or $-n<r-r'<n$ , donc $r-r'=0$ . C.Q.F.D.

Propriété — compatibilité avec

+

\times

Si $a\equiv b\pmod n$ et $c\equiv d\pmod n$ , alors $a+c\equiv b+d\pmod n$ et $ac\equiv bd\pmod n$ .

Démonstration

Par hypothèse, $a-b=kn$ et $c-d=k'n$ pour deux entiers $k,k'$ .

Somme.

$(a+c)-(b+d)=(a-b)+(c-d)$
$=$ $kn+k'n$
$=$ $n(k+k')$ multiple de $n$

Produit. On écrit $a=b+kn$ et $c=d+k'n$ :

$ac=(b+kn)(d+k'n)$
$=$ $bd+bk'n+dkn+kk'n^{2}$
$=$ $bd+n(bk'+dk+kk'n)$ multiple de $n$ ajouté à $bd$

Donc $ac-bd$ est multiple de $n$ . C.Q.F.D.

Par récurrence immédiate, la compatibilité s'étend aux puissances : $a\equiv b\pmod n\ \Rightarrow\ a^{p}\equiv b^{p}\pmod n$ pour tout $p\geqslant1$ . C'est ce qui rend les congruences si efficaces pour calculer des restes de grands nombres.

Exemple — calculer un reste par congruence

Reste de $15\times23$ dans la division par $7$ :

$15\equiv1\pmod7$ $15=2\times7+1$
$23\equiv2\pmod7$ $23=3\times7+2$
$\Rightarrow$ $15\times23\equiv1\times2\pmod7$ compatibilité avec $\times$
$\equiv$ $2\pmod7$

Le reste de $15\times23=345$ par $7$ est $2$ , sans poser la division de $345$ .

Attention

La compatibilité avec $\times$ n'a pas d'équivalent pour la division : de $ac\equiv bc\pmod n$ on ne peut pas toujours simplifier en $a\equiv b\pmod n$ . Exemple : $2\times2\equiv2\times5\pmod6$ (les deux valent $4$ ), pourtant $2\not\equiv5\pmod6$ . La simplification n'est licite que si $\operatorname{pgcd}(c,n)=1$ (théorème de Gauss).

6.2 Puissances et cycles de restes

Calculer $2^{100}\pmod7$ directement est hors de portée. Mais les restes des puissances successives d'un nombre modulo $n$ sont périodiques : il n'existe que $n$ restes possibles.

$n$	1	2	3	4	5	6
$2^{n}\bmod7$	2	4	1	2	4	1

Méthode — calculer

a^{N}\pmod n

On calcule les restes de $a^{1},a^{2},a^{3},\ldots$ modulo $n$ jusqu'à revoir un reste déjà obtenu : cela signale un cycle de période $T$ . On effectue alors la division euclidienne $N=Tq+s$ , et $a^{N}\equiv a^{s}\pmod n$ (ou $a^{T}$ si $s=0$ ).

Exemple — reste de

2^{100}

modulo 7

Le tableau montre un cycle de période $T=3$ : $2,4,1,2,4,1,\ldots$

$100=3\times33+1$ division de l'exposant par la période
$\Rightarrow$ $2^{100}\equiv2^{1}\pmod7$
$\equiv$ $2\pmod7$

Figure 4 — Sur l'horloge à

7

positions, additionner revient à tourner : partant de

5

et avançant de

4

crans, on arrive sur

2

, exactement comme

5+4\equiv2\pmod7

6.3 Petit théorème de Fermat

Petit théorème de Fermat

Soit $p$ premier et $a$ un entier tel que $p\nmid a$ . Alors $a^{p-1}\equiv1\pmod p$ . De façon équivalente, pour tout entier $a$ : $a^{p}\equiv a\pmod p$ .

Idée de la preuve : si $p\nmid a$ , les restes de $a,2a,\ldots,(p-1)a$ modulo $p$ sont non nuls et deux à deux distincts — ce sont donc, dans un autre ordre, exactement $1,2,\ldots,p-1$ . En multipliant ces $p-1$ congruences membre à membre puis en simplifiant par $(p-1)!$ (licite car $\operatorname{pgcd}((p-1)!,p)=1$ , par Gauss), on obtient $a^{p-1}\equiv1\pmod p$ .

Exemple — reste de

2^{10}

modulo 11

$11$ est premier et $11\nmid2$ , donc $2^{10}\equiv1\pmod{11}$ directement par Fermat — ce qui explique pourquoi la période du cycle des restes de $2^{n}$ modulo un premier $p$ divise toujours $p-1$ . Attention : l'hypothèse « $p$ premier » est indispensable — pour un module composé, rien ne garantit $a^{n-1}\equiv1\pmod n$ .

7Applications : critères de divisibilité, codage

Il est temps de récolter les fruits de ce chapitre : les congruences expliquent la preuve par $9$ , la clé qui protège un numéro de compte ou un livre, le jour de la semaine d'une date future, et le principe qui protège tes échanges sur internet.

7.1 Critères de divisibilité par 3, 9 et 11

Théorème — critères par 3 et par 9

Un entier naturel $n$ , de chiffres $a_{k}a_{k-1}\ldots a_{1}a_{0}$ en écriture décimale, est congru modulo $9$ (et modulo $3$ ) à la somme de ses chiffres :

$n\equiv a_{k}+a_{k-1}+\cdots+a_{0}\pmod9$

En particulier, $n$ est divisible par $9$ (resp. $3$ ) si et seulement si la somme de ses chiffres l'est.

Démonstration

$n=\displaystyle\sum_{i=0}^{k}a_{i}\times10^{i}$ . Or $10\equiv1\pmod9$ , donc $10^{i}\equiv1\pmod9$ pour tout $i$ (compatibilité avec les puissances). Par compatibilité avec $+$ et $\times$ :

$n=\displaystyle\sum_{i=0}^{k}a_{i}\times10^{i}$
$\equiv$ $\displaystyle\sum_{i=0}^{k}a_{i}\times1\pmod9$
$\equiv$ $a_{k}+\cdots+a_{0}\pmod9$

Le même raisonnement avec $10\equiv1\pmod3$ donne le critère modulo $3$ . C.Q.F.D.

Théorème — critère par 11

$n$ est congru modulo $11$ à la somme alternée de ses chiffres, $a_{0}-a_{1}+a_{2}-\cdots\pmod{11}$ : $n$ est divisible par $11$ si et seulement si cette somme alternée l'est.

Même démonstration, en remarquant que $10\equiv-1\pmod{11}$ , donc $10^{i}\equiv(-1)^{i}\pmod{11}$ .

Exemple — appliquer les trois critères à 8 624

$8+6+2+4=20$ somme des chiffres
$20$ n'est multiple ni de $3$ ni de $9$ $8\,624$ n'est divisible ni par $3$ ni par $9$
$4-2+6-8=0$ somme alternée depuis les unités
$\Rightarrow$ $0$ est multiple de $11$ donc $11\mid8\,624$ ; en effet $8\,624=11\times784$

7.2 Clés de contrôle : ISBN et RIB

Une clé de contrôle est un chiffre supplémentaire, calculé par congruence à partir des autres, qui permet de détecter automatiquement une erreur de saisie ou de transmission.

Règle de l'ISBN à 10 chiffres

Un ISBN-10 $a_{1}\ldots a_{10}$ vérifie $\displaystyle\sum_{i=1}^{10}i\times a_{i}\equiv0\pmod{11}$ ; le dernier chiffre $a_{10}$ (la clé) peut valoir $10$ , noté $X$ .

Exemple — vérifier la clé d'un ISBN

Vérifions l'ISBN $1\text{-}234\text{-}56789\text{-}X$ (chiffres $1,2,3,4,5,6,7,8,9,10$ ) :

$1\times1+2\times2+3\times3+4\times4+5\times5+6\times6+7\times7+8\times8+9\times9+10\times10$
$=$ $1+4+9+16+25+36+49+64+81+100$
$=$ $385$
$385=11\times35$ reste nul
$\Rightarrow$ la clé $X$ (soit $10$ ) est correcte

Le même principe protège d'autres identifiants : la clé RIB bancaire se calcule par $\text{clé}=97-(r\bmod97)$ ; codes-barres EAN et numéros d'immatriculation utilisent des sommes pondérées analogues, modulo $10$ ou $11$ .

7.3 Calendrier perpétuel

Les jours de la semaine se répètent avec une période de $7$ : si l'on numérote les jours $0$ (lundi) à $6$ (dimanche), connaître le jour d'une date de référence permet, par congruence modulo $7$ , de trouver le jour de n'importe quelle autre date.

Exemple — quel jour tombe le 14 juillet 2026 ?

Le 1er janvier 2026 est un jeudi (jour $3$ ). Comptons les jours écoulés jusqu'au 14 juillet 2026 ( $2026$ n'est pas bissextile) : $31+28+31+30+31+30+13=194$ .

$194=7\times27+5$ division euclidienne par $7$
$\Rightarrow$ jour $\equiv3+5\pmod7$
$\equiv$ $1\pmod7$

Le jour $1$ correspond à mardi : le 14 juillet 2026 tombe un mardi.

7.4 Chiffrement affine et introduction au RSA

En associant à chaque lettre un entier de $0$ (A) à $25$ (Z), on la chiffre par $x\mapsto ax+b\pmod{26}$ , avec $\operatorname{pgcd}(a,26)=1$ pour rester déchiffrable — Bézout donne alors l'inverse de $a$ modulo $26$ .

Exemple — chiffrer avec

x\mapsto3x+5\pmod{26}

La lettre $\text{E}$ ( $x=4$ ) devient :

$3\times4+5=17$ $17$ correspond à la lettre $\text{R}$

Le système RSA, qui sécurise une grande partie d'internet, généralise cette idée par $x\mapsto x^{e}\pmod N$ , où $N=pq$ est le produit de deux très grands nombres premiers secrets : sa sécurité tient à ce que factoriser $N$ soit, en pratique, infaisable. Chaque outil de ce chapitre — Euclide, Bézout, Gauss, congruences — trouve ainsi une utilité concrète dans les technologies qui t'entourent.

Fiche mémo

$b\mid a\iff\exists k\in\mathbb{Z},\ a=bk$ ; division euclidienne : $a=bq+r$ , $0\leqslant r<b$ , $(q,r)$ uniques.
Euclide : $\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r)$ ; le pgcd est le dernier reste non nul.
$\operatorname{pgcd}(a,b)\times\operatorname{ppcm}(a,b)=|ab|$ .
Bézout : $\exists u,v\in\mathbb{Z},\ au+bv=\operatorname{pgcd}(a,b)$ ; $a,b$ premiers entre eux $\iff\exists u,v,\ au+bv=1$ .
Gauss : $a\mid bc$ et $\operatorname{pgcd}(a,b)=1\ \Rightarrow\ a\mid c$ .
$ax+by=c$ a des solutions $\iff\operatorname{pgcd}(a,b)\mid c$ ; solution générale $x=x_{0}+k\dfrac{b}{d}$ , $y=y_{0}-k\dfrac{a}{d}$ .
Nombre premier : seuls diviseurs $1$ et lui-même ; infinité de nombres premiers (Euclide).
Décomposition : $n=p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}}$ (unique) ; nombre de diviseurs $=(\alpha_{1}+1)\cdots(\alpha_{k}+1)$ .
$a\equiv b\pmod n\iff n\mid(a-b)\iff$ même reste par $n$ ; compatible avec $+$ , $\times$ , puissances.
Petit théorème de Fermat : $p$ premier, $p\nmid a\ \Rightarrow\ a^{p-1}\equiv1\pmod p$ .
Divisible par $9$ (ou $3$ ) $\iff$ somme des chiffres divisible par $9$ (ou $3$ ) ; par $11$ $\iff$ somme alternée divisible par $11$ .
Clé de contrôle, calendrier, chiffrement : toujours une somme pondérée prise modulo un entier fixé.

8Exercices corrigés

Niveau 1 — Application directe

Effectue la division euclidienne de $1\,000$ par $37$ , puis celle de $-58$ par $9$ .

Voir le corrigé détaillé

$37\times27=999$
$1\,000=37\times27+1$ $0\leqslant1<37$ : $q=27$ , $r=1$
$9\times(-7)=-63$
$-58=9\times(-7)+5$ $0\leqslant5<9$ : $q=-7$ , $r=5$

Calcule $\operatorname{pgcd}(198,84)$ par l'algorithme d'Euclide, puis déduis-en $\operatorname{ppcm}(198,84)$ .

Voir le corrigé détaillé

$198=84\times2+30$
$84=30\times2+24$
$30=24\times1+6$
$24=6\times4+0$
$\Rightarrow$ $\operatorname{pgcd}(198,84)=6$ dernier reste non nul
$6\times\operatorname{ppcm}(198,84)=198\times84$
$\Rightarrow$ $\operatorname{ppcm}(198,84)=2\,772$

Détermine un couple de Bézout $(u,v)$ tel que $48u+18v=\operatorname{pgcd}(48,18)$ .

Voir le corrigé détaillé

$48=18\times2+12$
$18=12\times1+6$
$12=6\times2+0$ $\operatorname{pgcd}(48,18)=6$
$6=18-12\times1$
$12=48-18\times2$ on réinjecte
$\Rightarrow$ $6=18-(48-18\times2)$
$=$ $48\times(-1)+18\times3$

Le couple $(u,v)=(-1,3)$ convient.

Résous dans $\mathbb{Z}^{2}$ l'équation $5x+3y=1$ .

Voir le corrigé détaillé

$\operatorname{pgcd}(5,3)=1$ , qui divise $1$ : l'équation a des solutions.

$5\times(-1)+3\times2=-5+6$
$=$ $1$ couple particulier $(x_{0},y_{0})=(-1,2)$
$x=-1+3k,\quad y=2-5k,\quad k\in\mathbb{Z}$

Détermine le reste de $37\times48$ dans la division par $9$ , sans calculer le produit.

Voir le corrigé détaillé

$37\equiv1\pmod9$ $37=4\times9+1$
$48\equiv3\pmod9$ $48=5\times9+3$
$\Rightarrow$ $37\times48\equiv1\times3\pmod9$
$\equiv$ $3\pmod9$

Décompose $360$ en produit de facteurs premiers, puis donne le nombre de ses diviseurs positifs.

Voir le corrigé détaillé

$360=2\times180$
$=$ $2^{2}\times90$
$=$ $2^{3}\times45$
$=$ $2^{3}\times3^{2}\times5$
$(3+1)\times(2+1)\times(1+1)$
$=$ $24$ $360$ possède $24$ diviseurs positifs

Niveau 2 — Approfondissement

Montre que $17$ et $25$ sont premiers entre eux en exhibant un couple de Bézout, puis démontre : si $17\mid25n$ , alors $17\mid n$ .

Voir le corrigé détaillé

$25=17\times1+8$
$17=8\times2+1$ $\operatorname{pgcd}(17,25)=1$
$1=17-8\times2$
$8=25-17$ on réinjecte
$\Rightarrow$ $1=17-(25-17)\times2$
$=$ $17\times3+25\times(-2)$

Le couple $(3,-2)$ confirme $\operatorname{pgcd}(17,25)=1$ . Comme $17\mid25n$ et $\operatorname{pgcd}(17,25)=1$ , le théorème de Gauss donne $17\mid n$ .

Résous entièrement dans $\mathbb{Z}^{2}$ l'équation $20x+12y=16$ .

Voir le corrigé détaillé

$\operatorname{pgcd}(20,12)=4$ Euclide : $20=12\times1+8$ , $12=8\times1+4$ , $8=4\times2+0$
$4\mid16$ l'équation a des solutions
$20x+12y=16$
$\iff$ $5x+3y=4$ on divise par $4$
$5\times(-4)+3\times8=4$ d'après l'exercice 4, coefficients $\times4$
$\Rightarrow$ $x=-4+3k,\quad y=8-5k,\quad k\in\mathbb{Z}$

Détermine le reste de $3^{47}$ dans la division par $13$ .

Voir le corrigé détaillé

$3^{2}=9$
$3^{3}=27$
$\equiv$ $1\pmod{13}$ cycle de période $T=3$ : $3,9,1,3,9,1,\ldots$
$47=3\times15+2$
$\Rightarrow$ $3^{47}\equiv3^{2}\pmod{13}$
$\equiv$ $9\pmod{13}$

Remarque : $13$ est premier, donc par Fermat $3^{12}\equiv1\pmod{13}$ ; la période $3$ trouvée divise bien $12$ .

Détermine les chiffres $x$ et $y$ tels que $N=\overline{1\,x\,2\,7\,y}$ soit divisible à la fois par $9$ et par $11$ .

Voir le corrigé détaillé

$1+x+2+7+y=10+x+y$ somme des chiffres, $N$ div. par $9$
$\Rightarrow$ $x+y\equiv8\pmod9$
$y-7+2-x+1=y-x-4$ somme alternée, $N$ div. par $11$
$\Rightarrow$ $y-x\equiv4\pmod{11}$

Avec $x,y$ chiffres ( $0$ à $9$ ), $x+y=8$ et $y-x=4$ donnent $y=6$ , $x=2$ ; les autres combinaisons possibles conduisent à des valeurs hors de $[0\,;\,9]$ . Vérification : $N=12\,276=9\times1\,364=11\times1\,116$ .

Niveau 3 — Type bac

On considère l'équation $(E)\ :\ 15x-24y=9$ , d'inconnue $(x,y)\in\mathbb{Z}^{2}$ .

Déterminer $d=\operatorname{pgcd}(15,24)$ et vérifier que $(E)$ admet des solutions.
Trouver une solution particulière de $(E)$ , puis résoudre entièrement $(E)$ .
Déterminer la solution pour laquelle $x$ est strictement positif et minimal.

Voir le corrigé détaillé

$24=15\times1+9$
$15=9\times1+6$
$9=6\times1+3$
$6=3\times2+0$
$\Rightarrow$ $d=\operatorname{pgcd}(15,24)=3$

$3\mid9$ : $(E)$ admet des solutions, équivalente à $5x-8y=3$ après division par $3$ .

2. Remontée pour $\operatorname{pgcd}(5,8)$ :

$8=5\times1+3$
$5=3\times1+2$
$3=2\times1+1$
$1=3-2\times1$
$2=5-3\times1$ on réinjecte
$\Rightarrow$ $1=3-(5-3)$
$=$ $3\times2-5$
$3=8-5\times1$ on réinjecte encore
$\Rightarrow$ $1=(8-5)\times2-5$
$=$ $8\times2-5\times3$

Donc $5\times(-3)+8\times2=1$ , et en multipliant par $3$ : $5\times(-9)+8\times6=3$ . Comme $8\times6=-8\times(-6)$ , le couple $(x_{0},y_{0})=(-9,-6)$ vérifie $5x_{0}-8y_{0}=3$ . Solution générale :

$x=-9-8k,\quad y=-6-5k,\quad k\in\mathbb{Z}$

3. On veut $x=-9-8k>0$ , soit $k<-\dfrac{9}{8}$ , donc $k\leqslant-2$ ; $x$ est minimal pour le plus grand $k$ possible, $k=-2$ :

$x=-9-8\times(-2)=7$
$y=-6-5\times(-2)=4$

La solution cherchée est $(x,y)=(7,4)$ — on vérifie $15\times7-24\times4=105-96=9$ .

Restitution organisée de connaissances. Démontre que, pour tout entier naturel $n$ , $n^{3}-n$ est divisible par $6$ .

Voir le corrigé détaillé

On factorise : $n^{3}-n=n(n-1)(n+1)$ , produit de trois entiers consécutifs.

Divisibilité par $2$ . Parmi $n-1$ et $n$ , l'un des deux est pair (deux entiers consécutifs), donc $2\mid n(n-1)$ , donc $2\mid n(n-1)(n+1)$ .

Divisibilité par $3$ . Trois cas selon le reste de $n$ modulo $3$ :

si $n\equiv0\pmod3$ : $3\mid n$
si $n\equiv1\pmod3$ : $n-1\equiv0\pmod3$ , donc $3\mid(n-1)$
si $n\equiv2\pmod3$ : $n+1\equiv0\pmod3$ , donc $3\mid(n+1)$

Dans tous les cas, $3\mid n(n-1)(n+1)$ . Comme $2\mid n^{3}-n$ , $3\mid n^{3}-n$ et $\operatorname{pgcd}(2,3)=1$ , le corollaire du théorème de Gauss (section 4.2) donne $2\times3=6\mid n^{3}-n$ . C.Q.F.D.

Un entier naturel $N$ vérifie $N\equiv2\pmod5$ et $N\equiv3\pmod7$ .

Montre que $N-17$ est divisible par $5$ et par $7$ .
En déduire que $N\equiv17\pmod{35}$ .
Détermine le plus petit entier naturel $N>100$ vérifiant ces conditions.

Voir le corrigé détaillé

1. $17\equiv2\pmod5$ et $N\equiv2\pmod5$ , donc $N-17\equiv0\pmod5$ . De même, $17\equiv3\pmod7$ et $N\equiv3\pmod7$ , donc $N-17\equiv0\pmod7$ .

2. $5\mid(N-17)$ , $7\mid(N-17)$ et $\operatorname{pgcd}(5,7)=1$ : le corollaire de Gauss donne $5\times7=35\mid(N-17)$ , soit $N\equiv17\pmod{35}$ .

$N=17+35k,\quad k\in\mathbb{N}$
$17+35k>100$
$\Rightarrow$ $k>\dfrac{83}{35}\approx2{,}37$
$\Rightarrow$ $k=3$ plus petit entier convenant
$N=17+35\times3$
$=$ $122$

Niveau 4 — Problèmes de vie courante

Le partage du commerçant (Bamako). Un commerçant du grand marché de Bamako possède $84$ sacs de mil et $126$ sacs de riz. Il veut les répartir dans des paniers identiques, chaque panier ne contenant qu'une seule céréale, sans qu'aucun sac ne reste inutilisé, en mettant le plus grand nombre possible de sacs par panier.

Combien de sacs identiques le commerçant peut-il mettre au maximum dans chaque panier ?
Combien de paniers utilisera-t-il en tout ?

Voir le corrigé détaillé

1. Le nombre de sacs par panier doit diviser à la fois $84$ et $126$ ; le maximum recherché est $\operatorname{pgcd}(84,126)$ .

$126=84\times1+42$
$84=42\times2+0$
$\Rightarrow$ $\operatorname{pgcd}(84,126)=42$

Le commerçant peut mettre $42$ sacs par panier.

$84\div42=2$ paniers de mil
$126\div42=3$ paniers de riz
$\Rightarrow$ $2+3=5$ paniers au total

La bibliothèque de Dakar. Un ouvrage de la bibliothèque universitaire de Dakar porte l'ISBN $2\text{-}7071\text{-}1234\text{-}?$ , dont le dernier chiffre (la clé) est effacé. Détermine cette clé.

Voir le corrigé détaillé

Les neuf premiers chiffres sont $2,7,0,7,1,1,2,3,4$ .

$1\times2+2\times7+3\times0+4\times7+5\times1+6\times1+7\times2+8\times3+9\times4$
$=$ $2+14+0+28+5+6+14+24+36$
$=$ $129$
$129\equiv8\pmod{11}$ $129=11\times11+8$
$10\equiv-1\pmod{11}$
$\Rightarrow$ $8+10a_{10}\equiv8-a_{10}\pmod{11}$
$8-a_{10}\equiv0\pmod{11}$ condition de validité de la clé
$\Rightarrow$ $a_{10}\equiv8\pmod{11}$

La clé manquante est $8$ .

Jeu d'énigmes à Douala. Pour un jeu organisé à Douala, chaque lettre (numérotée de $0$ pour A à $25$ pour Z) est codée par $x\mapsto5x+8\pmod{26}$ . La première lettre du message codé est $\text{P}$ ( $x=15$ ). Quelle est la lettre d'origine ?

Voir le corrigé détaillé

Il faut d'abord inverser $5$ modulo $26$ par l'algorithme d'Euclide :

$26=5\times5+1$
$\Rightarrow$ $1=26-5\times5$
$\Rightarrow$ $5\times(-5)\equiv1\pmod{26}$
$-5\equiv21\pmod{26}$ inverse de $5$ : c'est $21$

Notons $y$ la lettre d'origine : $5y+8\equiv15\pmod{26}$ .

$5y\equiv7\pmod{26}$
$\Rightarrow$ $y\equiv21\times7\pmod{26}$
$\equiv$ $147\pmod{26}$
$\equiv$ $17\pmod{26}$

La lettre d'origine est $\text{R}$ ( $y=17$ ). Vérification : $5\times17+8=93\equiv15\pmod{26}$ , soit $\text{P}$ .

Teste-toi gratuitement

8 questions

Nombres complexes : forme algébrique et trigonométrique

Commencer →

8 questions

Logarithme népérien et exponentielle

Commencer →

📝 QCM de fin de leçon — 20 questions

Coche une réponse par question, puis clique sur « Vérifier mes réponses » : tu obtiens ta note sur 20 avec la correction détaillée de chaque question.

« $b$ divise $a$ », noté $b \mid a$ , signifie qu'il existe un entier $k$ tel que :

b = ak

k = ab

a = bk

a + b = k

Explication : Par définition,

b\mid a

signifie qu'il existe

k\in\mathbb{Z}

tel que

a = bk

b

est le diviseur,

a

le multiple.

Dans la division euclidienne de $a$ par $b$ ( $b\in\mathbb{N}^*$ ), le couple $(q,r)$ vérifie :

a = bq + r

avec

r

quelconque

a = bq + r

avec

0 \leqslant r < b

a = qr + b

avec

0 \leqslant r < b

a = bq - r

avec

0 \leqslant r < b

Explication : Le théorème de la division euclidienne garantit l'existence et l'unicité de

(q,r)

tels que

a=bq+r

avec

0\leqslant r<b

La division euclidienne de $a = -7$ par $b = 3$ donne :

q=-2

r=-1

q=-3

r=-2

q=-2

r=1

q=-3

r=2

Explication : Il faut

0\leqslant r<3

. Or

-7 = 3\times(-3)+2

, avec

0\leqslant2<3

: le reste

-1

obtenu par troncature vers zéro est interdit, jamais négatif.

Si $a \mid b$ et $a \mid c$ , alors pour tous entiers $u, v$ :

a \mid (bu + cv)

a \mid (b - c)

seulement

bu + cv \mid a

a

divise

u

v

Explication : C'est la propriété de combinaison linéaire : un diviseur commun de

b

c

divise toute combinaison entière

bu+cv

. C'est le principe caché derrière l'algorithme d'Euclide.

L'algorithme d'Euclide repose sur la propriété : si $r$ est le reste de la division de $a$ par $b$ , alors :

\operatorname{pgcd}(a,b) = a - b

\operatorname{pgcd}(a,b) = r

\operatorname{pgcd}(a,b) = \operatorname{pgcd}(b,r)

\operatorname{pgcd}(a,b) = \operatorname{pgcd}(a,r)

Explication : Les couples

(a,b)

(b,r)

ont exactement les mêmes diviseurs communs, donc le même pgcd : c'est le principe de l'algorithme d'Euclide.

Dans l'algorithme d'Euclide, le PGCD est :

le premier reste obtenu le dernier reste non nul toujours égal à

1

le dernier quotient calculé

Explication : On répète les divisions jusqu'à obtenir un reste nul ; le PGCD est le dernier reste non nul obtenu juste avant.

Calcule $\operatorname{pgcd}(150, 40)$ par l'algorithme d'Euclide.

5

20

2

10

Explication :

150 = 40\times3+30

40 = 30\times1+10

30 = 10\times3+0

dernier reste non nul :

\operatorname{pgcd}(150,40)=10

Deux entiers $a$ et $b$ sont premiers entre eux lorsque :

\operatorname{pgcd}(a,b) = 1

a

b

sont tous deux des nombres premiers

\operatorname{ppcm}(a,b) = 1

a

b

n'ont aucun diviseur commun autre que

0

Explication : Par définition,

a

b

sont premiers entre eux si leur seul diviseur positif commun est

1

, c'est-à-dire

\operatorname{pgcd}(a,b)=1

— cela n'exige pas que

a

b

soit lui-même premier (ex.

8

15

Sachant $\operatorname{pgcd}(36, 24) = 12$ , quel est $\operatorname{ppcm}(36, 24)$ ?

864

36

72

12

Explication :

\operatorname{pgcd}(a,b)\times\operatorname{ppcm}(a,b)=|ab|

, donc

12\times\operatorname{ppcm}=36\times24=864

\operatorname{ppcm}(36,24) = 864/12 = 72

Le théorème de Bézout affirme que si $d = \operatorname{pgcd}(a,b)$ , alors il existe des entiers relatifs $u,v$ tels que :

au \times bv = d

au - bv = 0

a + b = d(u+v)

au + bv = d

Explication : Le théorème de Bézout garantit l'existence d'un couple

(u,v)\in\mathbb{Z}^2

tel que

au+bv=d

, où

d=\operatorname{pgcd}(a,b)

D'après le corollaire de Bézout, $a$ et $b$ sont premiers entre eux si et seulement si :

au + bv = 0

pour un couple

(u,v)

au + bv = 1

pour un couple

(u,v)

a

b

sont impairs

au + bv = ab

pour un couple

(u,v)

Explication :

a

b

sont premiers entre eux si et seulement s'il existe

u,v\in\mathbb{Z}

tels que

au+bv=1

: c'est la caractérisation de Bézout.

Le théorème de Gauss énonce : si $a \mid bc$ et $\operatorname{pgcd}(a,b) = 1$ , alors :

a \mid c

a \mid b

b \mid c

c \mid a

Explication : C'est l'énoncé exact du théorème de Gauss : si

a

divise le produit

bc

et si

a

b

sont premiers entre eux, alors

a

divise nécessairement

c

On sait que $6 \mid 4 \times 3 = 12$ , mais $6 \nmid 4$ et $6 \nmid 3$ . Ceci n'est pas une contradiction du théorème de Gauss car :

le théorème de Gauss ne s'applique qu'aux nombres premiers

12

n'est pas un multiple de

6

\operatorname{pgcd}(6,4) = 2 \neq 1

, l'hypothèse du théorème n'est pas vérifiée

6

divise bien

4

Explication : L'hypothèse «

\operatorname{pgcd}(a,b)=1

» est indispensable au théorème de Gauss. Ici

\operatorname{pgcd}(6,4)=2\neq1

, donc on n'a aucun droit de conclure que

6

divise

4

3

L'équation diophantienne $ax+by=c$ (avec $d=\operatorname{pgcd}(a,b)$ ) admet au moins une solution entière si et seulement si :

c

est premier

d \mid c

a

b

sont premiers entre eux

c \mid d

Explication : D'après le théorème d'existence,

ax+by=c

a des solutions entières si et seulement si

d=\operatorname{pgcd}(a,b)

divise

c

L'équation $6x + 9y = 5$ a-t-elle des solutions entières ?

Oui, car

6

9

sont entiers Oui,

(x,y)=(1,-\frac{1}{9})

convient Impossible à déterminer sans essayer toutes les valeurs Non, car

\operatorname{pgcd}(6,9)=3

ne divise pas

5

Explication :

\operatorname{pgcd}(6,9)=3

, et

3\nmid5

: l'équation n'a aucune solution entière.

6x+9y

est toujours multiple de

3

, jamais égal à

5

Un entier $p \geqslant 2$ est premier lorsque :

ses seuls diviseurs positifs sont

1

p

il est impair il n'est divisible par aucun nombre pair il est premier avec tous les entiers pairs

Explication : C'est la définition : un entier

p\geqslant2

est premier si ses seuls diviseurs positifs sont

1

p

lui-même.

La démonstration d'Euclide de l'infinité des nombres premiers considère, pour une liste finie supposée $p_1,\ldots,p_n$ , le nombre $N = p_1\times\cdots\times p_n + 1$ . Elle montre que :

N

est toujours premier

N

est toujours composé tout diviseur premier de

N

ne peut être aucun des

p_i

, contredisant l'hypothèse de liste complète

N

est toujours un multiple de

p_1

Explication :

N

admet un diviseur premier

p

, qui devrait être l'un des

p_i

(liste supposée complète) ; mais alors

p_i

diviserait

N-p_1\times\cdots\times p_n=1

, impossible. Contradiction : la liste ne peut être finie.

Deux entiers $a$ et $b$ sont congrus modulo $n$ , noté $a \equiv b \pmod n$ , lorsque :

a

b

sont tous deux multiples de

n

n

divise

a - b

a = b + n

a

n

sont premiers entre eux

Explication : Par définition,

a\equiv b\pmod n \iff n\mid(a-b)

, ce qui équivaut aussi à dire que

a

b

ont le même reste dans la division euclidienne par

n

Le petit théorème de Fermat affirme que si $p$ est premier et $p \nmid a$ , alors :

a^{p} \equiv 0 \pmod p

a^{p-1} \equiv p \pmod p

a^{p-1} \equiv 1 \pmod p

a \equiv p-1 \pmod p

Explication : C'est l'énoncé exact :

p

premier,

p\nmid a

\Rightarrow

a^{p-1}\equiv1\pmod p

. Par exemple,

11

premier et

11\nmid2

donnent

2^{10}\equiv1\pmod{11}

Le nombre $N = 6\,381$ a pour somme des chiffres $6+3+8+1=18$ . Que peut-on en conclure ?

N

est premier

N

est divisible par

11

uniquement

N

n'est divisible ni par

3

ni par

9

N

est divisible à la fois par

3

et par

9

Explication :

N\equiv

(somme des chiffres)

\pmod9

(et donc aussi

\pmod3

). Ici

18

est multiple de

9

(et de

3

), donc

N

est divisible à la fois par

3

et par

9

: en effet

6\,381 = 9\times709

S'inscrire à ce chapitre

Clique et envoie : ton message WhatsApp est déjà pré-rempli avec la classe, la matière et le chapitre.

S'inscrire sur WhatsApp

Demander un cours privé Rejoindre un groupe

En bref

Classe : Classe de Terminale (séries scientifiques)
Matière : Mathématiques
Durée estimée : 11 h
8 parties · 3 objectifs
Supports inclus : fiche, exercices corrigés, QCM

Les autres chapitres

Tout le programme

Arithmétique dans ℤ

Ce que tu sauras faire à la fin

1Divisibilité et division euclidienne

1.1 Multiples et diviseurs

1.2 Propriétés de la divisibilité

1.3 Division euclidienne

2PGCD, PPCM, algorithme d'Euclide

2.1 Le PGCD

2.2 L'algorithme d'Euclide

2.3 Nombres premiers entre eux

2.4 PPCM et relation avec le PGCD

3Théorème de Bézout

3.1 L'identité de Bézout

3.2 Caractérisation des nombres premiers entre eux

3.3 Recherche pratique : la remontée de l'algorithme d'Euclide

3.4 Une première application : l'équation ax+by=cax+by=cax+by=c

4Théorème de Gauss

4.1 Énoncé et démonstration

4.2 Corollaires

4.3 Résolution complète de l'équation ax+by=cax+by=cax+by=c

5Nombres premiers et décomposition

5.1 Nombres premiers et leur infinité

5.2 Le crible d'Ératosthène

5.3 Décomposition en facteurs premiers

6Congruences dans ℤ

6.1 Définition et compatibilité avec les opérations

6.2 Puissances et cycles de restes

6.3 Petit théorème de Fermat

7Applications : critères de divisibilité, codage

7.1 Critères de divisibilité par 3, 9 et 11

7.2 Clés de contrôle : ISBN et RIB

7.3 Calendrier perpétuel

7.4 Chiffrement affine et introduction au RSA

Fiche mémo

8Exercices corrigés

Teste-toi gratuitement

Nombres complexes : forme algébrique et trigonométrique

Logarithme népérien et exponentielle

📝 QCM de fin de leçon — 20 questions

3.4 Une première application : l'équation $ax+by=c$

4.3 Résolution complète de l'équation $ax+by=c$