Arithmétique

Leçon 1 : Divisibilité et division euclidienne

Voir la vidéo de la leçon 1

1.1 Diviseurs et multiples

Définition. Soit $a$ et $b$ deux entiers relatifs. On dit que $b$ divise $a$ s'il existe un entier relatif $k$ tel que $a = k\,b$. On note $b \mid a$ (on lit « $b$ divise $a$ »). On dit aussi que $b$ est un diviseur de $a$, ou que $a$ est un multiple de $b$.

Exemple 1.

• $6 \mid 42$, car $42 = 7 \times 6$ ;
• $-3 \mid 12$, car $12 = (-4) \times (-3)$ ;
• $5$ ne divise pas $12$ (on note $5 \nmid 12$) : $12$ est compris entre $2 \times 5 = 10$ et $3 \times 5 = 15$.

Remarques.

• Tout entier divise $0$, car $0 = 0 \times b$. Mais $0$ ne divise que $0$.
• $1$ et $-1$ divisent tout entier.
• $a$ et $-a$ ont les mêmes diviseurs. Si $a \neq 0$ et $b \mid a$, alors $|b| \leq |a|$ : un entier non nul a un nombre fini de diviseurs.
• Les multiples de $b$ forment l'ensemble $b\mathbb{Z} = \{\dots\,;-2b\,;-b\,;0\,;b\,;2b\,;\dots\}$.

Exemple 2. Les diviseurs positifs de $12$ sont $1$, $2$, $3$, $4$, $6$ et $12$. Dans $\mathbb{Z}$, $12$ a donc $12$ diviseurs : $\pm 1$, $\pm 2$, $\pm 3$, $\pm 4$, $\pm 6$, $\pm 12$.

1.2 Propriétés de la divisibilité

Soit $a$, $b$ et $c$ des entiers relatifs.

Démonstration de la deuxième propriété. Si $b = k\,a$ et $c = k'\,a$, alors $bu + cv = (ku + k'v)\,a$, et $ku + k'v$ est un entier.

Méthode : faire disparaître l'inconnue. Pour trouver les $n$ tels qu'une expression en $n$ divise une autre, on fabrique une combinaison des deux qui ne dépend plus de $n$.

Exemple 3. Déterminer les entiers naturels $n$ tels que $n + 2$ divise $3n + 11$.

$n + 2$ divise $n + 2$, donc il divise $3(n + 2) = 3n + 6$. S'il divise aussi $3n + 11$, il divise la différence : $(3n + 11) - (3n + 6) = 5$. Donc $n + 2$ est un diviseur positif de $5$ : $n + 2 = 1$ ou $n + 2 = 5$. Comme $n + 2 \geq 2$, il reste $n + 2 = 5$, soit $n = 3$.

Vérification : pour $n = 3$, $3n + 11 = 20$ et $n + 2 = 5$ divise bien $20$. La seule solution est $n = 3$.

1.3 Division euclidienne dans $\mathbb{N}$

Théorème. Soit $a \in \mathbb{N}$ et $b \in \mathbb{N}^*$. Il existe un unique couple $(q\,;r)$ d'entiers naturels tel que $a = b\,q + r \qquad \text{et} \qquad 0 \leq r < b.$ $q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$.

Exemple 4. $2\,026 = 7 \times 289 + 3$, et $0 \leq 3 < 7$ : le quotient de $2\,026$ par $7$ est $289$ et le reste est $3$.

Remarque. $b$ divise $a$ si, et seulement si, le reste de la division euclidienne de $a$ par $b$ est nul.

1.4 Division euclidienne dans $\mathbb{Z}$

Théorème. Soit $a \in \mathbb{Z}$ et $b \in \mathbb{Z}^*$. Il existe un unique couple $(q\,;r)$, avec $q \in \mathbb{Z}$ et $r \in \mathbb{N}$, tel que $a = b\,q + r \qquad \text{et} \qquad 0 \leq r < |b|.$

Le reste est toujours positif ou nul, même si $a$ est négatif.

Exemple 5. Division euclidienne de $-17$ par $5$. On divise d'abord $17$ : $17 = 5 \times 3 + 2$, donc $-17 = 5 \times (-3) - 2$. Mais $-2$ n'est pas un reste, car il est négatif. On retire donc une fois $5$ au quotient et on l'ajoute au reste : $-17 = 5 \times (-4) + 3, \qquad 0 \leq 3 < 5.$ Le quotient est $-4$ et le reste est $3$.

