Point de départ · 1

On effectue la division de $-25$ par $4$ . En écrivant $-25 = 4 \times (-6) - 1$ , le nombre $-1$ peut-il être le reste euclidien ?

Remarque

Une division euclidienne impose toujours que le reste soit un entier naturel : il doit obligatoirement être positif ou nul ( $r \ge 0$ ).

Définition · 2

Théorème de la division euclidienne dans $\mathbb{Z}$

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

a \in \mathbb{Z} \quad \text{et} \quad b \in \mathbb{Z}^*

Il existe un unique couple d'entiers relatifs $(q, r)$ vérifiant ces deux conditions. L'entier $q$ est le quotient et l'entier $r$ est le reste.

Vocabulaire

dividende — $a$
diviseur — $b$
quotient — $q$
reste — $r$

Exemple travaillé · 3

Déterminer le quotient $q$ et le reste $r$ de la division euclidienne de $-317$ par $21$ .

1

On pose la division euclidienne de $317$ par $21$ :

2

317 = 21 \times 15 + 2

3

On multiplie chaque membre par $-1$ pour faire apparaître le dividende $-317$ :

4

-317 = 21 \times (-15) - 2

5

Le nombre $-2$ est négatif : il ne peut pas être un reste euclidien. On retranche et on ajoute $21$ pour compenser :

6

-317 = 21 \times (-15) - 21 + (21 - 2) = 21 \times (-16) + 19

7

On vérifie l'encadrement réglementaire du reste :

8

0 \le 19 < 21

9

Le quotient est $q = -16$ et le reste est $r = 19$ .

Exemple travaillé · 4

Déterminer le quotient $q$ et le reste $r$ de la division euclidienne de $-671$ par $-6$ .

1

Le diviseur est $b = -6$ . Le reste doit impérativement vérifier :

2

0 \le r < |-6| \iff 0 \le r < 6

3

On effectue d'abord la division euclidienne de $671$ par $6$ :

4

671 = 6 \times 111 + 5

5

On adapte les signes pour faire apparaître le diviseur $-6$ :

6

-671 = (-6) \times 111 - 5

7

Le reste provisoire $-5$ est négatif. On retranche et on ajoute $|-6| = 6$ :

8

-671 = (-6) \times 111 - 6 + (6 - 5) = (-6) \times 112 + 1

9

Comme $0 \le 1 < 6$ , l'égalité traduit la division euclidienne : le quotient est $q = 112$ et le reste est $r = 1$ .

Piège classique · 5

Pour diviser $-45$ par $7$ , un élève écrit : $-45 = 7 \times (-6) - 3$ . Il conclut que le quotient est $-6$ et le reste est $-3$ . Cette réponse est-elle valide ?

Attention

Accepter $r = -3$ comme reste sous prétexte que l'égalité arithmétique $7 \times (-6) - 3 = -45$ est exacte.

À la place : Un reste euclidien doit obligatoirement vérifier $0 \le r < 7$ . Il faut écrire $-45 = 7 \times (-7) + 4$ : le quotient est $-7$ et le reste est $4$ .

Vérification · 6

Détermine le quotient $q$ et le reste $r$ de la division euclidienne de $-50$ par $8$ .

Remarque

On a $-50 = 8 \times (-7) + 6$ . Le quotient est $-7$ et le reste est $6$ , car $0 \le 6 < 8$ . L'écriture $8 \times (-6) - 2$ aurait donné un reste négatif, ce qui contredit le théorème.

Point de départ · 7

Quel est le PGCD de $-24$ et $56$ ?

Remarque

Le PGCD de deux entiers non nuls est le plus grand entier qui les divise tous les deux : c'est obligatoirement un entier naturel strictement positif. On a donc $(-24) \wedge 56 = |-24| \wedge 56 = 24 \wedge 56 = 8$ .

Définition · 8

PGCD, PPCM et forme irréductible dans $\mathbb{Z}$

