Imprimer le chapitre

Toutes les leçons du chapitre, prêtes pour le papier. Les séries d'exercices sont notées A, B, C… et corrigées à la fin.

Avec le corrigé

Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.

1. PGCD et algorithme d'Euclide

Échauffement

Trois questions rapides sur des leçons déjà vues.

Découvrir

Quel est le plus grand diviseur commun à 12 et 18 ?

$6$
$36$

L'idée clé

L'algorithme d'Euclide répète des divisions euclidiennes.

$\mathrm{PGCD}(a ; b) = \mathrm{PGCD}(b ; r)$ , où $r$ est le reste de la division de $a$ par $b$ . Le PGCD est le dernier reste non nul.

$a$ et $b$ sont premiers entre eux si $\mathrm{PGCD}(a ; b) = 1$ .

Exemple corrigé

Calcule $\mathrm{PGCD}(252 ; 105)$ .

\mathrm{PGCD}(105 ; 42)

252 = 105 × 2 + 42.

\mathrm{PGCD}(42 ; 21)

105 = 42 × 2 + 21.

21

42 = 21 × 2 + 0.

À toi, guidé

À toi : calcule $\mathrm{PGCD}(35 ; 14)$ .

7

35 = 14 × 2 + 7, 14 = 7 × 2.

Entraînement ★

Calcule $\mathrm{PGCD}(14 ; 16)$ .
Calcule $\mathrm{PGCD}(15 ; 20)$ .
Calcule $\mathrm{PGCD}(63 ; 72)$ .

Attention !

Entraînement ★★

Les nombres $5$ et $6$ sont-ils premiers entre eux ?
1. Oui, toujours
2. Seulement s'ils sont premiers
3. Non
Les nombres $2$ et $3$ sont-ils premiers entre eux ?
1. Oui, toujours
2. Seulement s'ils sont premiers
3. Non

Calcule $\mathrm{PGCD}(6 ; 2)$ .

Dans l'algorithme d'Euclide pour $36$ et 15, on remplace le couple par (15 ; $r$ ). Que vaut $r$ ?

Bilan

Trois questions pour vérifier que c'est acquis.

Calcule $\mathrm{PGCD}(14 ; 16)$ .
Calcule $\mathrm{PGCD}(15 ; 20)$ .
Calcule $\mathrm{PGCD}(63 ; 72)$ .

Fiche résumé

PGCD

$\mathrm{PGCD}(a ; b) = \mathrm{PGCD}(b ; r)$ .
Dernier reste non nul.

Attention : ne confonds pas avec le dernier quotient.

2. Théorème de Bézout

Échauffement

Trois questions rapides sur des leçons déjà vues.

Découvrir

On a $3 \times 2 + 5 \times (-1) = 1$ . Que peut-on dire de 3 et 5 ?

Ils sont premiers entre eux
Ils ont 2 pour diviseur commun

L'idée clé

Le théorème relie PGCD et combinaisons linéaires.

Bézout : $a$ et $b$ sont premiers entre eux si et seulement s'il existe des entiers $u$ et $v$ tels que $au + bv = 1$ .

Plus généralement, il existe $u$ et $v$ tels que $au + bv = \mathrm{PGCD}(a ; b)$ .

Exemple corrigé

Trouve un couple $(u ; v)$ tel que $7u + 3v = 1$ .

7 = 3 \times 2 + 1

Euclide.

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

On isole 1.

(u ; v) = (1 ; -2)

On lit.

À toi, guidé

À toi : avec $5u + 2v = 1$ et $u = 1$ , que vaut $v$ ?

-2

5 + 2v = 1.

Entraînement ★

On a $9 \times 1 + 4 \times v = 1$ . Que vaut $v$ ?
On a $7 \times 1 + 3 \times v = 1$ . Que vaut $v$ ?
On a $11 \times 1 + 5 \times v = 1$ . Que vaut $v$ ?

Attention !

Entraînement ★★

Existe-t-il des entiers $u$ et $v$ tels que $12u + 24v = 1$ ?
1. Non, car le PGCD n'est pas 1
2. Oui, toujours
3. Oui, avec $u = v = 1$
Existe-t-il des entiers $u$ et $v$ tels que $10u + 20v = 1$ ?
1. Non, car le PGCD n'est pas 1
2. Oui, toujours
3. Oui, avec $u = v = 1$

Avec $u = 1$ et $v = -2$ , que vaut $(5)u + 2v$ ?

Selon le théorème de Bézout, que signifie l'existence d'entiers $u$ , $v$ tels que $au + bv = 1$ ?
1. $a$ et $b$ sont premiers entre eux
2. $a$ divise $b$
3. $a$ et $b$ sont des nombres premiers

Bilan