Exemple 6. Division euclidienne de $17$ par $-5$ : $17 = (-5) \times (-3) + 2$, avec $0 \leq 2 < |-5| = 5$.

Démonstration (cas $b > 0$, non exigée).

• Existence. On prend pour $q$ la partie entière de $\dfrac{a}{b}$ (Seconde) : $q \leq \dfrac{a}{b} < q + 1$. En multipliant par $b > 0$ : $bq \leq a < bq + b$, donc $r = a - bq$ vérifie $0 \leq r < b$.
• Unicité. Si $a = bq + r = bq' + r'$ avec $0 \leq r < b$ et $0 \leq r' < b$, alors $b\,|q - q'| = |r' - r| < b$. L'entier naturel $|q - q'|$ est donc strictement inférieur à $1$ : il est nul, d'où $q = q'$ puis $r = r'$.

Pour $b < 0$, on divise $a$ par $|b| = -b$ : $a = (-b)\,q + r$, c'est-à-dire $a = b\,(-q) + r$.

1.5 Raisonner sur les restes

Dans la division par $n$, il n'y a que $n$ restes possibles : $0$, $1$, …, $n - 1$. Tout entier s'écrit donc sous l'une des formes $nk$, $nk + 1$, …, $nk + (n - 1)$, avec $k \in \mathbb{Z}$. On peut alors raisonner cas par cas.

Exemple 7. Montrer que, pour tout entier $n$, $n(n + 1)(2n + 1)$ est divisible par $3$.

Reste de $n$ par $3$	$n = 3k$	$n = 3k + 1$	$n = 3k + 2$
Facteur divisible par $3$	$n = 3k$	$2n + 1 = 6k + 3 = 3(2k + 1)$	$n + 1 = 3k + 3 = 3(k + 1)$

Dans chacun des trois cas, l'un des facteurs est un multiple de $3$, donc le produit aussi.

Leçon 2 : Congruences

Voir la vidéo de la leçon 2

2.1 Définition

Définition. Soit $n$ un entier naturel, $n \geq 2$. Deux entiers relatifs $a$ et $b$ sont congrus modulo $n$ s'ils ont le même reste dans la division euclidienne par $n$. On note $a \equiv b \;[n]$ et on lit « $a$ est congru à $b$ modulo $n$ ». On rencontre aussi les notations $a \equiv b \pmod n$ et $a \equiv b \;(n)$.

Théorème. $a \equiv b \;[n]$ si, et seulement si, $n$ divise $a - b$.

Démonstration. Écrivons $a = nq + r$ et $b = nq' + r'$ avec $0 \leq r < n$ et $0 \leq r' < n$. Alors $a - b = n(q - q') + (r - r')$, avec $-n < r - r' < n$.

• Si $r = r'$, alors $a - b = n(q - q')$ est un multiple de $n$.
• Si $n \mid a - b$, alors $n$ divise aussi $r - r' = (a - b) - n(q - q')$. Or le seul multiple de $n$ strictement compris entre $-n$ et $n$ est $0$ : donc $r = r'$.

Exemple 8.

• $23 \equiv 2 \;[7]$, car $23 = 7 \times 3 + 2$ ; de même $100 \equiv 2 \;[7]$, car $100 = 7 \times 14 + 2$.
• $-5 \equiv 2 \;[7]$, car $-5 - 2 = -7$ est un multiple de $7$.
• $2\,026 \equiv 0 \;[2]$ : un entier est pair si, et seulement si, il est congru à $0$ modulo $2$.

Conséquences.

• Si $r$ est le reste de la division euclidienne de $a$ par $n$, alors $a \equiv r \;[n]$. Tout entier est congru modulo $n$ à un, et un seul, des entiers $0$, $1$, …, $n - 1$ : son reste.
• $a \equiv 0 \;[n]$ si, et seulement si, $n$ divise $a$.
• Pour tous entiers $a$, $b$, $c$ : $a \equiv a \;[n]$ ; si $a \equiv b \;[n]$, alors $b \equiv a \;[n]$ ; si $a \equiv b \;[n]$ et $b \equiv c \;[n]$, alors $a \equiv c \;[n]$.

2.2 Congruences et opérations