Soient $a$ et $b$ deux entiers relatifs non nuls. Le PGCD et le PPCM sont des entiers naturels strictement positifs calculés à partir des valeurs absolues :

$a \wedge b = |a| \wedge |b| \quad \text{et} \quad a \vee b = |a| \vee |b|$

Le produit du PGCD et du PPCM est égal à la valeur absolue du produit des deux entiers :

$(a \wedge b) \times (a \vee b) = |ab|$

Si $d = a \wedge b$ , il existe un unique couple d'entiers relatifs $(a', b')$ tel que :

$a = da' \quad \text{et} \quad b = db' \quad \text{avec} \quad a' \wedge b' = 1$

Exemple travaillé · 9

Déterminer $a \wedge b$ puis $a \vee b$ pour $a = 123$ et $b = -82$ .

1

On utilise la valeur absolue pour se ramener à des entiers naturels :

2

123 \wedge (-82) = 123 \wedge |-82| = 123 \wedge 82

3

On effectue l'algorithme d'Euclide entre $123$ et $82$ :

4

123 = 82 \times 1 + 41

5

82 = 41 \times 2 + 0

6

Le dernier reste non nul est $41$ , donc $a \wedge b = 41$ .

7

On calcule le PPCM par la relation fondamentale :

8

a \vee b = \frac{|ab|}{a \wedge b} = \frac{|123 \times (-82)|}{41} = \frac{10086}{41} = 246

Définition · 10

Combinaisons linéaires et diviseurs communs

Tout diviseur commun à deux entiers divise toute combinaison linéaire de ces deux entiers :

$d \mid a \quad \text{et} \quad d \mid b \implies d \mid (ua + vb) \quad \text{pour tous } u, v \in \mathbb{Z}$

Comme le PGCD $a \wedge b$ est un diviseur commun à $a$ et $b$ , il divise toute combinaison linéaire de $a$ et $b$ :

$(a \wedge b) \mid (ua + vb)$

Exemple travaillé · 11

Soit $n \in \mathbb{N}$ . On pose $a = 2n+8$ et $b = 3n+15$ . Montrer que $a \wedge b$ divise $6$ .

1

Soit $d = a \wedge b$ . Le nombre $d$ divise toute combinaison linéaire de $a$ et $b$ .

2

On choisit les coefficients $u = 3$ et $v = -2$ pour éliminer le terme en $n$ :

3

3a - 2b = 3(2n+8) - 2(3n+15)

4

3a - 2b = (6n + 24) - (6n + 30) = -6

5

Puisque $d$ divise $-6$ , $d$ divise nécessairement son opposé $|-6| = 6$ .

Piège classique · 12

On a établi que pour tout $n \in \mathbb{N}$ , le PGCD de $a = 2n+8$ et $b = 3n+15$ divise $6$ . Peut-on affirmer que $(2n+8) \wedge (3n+15) = 6$ pour tout entier $n$ ?

Attention

Affirmer que le PGCD est égal à $6$ dès que la combinaison linéaire sans $n$ est égale à $-6$ .

À la place : L'égalité $3a - 2b = -6$ prouve seulement que $a \wedge b$ divise $6$ , donc $a \wedge b \in \{1 ; 2 ; 3 ; 6\}$ . Pour $n = 0$ , on a $a = 8$ et $b = 15$ : or $8 \wedge 15 = 1 \neq 6$ .

Vérification · 13

Soit $n \in \mathbb{N}$ . On pose $u = n+1$ et $v = n+9$ . Quelle est la valeur maximale que peut prendre le PGCD $u \wedge v$ ?

Remarque

On effectue la différence : $v - u = (n+9) - (n+1) = 8$ . Le PGCD $u \wedge v$ divise donc $8$ . Les diviseurs positifs de $8$ sont $1, 2, 4$ et $8$ . La valeur maximale possible est donc $8$ (atteinte par exemple pour $n = 7$ , car $8 \wedge 16 = 8$ ).