Trois questions pour vérifier que c'est acquis.

On a $9 \times 1 + 4 \times v = 1$ . Que vaut $v$ ?
On a $7 \times 1 + 3 \times v = 1$ . Que vaut $v$ ?
On a $11 \times 1 + 5 \times v = 1$ . Que vaut $v$ ?

Fiche résumé

Bézout

$au + bv = 1 \iff \mathrm{PGCD}(a ; b) = 1$ .
On remonte l'algorithme d'Euclide.

Attention : le couple $(u ; v)$ n'est pas unique.

3. Théorème de Gauss

Échauffement

Trois questions rapides sur des leçons déjà vues.

Découvrir

3 divise $5x$ . Peut-on affirmer que 3 divise $x$ ?

Oui, car 3 et 5 sont premiers entre eux
Non, jamais

L'idée clé

Ce théorème sert à résoudre des équations en entiers.

Gauss : si

a

divise

bc

et si

a

b

sont premiers entre eux, alors

a

divise

c

Exemple corrigé

On sait que $7x = 4y$ , avec $x$ et $y$ entiers. Que dire de $y$ ?

7 \mid 4y

7 divise 4y.

7 \mid y

7 et 4 sont premiers entre eux.

À toi, guidé

À toi : 5 divise $3n$ . Lequel divise $n$ ?

5

5 et 3 sont premiers entre eux.

Entraînement ★

On sait que 5 divise $11n$ , avec $n$ entier. Quel est le plus petit entier $n > 0$ possible ?
On sait que 7 divise $8n$ , avec $n$ entier. Quel est le plus petit entier $n > 0$ possible ?
On sait que 3 divise $8n$ , avec $n$ entier. Quel est le plus petit entier $n > 0$ possible ?

Attention !

Entraînement ★★

Quelle hypothèse faut-il pour appliquer le théorème de Gauss à « $a$ divise $bc$ » ?
1. $a$ et $b$ sont premiers entre eux
2. $a$ est pair
3. $b$ et $c$ sont égaux
Quelle hypothèse faut-il pour appliquer le théorème de Gauss à « $a$ divise $bc$ » ?
1. $a$ et $b$ sont premiers entre eux
2. $a$ est pair
3. $b$ et $c$ sont égaux

7 divise $9n$ , et 7 et 9 sont premiers entre eux. Quel est le plus petit entier $n > 0$ possible ?

6 divise $4 \times 3$ . Peut-on en conclure que 6 divise 4 ou 3 ?
1. Non : 6 n'est premier ni avec 4 ni avec 3
2. Oui : par le théorème de Gauss
3. Oui : 6 divise toujours un facteur

Bilan

Trois questions pour vérifier que c'est acquis.

On sait que 5 divise $11n$ , avec $n$ entier. Quel est le plus petit entier $n > 0$ possible ?
On sait que 7 divise $8n$ , avec $n$ entier. Quel est le plus petit entier $n > 0$ possible ?
On sait que 3 divise $8n$ , avec $n$ entier. Quel est le plus petit entier $n > 0$ possible ?

Fiche résumé

Gauss

Si $a \mid bc$ et $\mathrm{PGCD}(a ; b) = 1$ , alors $a \mid c$ .
Base des équations diophantiennes.

Attention : vérifie toujours « premiers entre eux ».

4. Congruence ax ≡ b, inverse modulo n et chiffrement

Échauffement

Trois questions rapides sur des leçons déjà vues.

Découvrir

On veut résoudre $3x \equiv 1\ [7]$ . Quelle valeur de $x$ convient ?

$5$
$\dfrac{1}{3}$

L'idée clé

On ne divise pas : on multiplie par un inverse.

Si $a$ et $n$ sont premiers entre eux, il existe un inverse $a'$ de $a$ modulo $n$ : $aa' \equiv 1\ [n]$ . Alors $ax \equiv b\ [n] \iff x \equiv a'b\ [n]$ .

Chiffrement affine : on code $x$ par $y \equiv ax + b\ [26]$ ; pour déchiffrer, on utilise l'inverse de $a$ modulo 26.

Exemple corrigé

Résous $3x \equiv 4\ [7]$ .

5 \times 3 \equiv 1\ [7]

L'inverse de 3 est 5.

x \equiv 20\ [7]

On multiplie par 5.

x \equiv 6\ [7]

On réduit.

À toi, guidé

À toi : quel est l'inverse de 2 modulo 5 ?

3

2 × 3 = 6 ≡ 1.

Entraînement ★

Résous $3x \equiv 12\ [7]$ : donne la solution $x$ entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Résous $3x \equiv 9\ [7]$ : donne la solution $x$ entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Résous $3x \equiv 6\ [7]$ : donne la solution $x$ entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)

Attention !