Théorème. Si $a \equiv b \;[n]$ et $a' \equiv b' \;[n]$, alors :

• $a + a' \equiv b + b' \;[n]$ et $a - a' \equiv b - b' \;[n]$ ;
• $a\,a' \equiv b\,b' \;[n]$ ; en particulier $k\,a \equiv k\,b \;[n]$ pour tout entier $k$ ;
• $a^p \equiv b^p \;[n]$ pour tout entier naturel $p$.

Démonstration.

• $(a + a') - (b + b') = (a - b) + (a' - b')$ est la somme de deux multiples de $n$.
• $a\,a' - b\,b' = a\,(a' - b') + b'\,(a - b)$ est une combinaison de deux multiples de $n$.
• Pour les puissances, par récurrence sur $p$ : $a^0 = 1 \equiv 1 = b^0$, et si $a^p \equiv b^p \;[n]$, on multiplie membre à membre par $a \equiv b \;[n]$ pour obtenir $a^{p+1} \equiv b^{p+1} \;[n]$.

Méthode. Pour calculer un reste, on remplace chaque nombre par un nombre plus petit qui lui est congru, puis on calcule.

Exemple 9. Reste de $2\,026 \times 1\,999 + 100$ dans la division par $7$ : $2\,026 \equiv 3$, $1\,999 \equiv 4$ et $100 \equiv 2 \;[7]$, donc $2\,026 \times 1\,999 + 100 \equiv 3 \times 4 + 2 = 14 \equiv 0 \;[7].$ Ce nombre est un multiple de $7$.

Attention : on ne divise pas une congruence. $6 \equiv 16 \;[10]$, c'est-à-dire $2 \times 3 \equiv 2 \times 8 \;[10]$, mais $3 \not\equiv 8 \;[10]$.

2.3 Restes des puissances

Les restes des puissances successives d'un entier finissent par se répéter. Dès qu'une puissance est congrue à $1$, le cycle recommence.

Exemple 10. Les puissances de $2$ modulo $7$.

$k$	$1$	$2$	$3$	$4$	$5$	$6$
$2^k$ modulo $7$	$2$	$4$	$1$	$2$	$4$	$1$

Comme $2^3 = 8 \equiv 1 \;[7]$, on a $2^{3m} = (2^3)^m \equiv 1^m = 1 \;[7]$ pour tout entier naturel $m$. Pour $2^{100}$, on divise l'exposant par $3$ : $100 = 3 \times 33 + 1$, donc $2^{100} = (2^3)^{33} \times 2 \equiv 1 \times 2 = 2 \;[7].$ Le reste de $2^{100}$ dans la division par $7$ est $2$.

Exemple 11 (dernier chiffre). Le dernier chiffre d'un entier naturel est son reste dans la division par $10$. Les puissances de $7$ modulo $10$ valent $7$, $9$, $3$, $1$, puis le cycle recommence. Comme $2\,026 = 4 \times 506 + 2$, on a $7^{2\,026} = (7^4)^{506} \times 7^2 \equiv 49 \equiv 9 \;[10]$ : le dernier chiffre de $7^{2\,026}$ est $9$.

Exemple 12. Montrer que, pour tout entier naturel $n$, $3^{2n} - 2^n$ est divisible par $7$.

$3^{2n} = (3^2)^n = 9^n$ et $9 \equiv 2 \;[7]$, donc $9^n \equiv 2^n \;[7]$, c'est-à-dire $3^{2n} - 2^n \equiv 0 \;[7]$.

2.4 Applications : calendrier et critères de divisibilité

Le calendrier. Les jours de la semaine reviennent tous les $7$ jours : deux dates séparées par $N$ jours tombent le même jour de la semaine si, et seulement si, $N \equiv 0 \;[7]$. Pour savoir quel jour on sera dans $N$ jours, on cherche le reste de $N$ modulo $7$.

Exemple 13. Le 4 novembre 2026 est un mercredi. Quel jour de la semaine serons-nous $1\,000$ jours plus tard ?

$1\,000 = 7 \times 142 + 6$, donc $1\,000 \equiv 6 \;[7]$ : on avance de $6$ jours à partir du mercredi, et on tombe sur un mardi.

Critères de divisibilité. Un entier naturel s'écrit en base dix $N = a_k 10^k + \dots + a_1 10 + a_0$, où $a_0$, $a_1$, …, $a_k$ sont ses chiffres (voir la leçon 8).