Point de départ · 14

Existe-t-il un couple d'entiers relatifs $(x, y)$ tel que $6x + 9y = 5$ ?

Remarque

On peut factoriser le membre de gauche par $3$ : $6x + 9y = 3(2x + 3y)$ . Quel que soit le choix des entiers $x$ et $y$ , l'expression $6x + 9y$ est un multiple de $3$ . Comme $3$ ne divise pas $5$ , cette égalité est impossible dans $\mathbb{Z}$ .

Définition · 15

Théorème de Bézout et condition de résolubilité

Deux entiers relatifs non nuls $a$ et $b$ sont premiers entre eux si et seulement s'il existe deux entiers relatifs $u$ et $v$ tels que :

$au + bv = 1$

Pour des entiers relatifs non nuls $a$ et $b$ et un entier $c$ , l'équation diophantienne linéaire $ax + by = c$ admet des solutions dans $\mathbb{Z} \times \mathbb{Z}$ si et seulement si le PGCD de $a$ et $b$ divise $c$ :

$(a \wedge b) \mid c$

Piège classique · 16

On considère l'équation $168x + 20y = 6$ d'inconnues $x, y \in \mathbb{Z}$ . Quelle étape doit-on impérativement réaliser avant de chercher une solution particulière ?

Attention

Lancer mécaniquement l'algorithme d'Euclide étendu sans vérifier si le second membre est divisible par le PGCD des coefficients.

À la place : On calcule d'abord le PGCD : $168 = 20 \times 8 + 8$ , $20 = 8 \times 2 + 4$ , $8 = 4 \times 2 + 0$ , donc $168 \wedge 20 = 4$ . Or $4$ ne divise pas $6$ . L'équation n'admet aucune solution dans $\mathbb{Z} \times \mathbb{Z}$ ( $S = \emptyset$ ), tout calcul de remontée est inutile.

Exemple travaillé · 17

Déterminer une solution particulière dans $\mathbb{Z} \times \mathbb{Z}$ de l'équation $42x + 5y = 1$ .

1

On effectue les divisions euclidiennes successives de l'algorithme d'Euclide :

2

42 = 5 \times 8 + 2

3

5 = 2 \times 2 + 1

4

Le dernier reste non nul est $1$ , donc $42 \wedge 5 = 1$ . L'équation admet des solutions entières.

5

On isole le reste $1$ dans la dernière division :

6

1 = 5 - 2 \times 2

7

On remplace le reste précédent $2 = 42 - 5 \times 8$ :

8

1 = 5 - 2 \times (42 - 5 \times 8)

9

1 = 5 - 2 \times 42 + 16 \times 5 = 42 \times (-2) + 5 \times 17

10

Le couple $(x_0, y_0) = (-2, 17)$ est une solution particulière de l'équation.

Exemple travaillé · 18

Sachant que $42(-2) + 5(17) = 1$ , déterminer une solution particulière de $42x + 5y = 3$ , puis une solution particulière de $168u + 20v = 4$ .

1

Pour $42x + 5y = 3$ , on multiplie l'égalité de Bézout par le second membre $3$ :

2

42 \times [(-2) \times 3] + 5 \times [17 \times 3] = 1 \times 3

3

42 \times (-6) + 5 \times 51 = 3

4

Le couple $(x_0, y_0) = (-6, 51)$ est une solution particulière de $42x + 5y = 3$ .

5

Pour l'équation $168u + 20v = 4$ , on simplifie chaque terme par $4$ :

6

168u + 20v = 4 \iff 4(42u + 5v) = 4 \times 1 \iff 42u + 5v = 1

7

On reconnaît directement l'équation résolue à l'étape précédente : une solution particulière est $(u_0, v_0) = (-2, 17)$ .

Vérification · 19

On donne $35 \wedge 14 = 7$ . Parmi les trois équations suivantes, laquelle admet des solutions entières dans $\mathbb{Z} \times \mathbb{Z}$ ?