Entraînement ★★

Avec le chiffrement $y \equiv 3x + 1\ [26]$ , quel nombre $y$ code $x = 3$ ?
Avec le chiffrement $y \equiv 3x + 1\ [26]$ , quel nombre $y$ code $x = 5$ ?

Quel est l'inverse de 2 modulo 5 ?

Résous $2x \equiv 10\ [11]$ : donne $x$ entre 0 et 10.

Bilan

Trois questions pour vérifier que c'est acquis.

Résous $3x \equiv 12\ [7]$ : donne la solution $x$ entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Résous $3x \equiv 9\ [7]$ : donne la solution $x$ entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Résous $3x \equiv 6\ [7]$ : donne la solution $x$ entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)

Fiche résumé

Inverse modulo $n$

Il existe si $\mathrm{PGCD}(a ; n) = 1$ .
$ax \equiv b \iff x \equiv a'b\ [n]$ .

Attention : on multiplie, on ne divise pas.

5. Équations diophantiennes

Échauffement

Trois questions rapides sur des leçons déjà vues.

Découvrir

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

L'idée clé

$ax + by = c$ a des solutions si et seulement si $\mathrm{PGCD}(a ; b)$ divise $c$ .

On trouve une solution particulière

(x_0 ; y_0)

, puis on utilise Gauss. Si

a

b

sont premiers entre eux, les solutions sont

x = x_0 + bk

y = y_0 - ak

k \in \mathbb{Z}

Exemple corrigé

Résous $3x + 5y = 1$ .

(x_0 ; y_0) = (2 ; -1)

Solution particulière.

3(x - 2) = 5(-1 - y)

On soustrait.

x = 2 + 5k

y = -1 - 3k

Gauss.

À toi, guidé

À toi : pour $2x + 3y = 1$ , on a la solution $(2 ; -1)$ . Combien vaut $x$ pour $k = 1$ dans $x = 2 + 3k$ ?

5

2 + 3.

Entraînement ★

Les solutions de $3x + 5y = 1$ sont $x = 2 + 5k$ , $y = -1 - 3k$ . Que vaut $x$ pour $k = 2$ ?
Les solutions de $3x + 5y = 1$ sont $x = 2 + 5k$ , $y = -1 - 3k$ . Que vaut $x$ pour $k = 4$ ?
Les solutions de $3x + 5y = 1$ sont $x = 2 + 5k$ , $y = -1 - 3k$ . Que vaut $x$ pour $k = 3$ ?

Attention !

Entraînement ★★

L'équation $8x + 16y = 9$ a-t-elle des solutions entières ?
1. Non
2. Oui, une seule
3. Oui, une infinité
L'équation $4x + 8y = 5$ a-t-elle des solutions entières ?
1. Non
2. Oui, une seule
3. Oui, une infinité

Problème final. On résout $3x + 5y = 18$ en entiers.

Les solutions de $3x + 5y = 1$ sont $x = 2 + 5k$ , $y = -1 - 3k$ . Que vaut $y$ pour $k = 3$ ?

Une équation $ax + by = c$ a une solution entière. Combien en a-t-elle en tout ?
1. Une infinité
2. Une seule
3. Deux

Bilan

Trois questions pour vérifier que c'est acquis.

Les solutions de $3x + 5y = 1$ sont $x = 2 + 5k$ , $y = -1 - 3k$ . Que vaut $x$ pour $k = 2$ ?
Les solutions de $3x + 5y = 1$ sont $x = 2 + 5k$ , $y = -1 - 3k$ . Que vaut $x$ pour $k = 4$ ?
Les solutions de $3x + 5y = 1$ sont $x = 2 + 5k$ , $y = -1 - 3k$ . Que vaut $x$ pour $k = 3$ ?

Fiche résumé

Équations diophantiennes

Existence : $\mathrm{PGCD}(a ; b) \mid c$ .
Solution particulière, puis Gauss.

Attention : il y a une infinité de solutions.

Corrigé: PGCD, Bézout et Gauss

1. PGCD et algorithme d'Euclide

Oui, toujours
Oui, toujours

2. Théorème de Bézout

$-2$
$-2$
$-2$

Non, car le PGCD n'est pas 1
Non, car le PGCD n'est pas 1

$a$ et $b$ sont premiers entre eux

$-2$
$-2$
$-2$

3. Théorème de Gauss

$a$ et $b$ sont premiers entre eux
$a$ et $b$ sont premiers entre eux

Non : 6 n'est premier ni avec 4 ni avec 3

4. Congruence ax ≡ b, inverse modulo n et chiffrement

$10$
$16$

5. Équations diophantiennes

$12$
$22$
$17$

$-3$

$-10$

Une infinité

$12$
$22$
$17$