• Comme $10 \equiv 1 \;[9]$, on a $10^i \equiv 1 \;[9]$, donc $N \equiv a_k + \dots + a_1 + a_0 \;[9]$ : un entier est congru modulo $9$ à la somme de ses chiffres. Il est divisible par $9$ si, et seulement si, cette somme l'est. Le même raisonnement vaut modulo $3$, car $10 \equiv 1 \;[3]$.
• Comme $10 \equiv -1 \;[11]$, on a $10^i \equiv (-1)^i \;[11]$, donc $N \equiv a_0 - a_1 + a_2 - \dots \;[11]$ : on alterne les signes en partant du chiffre des unités.

Exemple 14. Pour $N = 7\,654\,321$ : la somme des chiffres vaut $28$ et $28 \equiv 1 \;[9]$, donc $N \equiv 1 \;[9]$. La somme alternée vaut $1 - 2 + 3 - 4 + 5 - 6 + 7 = 4$, donc $N \equiv 4 \;[11]$.

Leçon 3 : PGCD et algorithme d'Euclide

Voir la vidéo de la leçon 3

3.1 Définition

Soit $a$ et $b$ deux entiers relatifs non tous les deux nuls. Leurs diviseurs communs sont en nombre fini, et $1$ en fait partie.

Définition. Le plus grand commun diviseur de $a$ et $b$ est le plus grand de leurs diviseurs communs. On le note $\mathrm{PGCD}(a\,;b)$, ou $a \wedge b$.

Exemple 15. Les diviseurs positifs de $24$ sont $1$, $2$, $3$, $4$, $6$, $8$, $12$, $24$ ; ceux de $36$ sont $1$, $2$, $3$, $4$, $6$, $9$, $12$, $18$, $36$. Les diviseurs communs positifs sont $1$, $2$, $3$, $4$, $6$, $12$, donc $\mathrm{PGCD}(24\,;36) = 12$.

Propriétés immédiates.

• $\mathrm{PGCD}(a\,;b) \geq 1$, $\mathrm{PGCD}(a\,;b) = \mathrm{PGCD}(b\,;a)$ et $\mathrm{PGCD}(a\,;b) = \mathrm{PGCD}(|a|\,;|b|)$ : on peut toujours se ramener à des entiers naturels.
• Si $a \neq 0$, $\mathrm{PGCD}(a\,;0) = |a|$.
• Si $b \neq 0$ et $b \mid a$, alors $\mathrm{PGCD}(a\,;b) = |b|$.

3.2 Le lemme d'Euclide

Propriété. Si $a = b\,q + r$ (avec $a$, $b$, $q$, $r$ entiers), alors $a$ et $b$ ont les mêmes diviseurs communs que $b$ et $r$. En particulier $\mathrm{PGCD}(a\,;b) = \mathrm{PGCD}(b\,;r).$

Démonstration. Si $d$ divise $a$ et $b$, il divise $r = a - bq$ (combinaison). Si $d$ divise $b$ et $r$, il divise $a = bq + r$. Les deux couples ont donc exactement les mêmes diviseurs communs, donc le même plus grand.

3.3 L'algorithme d'Euclide

Soit $a$ et $b$ deux entiers naturels avec $b \neq 0$. On effectue la division euclidienne de $a$ par $b$, puis celle de $b$ par le reste, puis celle du premier reste par le deuxième, et ainsi de suite. Les restes sont des entiers naturels strictement décroissants : on finit par obtenir un reste nul.

Théorème. Le PGCD de $a$ et $b$ est le dernier reste non nul de l'algorithme d'Euclide.

En effet, d'après le lemme d'Euclide, le PGCD ne change pas d'une ligne à la suivante, et à la dernière ligne, $\mathrm{PGCD}(r\,;0) = r$.

Exemple 16. Calcul de $\mathrm{PGCD}(924\,;360)$.

Division	Reste
$924 = 360 \times 2 + 204$	$204$
$360 = 204 \times 1 + 156$	$156$
$204 = 156 \times 1 + 48$	$48$
$156 = 48 \times 3 + 12$	$\mathbf{12}$
$48 = 12 \times 4 + 0$	$0$

Le dernier reste non nul est $12$ : $\mathrm{PGCD}(924\,;360) = 12$.