Remarque

Une équation $35x + 14y = c$ admet des solutions entières si et seulement si $35 \wedge 14$ divise $c$ , c'est-à-dire si $7$ divise $c$ . Comme $7$ divise $21$ ( $21 = 7 \times 3$ ), l'équation $35x + 14y = 21$ admet des solutions. En revanche, $7$ ne divise ni $20$ ni $22$ .

Point de départ · 20

Le nombre $6$ divise le produit $4 \times 9 = 36$ . Peut-on en déduire que $6$ divise $4$ ou que $6$ divise $9$ ?

Remarque

Non, car $6$ ne divise ni $4$ ni $9$ . Un entier peut parfaitement diviser un produit sans diviser aucun des facteurs. Pour garantir la transmission de la divisibilité à l'un des facteurs, une condition de coprimalité est indispensable : c'est l'objet du lemme de Gauss.

Définition · 21

Lemme de Gauss et divisibilité conjointe

Soient $a$ , $b$ et $c$ trois entiers relatifs non nuls. Si $a$ divise le produit $bc$ et si $a$ est premier avec $b$ , alors $a$ divise nécessairement $c$ :

$a \mid bc \quad \text{et} \quad a \wedge b = 1 \implies a \mid c$

Conséquence pour la divisibilité simultanée : si deux entiers divisent un même nombre et sont premiers entre eux, leur produit le divise également :

$a \mid c, \quad b \mid c \quad \text{et} \quad a \wedge b = 1 \implies ab \mid c$

Piège classique · 22

Un entier relatif $n$ est divisible par $2$ et par $28$ . Peut-on en déduire que $n$ est nécessairement divisible par $2 \times 28 = 56$ ?

Attention

Multiplier deux diviseurs sans vérifier au préalable qu'ils sont premiers entre eux.

À la place : La divisibilité par le produit $ab$ exige impérativement la condition $a \wedge b = 1$ . Ici, $2 \wedge 28 = 2 \neq 1$ . Le nombre $28$ est bien divisible par $2$ et par $28$ , mais n'est pas divisible par $56$ .

Exemple travaillé · 23

On considère l'équation $(E) : 5x - 3y = 2$ dans $\mathbb{Z} \times \mathbb{Z}$ . Sachant que $(1, 1)$ est une solution particulière de $(E)$ , déterminer l'ensemble des solutions de $(E)$ .

1

Le couple $(x, y)$ et la solution particulière $(1, 1)$ vérifient tous les deux l'équation :

2

5x - 3y = 2 \quad \text{et} \quad 5(1) - 3(1) = 2

3

Par soustraction membre à membre, on obtient l'égalité homogène :

4

5(x - 1) - 3(y - 1) = 0 \iff 5(x - 1) = 3(y - 1)

5

$5$ divise $3(y - 1)$ . Comme $5 \wedge 3 = 1$ , d'après le lemme de Gauss, $5$ divise $y - 1$ . Il existe donc un entier $k \in \mathbb{Z}$ tel que :

6

y - 1 = 5k \implies y = 5k + 1

7

En remplaçant $y - 1$ par $5k$ dans l'égalité $5(x - 1) = 3(y - 1)$ :

8

5(x - 1) = 3(5k) \implies x - 1 = 3k \implies x = 3k + 1

9

Réciproque : pour tout $k \in \mathbb{Z}$ , $5(3k+1) - 3(5k+1) = 15k + 5 - 15k - 3 = 2$ . L'ensemble des solutions est :

10

S_{\mathbb{Z} \times \mathbb{Z}} = \{(3k + 1 \; ; \; 5k + 1), \; k \in \mathbb{Z}\}

Exemple travaillé · 24