Conséquences.

• Les diviseurs communs de $a$ et $b$ sont exactement les diviseurs de leur PGCD (ils sont conservés d'une ligne à l'autre de l'algorithme, et à la fin ce sont les diviseurs de $r$).
• Pour tout entier naturel non nul $k$ : $\mathrm{PGCD}(ka\,;kb) = k\,\mathrm{PGCD}(a\,;b)$ (on multiplie par $k$ toutes les lignes de l'algorithme).

Exemple 17 (partage, situation simplifiée). Une association veut répartir $924$ cahiers et $360$ stylos en lots identiques, en utilisant tout le matériel, avec le plus grand nombre de lots possible. Le nombre de lots divise $924$ et $360$ : le plus grand possible est $\mathrm{PGCD}(924\,;360) = 12$. Chaque lot contient $924 : 12 = 77$ cahiers et $360 : 12 = 30$ stylos.

3.4 Entiers premiers entre eux

Définition. Deux entiers sont premiers entre eux si leur PGCD est égal à $1$ : leurs seuls diviseurs communs sont $1$ et $-1$.

Exemple 18. $35 = 5 \times 7$ et $18 = 2 \times 3^2$ sont premiers entre eux. $77$ et $30$ aussi.

Propriété. Si $d = \mathrm{PGCD}(a\,;b)$, avec $a$ et $b$ non nuls, alors $a = d\,a'$ et $b = d\,b'$, où $a'$ et $b'$ sont premiers entre eux.

Démonstration. $d = \mathrm{PGCD}(d\,a'\,;d\,b') = d\,\mathrm{PGCD}(a'\,;b')$, donc $\mathrm{PGCD}(a'\,;b') = 1$.

Application aux fractions. Une fraction $\dfrac{a}{b}$ est irréductible si $a$ et $b$ sont premiers entre eux. Pour la rendre irréductible, on divise $a$ et $b$ par leur PGCD : $\dfrac{924}{360} = \dfrac{12 \times 77}{12 \times 30} = \dfrac{77}{30}$.

3.5 PGCD de plusieurs entiers

Le PGCD de plusieurs entiers est le plus grand de leurs diviseurs communs. On le calcule de proche en proche : $\mathrm{PGCD}(a\,;b\,;c) = \mathrm{PGCD}\big(\mathrm{PGCD}(a\,;b)\,;c\big).$

Exemple 19. $\mathrm{PGCD}(924\,;360\,;150) = \mathrm{PGCD}(12\,;150) = 6$, car $150 = 12 \times 12 + 6$ et $12 = 6 \times 2$.

Leçon 4 : Identité de Bézout et théorème de Gauss

Voir la vidéo de la leçon 4

4.1 Identité de Bézout

Théorème (identité de Bézout). Soit $a$ et $b$ deux entiers non tous les deux nuls, et $d = \mathrm{PGCD}(a\,;b)$. Il existe deux entiers relatifs $u$ et $v$ tels que $a\,u + b\,v = d.$

Démonstration (pour $a$ et $b$ naturels, $b \neq 0$). Dans l'algorithme d'Euclide, chaque reste s'écrit sous la forme $a\,u + b\,v$ avec $u$, $v$ entiers. C'est vrai pour $a = a \times 1 + b \times 0$ et pour $b = a \times 0 + b \times 1$ ; et si deux restes consécutifs $r_1$ et $r_2$ sont de cette forme, le suivant, $r_3 = r_1 - r_2\,q$, l'est aussi. C'est donc vrai pour le dernier reste non nul, qui est $d$.

Méthode : la remontée de l'algorithme d'Euclide. On écrit chaque reste à partir de la ligne qui le donne, puis on remplace, en remontant, jusqu'à n'avoir plus que $a$ et $b$.

Exemple 20. Trouver $u$ et $v$ tels que $84\,u + 30\,v = \mathrm{PGCD}(84\,;30)$.

L'algorithme d'Euclide donne : $84 = 30 \times 2 + 24$ ; $30 = 24 \times 1 + 6$ ; $24 = 6 \times 4 + 0$. Donc $\mathrm{PGCD}(84\,;30) = 6$. On remonte : $6 = 30 - 24 \times 1 = 30 - (84 - 30 \times 2) = 84 \times (-1) + 30 \times 3.$ On a donc $u = -1$ et $v = 3$. Vérification : $-84 + 90 = 6$.

Remarque. Le couple $(u\,;v)$ n'est pas unique : par exemple $84 \times 4 + 30 \times (-11) = 336 - 330 = 6$.

4.2 Théorème de Bézout

Théorème de Bézout. Deux entiers $a$ et $b$ sont premiers entre eux si, et seulement si, il existe deux entiers relatifs $u$ et $v$ tels que $a\,u + b\,v = 1.$

Démonstration.

• Si $\mathrm{PGCD}(a\,;b) = 1$, c'est l'identité de Bézout.
• Réciproquement, si $a\,u + b\,v = 1$, tout diviseur commun de $a$ et $b$ divise $a\,u + b\,v = 1$ : c'est $1$ ou $-1$. Donc $\mathrm{PGCD}(a\,;b) = 1$.

Méthode. Pour montrer que deux expressions sont premières entre elles, on cherche une combinaison qui vaut $1$ (ou $-1$).

Exemple 21.

• Pour tout entier $n$ : $(n + 1) \times 1 + n \times (-1) = 1$, donc deux entiers consécutifs sont premiers entre eux.
• Pour tout entier $n$ : $3\,(2n + 1) - 2\,(3n + 2) = -1$, donc $(2n + 1) \times (-3) + (3n + 2) \times 2 = 1$ : $2n + 1$ et $3n + 2$ sont premiers entre eux.

4.3 Théorème de Gauss

Théorème de Gauss. Soit $a$, $b$ et $c$ trois entiers. Si $a$ divise $b\,c$ et si $a$ est premier avec $b$, alors $a$ divise $c$.

Démonstration. Comme $\mathrm{PGCD}(a\,;b) = 1$, il existe $u$ et $v$ tels que $a\,u + b\,v = 1$. En multipliant par $c$ : $c = a\,c\,u + b\,c\,v$. Or $a$ divise $a\,c\,u$, et $a$ divise $b\,c$ donc $b\,c\,v$. Donc $a$ divise leur somme, $c$.

Exemple 22. Si $7$ divise $4n$, alors $7$ divise $n$, car $7$ et $4$ sont premiers entre eux.

Attention : l'hypothèse « premiers entre eux » est indispensable. $6$ divise $4 \times 3 = 12$, mais $6$ ne divise ni $4$ ni $3$.

4.4 Conséquence

Propriété. Si $a$ et $b$ divisent $c$, et si $a$ et $b$ sont premiers entre eux, alors $a\,b$ divise $c$.

Démonstration. $c = a\,k$ avec $k$ entier. $b$ divise $a\,k$ et $b$ est premier avec $a$ : d'après le théorème de Gauss, $b$ divise $k$, donc $k = b\,k'$ et $c = a\,b\,k'$.

Exemple 23.

• Un entier est divisible par $6$ si, et seulement si, il est divisible par $2$ et par $3$ ($2$ et $3$ sont premiers entre eux).
• Un entier est divisible par $12$ si, et seulement si, il est divisible par $3$ et par $4$. Mais être divisible par $2$ et par $6$ ne suffit pas : $6$ l'est, et n'est pas divisible par $12$. Ici $2$ et $6$ ne sont pas premiers entre eux.

Leçon 5 : Équations du type $ax + by = c$

Voir la vidéo de la leçon 5

Dans cette leçon, $a$ et $b$ sont des entiers naturels non nuls, $c$ est un entier naturel, et l'on cherche les couples $(x\,;y)$ d'entiers relatifs tels que $a\,x + b\,y = c$. C'est la compétence exigible du programme : « résoudre dans $\mathbb{Z}$ des équations du type $ax + by = c$ où $a$, $b$ et $c$ sont des entiers naturels ».

5.1 Existence de solutions

Théorème. Soit $d = \mathrm{PGCD}(a\,;b)$. L'équation $a\,x + b\,y = c$ a des solutions dans $\mathbb{Z}^2$ si, et seulement si, $d$ divise $c$.

Démonstration.

• Si $(x\,;y)$ est une solution, $d$ divise $a$ et $b$, donc il divise $a\,x + b\,y = c$.
• Réciproquement, si $c = d\,k$, l'identité de Bézout donne $u$ et $v$ tels que $a\,u + b\,v = d$ ; alors $a\,(u\,k) + b\,(v\,k) = d\,k = c$.

Exemple 24. $84\,x + 30\,y = 10$ n'a aucune solution entière : $\mathrm{PGCD}(84\,;30) = 6$ ne divise pas $10$. En effet, le membre de gauche est toujours un multiple de $6$.

5.2 Méthode de résolution

1. Simplifier. On calcule $d = \mathrm{PGCD}(a\,;b)$. Si $d$ ne divise pas $c$, il n'y a pas de solution. Sinon, on divise par $d$ : $a'\,x + b'\,y = c'$, avec $a'$ et $b'$ premiers entre eux.
2. Trouver une solution particulière $(x_0\,;y_0)$, à vue ou par la remontée de l'algorithme d'Euclide (on trouve $a'\,u + b'\,v = 1$, puis on multiplie par $c'$).
3. Soustraire et appliquer Gauss. Si $(x\,;y)$ est une solution, on soustrait $a'\,x_0 + b'\,y_0 = c'$ : $a'\,(x - x_0) = b'\,(y_0 - y).$ $a'$ divise $b'\,(y_0 - y)$ et $a'$ est premier avec $b'$, donc $a'$ divise $y_0 - y$ : $y_0 - y = a'\,k$ avec $k \in \mathbb{Z}$. En remplaçant, $a'\,(x - x_0) = b'\,a'\,k$, donc $x - x_0 = b'\,k$.
4. Vérifier et conclure. Réciproquement, pour tout $k \in \mathbb{Z}$, le couple $(x_0 + b'\,k\,;\,y_0 - a'\,k)$ est solution, car $a'\,b'\,k - b'\,a'\,k = 0$. L'ensemble des solutions est $\big\{(x_0 + b'\,k\,;\;y_0 - a'\,k),\ k \in \mathbb{Z}\big\}.$

Exemple 25. Résoudre dans $\mathbb{Z}^2$ l'équation $84\,x + 30\,y = 18$.

1. $\mathrm{PGCD}(84\,;30) = 6$ divise $18$. On divise par $6$ : $14\,x + 5\,y = 3$.
2. Solution particulière : $14 \times 2 + 5 \times (-5) = 28 - 25 = 3$, donc $(x_0\,;y_0) = (2\,;-5)$.
3. Si $14\,x + 5\,y = 3$, alors $14\,(x - 2) = 5\,(-5 - y)$. $5$ divise $14\,(x - 2)$ et $5$ est premier avec $14$, donc $5$ divise $x - 2$ : $x = 2 + 5k$. Alors $14 \times 5k = 5\,(-5 - y)$, d'où $y = -5 - 14k$.
4. Réciproquement, $14\,(2 + 5k) + 5\,(-5 - 14k) = 28 - 25 = 3$. Les solutions sont les couples $(2 + 5k\,;\,-5 - 14k)$, $k \in \mathbb{Z}$.

Remarque. Une autre solution particulière donne une autre écriture du même ensemble. Avec la remontée, $14 \times (-1) + 5 \times 3 = 1$, donc $(x_0\,;y_0) = (-3\,;9)$ : on obtient $(-3 + 5k\,;9 - 14k)$, qui décrit les mêmes couples (remplacer $k$ par $k + 1$).

5.3 Un problème concret

Exemple 26 (situation simplifiée). Dans une librairie, un cahier coûte $350$ F et un stylo $150$ F. Une élève a dépensé exactement $2\,600$ F. Combien a-t-elle pu acheter de cahiers et de stylos ?

On note $x$ le nombre de cahiers et $y$ le nombre de stylos : $350\,x + 150\,y = 2\,600$. En divisant par $50$ : $7\,x + 3\,y = 52$, avec $\mathrm{PGCD}(7\,;3) = 1$.

• Solution particulière : $7 \times 1 + 3 \times 15 = 52$.
• Comme ci-dessus, les solutions dans $\mathbb{Z}^2$ sont $x = 1 + 3k$ et $y = 15 - 7k$, $k \in \mathbb{Z}$.
• Ici $x$ et $y$ sont des entiers naturels : $1 + 3k \geq 0$ donne $k \geq 0$, et $15 - 7k \geq 0$ donne $k \leq 2$.

$k$	$0$	$1$	$2$
cahiers $x$	$1$	$4$	$7$
stylos $y$	$15$	$8$	$1$

Il y a trois possibilités.