L'équation $7x - 5y = 1$ a pour ensemble de solutions dans $\mathbb{Z} \times \mathbb{Z}$ les couples $(5k+3 \; ; \; 7k+4)$ avec $k \in \mathbb{Z}$ . Déterminer les couples $(x, y)$ d'entiers naturels solutions vérifiant $x + y \le 25$ .

1

On traduit la condition d'appartenance à $\mathbb{N}$ ( $x \ge 0$ et $y \ge 0$ ) :

2

5k + 3 \ge 0 \implies k \ge -\frac{3}{5} \quad \text{et} \quad 7k + 4 \ge 0 \implies k \ge -\frac{4}{7}

3

Puisque $k$ est un entier relatif, ces deux inégalités imposent $k \ge 0$ .

4

On injecte les expressions de $x$ et $y$ dans la contrainte $x + y \le 25$ :

5

(5k + 3) + (7k + 4) \le 25 \iff 12k + 7 \le 25 \iff 12k \le 18 \iff k \le 1{,}5

6

Les entiers relatifs vérifiant $0 \le k \le 1{,}5$ sont $k = 0$ et $k = 1$ .

7

Pour $k = 0$ : $(x, y) = (3 \; ; \; 4)$ . Pour $k = 1$ : $(x, y) = (8 \; ; \; 11)$ . Les couples solutions sont $(3 \; ; \; 4)$ et $(8 \; ; \; 11)$ .

Vérification · 25

On considère dans $\mathbb{Z} \times \mathbb{Z}$ l'égalité $11(x - 2) = 13(y - 1)$ . Sachant que $11 \wedge 13 = 1$ , quelle est l'expression générale de l'inconnue $x$ en fonction de $k \in \mathbb{Z}$ ?

Remarque

Comme $11$ divise $13(y - 1)$ et $11 \wedge 13 = 1$ , le lemme de Gauss assure que $11$ divise $y - 1$ , donc $y - 1 = 11k$ . En reportant : $11(x - 2) = 13(11k) \iff x - 2 = 13k$ , d'où $x = 13k + 2$ .

Point de départ · 26

Les entiers $23$ et $8$ ont tous les deux pour reste $3$ dans la division euclidienne par $5$ . Leur différence $23 - 8 = 15$ est-elle un multiple de $5$ ?

Remarque

Oui, car $23 - 8 = 15 = 5 \times 3$ . Deux entiers ont le même reste dans la division euclidienne par $n$ si et seulement si leur différence est un multiple de $n$ : c'est le principe fondamental de la relation de congruence.

Définition · 27

Relation de congruence et compatibilité opératoire

Soit $n \in \mathbb{N}^*$ . Deux entiers relatifs $a$ et $b$ sont dits congrus modulo $n$ s'ils ont le même reste dans la division euclidienne par $n$ :

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

La congruence est compatible avec l'addition, la soustraction, la multiplication et les puissances entières :

$a \equiv b \pmod n \implies a^p \equiv b^p \pmod n \quad \text{pour tout } p \in \mathbb{N}$

Piège classique · 28

On a la relation $2x \equiv 2 \times 4 \pmod 6$ . Peut-on en déduire directement que $x \equiv 4 \pmod 6$ ?

Attention

Simplifier par $2$ des deux côtés en laissant le module $6$ inchangé.

À la place : On ne peut simplifier $ca \equiv cb \pmod n$ par $c$ en gardant le même module que si $c \wedge n = 1$ . Ici, $2 \wedge 6 = 2 \neq 1$ . Par exemple, pour $x = 1$ , $2(1) = 2 \equiv 8 \pmod 6$ , alors que $1 \not\equiv 4 \pmod 6$ .

Définition · 29

Règles de simplification dans les congruences

Pour simplifier un facteur $c$ non nul dans une congruence, deux situations se présentent selon son PGCD avec le module :

$ca \equiv cb \pmod n \quad \text{et} \quad c \wedge n = 1 \implies a \equiv b \pmod n$

Si le facteur $c$ divise également le module $n$ , la simplification impose de réduire conjointement le module :

$ca \equiv cb \pmod n \iff a \equiv b \pmod{\frac{n}{c \wedge n}}$

Exemple travaillé · 30

Résoudre dans $\mathbb{Z}$ l'équation de congruence : $9x \equiv 15 \pmod{24}$ .

1

On cherche le PGCD des coefficients et du module : $9 \wedge 24 = 3$ . Comme $3$ divise $15$ , l'équation admet des solutions.

2

On applique la règle de simplification en divisant chaque membre et le module par $3$ :

3

9x \equiv 15 \pmod{24} \iff 3x \equiv 5 \pmod 8

4

On cherche un inverse de $3$ modulo $8$ : on remarque que $3 \times 3 = 9 \equiv 1 \pmod 8$ .

5

On multiplie les deux membres par $3$ (puisque $3 \wedge 8 = 1$ ) :

6

3 \times (3x) \equiv 3 \times 5 \pmod 8 \iff x \equiv 15 \equiv 7 \pmod 8

7

L'ensemble des solutions dans $\mathbb{Z}$ est constitué des entiers de la forme $x = 8k + 7$ avec $k \in \mathbb{Z}$ .

Exemple travaillé · 31

Déterminer le reste de la division euclidienne de $3^{1000}$ par $7$ .

1

On calcule les puissances successives de $3$ modulo $7$ pour déterminer la période des restes :

2

3^1 \equiv 3, \quad 3^2 \equiv 2, \quad 3^3 \equiv 6 \equiv -1, \quad 3^6 = (3^3)^2 \equiv (-1)^2 \equiv 1 \pmod 7

3

Puisque $3^6 \equiv 1 \pmod 7$ , les restes se répètent avec une période de $6$ : pour tout $n \in \mathbb{N}$ , $3^{n+6} \equiv 3^n \pmod 7$ .

4

On effectue la division euclidienne de l'exposant $1000$ par la période $6$ :

5

1000 = 6 \times 166 + 4

6

On décompose la puissance à l'aide de cette division :

7

3^{1000} = (3^6)^{166} \times 3^4 \equiv 1^{166} \times 3^4 \equiv 81 \pmod 7

8

Comme $81 = 7 \times 11 + 4$ , on a $81 \equiv 4 \pmod 7$ . Le reste de la division euclidienne de $3^{1000}$ par $7$ est donc $4$ .

Vérification · 32

On donne $2^3 \equiv 1 \pmod 7$ . Quel est le reste de la division euclidienne de $2^{2009}$ par $7$ ?

Remarque

On effectue la division de l'exposant par la période $3$ : $2009 = 3 \times 669 + 2$ . On a donc $2^{2009} = (2^3)^{669} \times 2^2 \equiv 1^{669} \times 4 \equiv 4 \pmod 7$ . Comme $0 \le 4 < 7$ , le reste est $4$ .

Arithmétique — cours

Le cours

Théorème de la division euclidienne dans $\mathbb{Z}$

PGCD, PPCM et forme irréductible dans $\mathbb{Z}$

Combinaisons linéaires et diviseurs communs

Théorème de Bézout et condition de résolubilité

Lemme de Gauss et divisibilité conjointe

Relation de congruence et compatibilité opératoire

Règles de simplification dans les congruences

Chapitres liés

Continuer sur Lumio

Arithmétique — cours

Le cours

Théorème de la division euclidienne dans Z\mathbb{Z}Z

PGCD, PPCM et forme irréductible dans Z\mathbb{Z}Z

Combinaisons linéaires et diviseurs communs

Théorème de Bézout et condition de résolubilité

Lemme de Gauss et divisibilité conjointe

Relation de congruence et compatibilité opératoire

Règles de simplification dans les congruences

Chapitres liés

Continuer sur Lumio

Théorème de la division euclidienne dans $\mathbb{Z}$

PGCD, PPCM et forme irréductible dans $\mathbb{Z}$