PGCD et algorithme d'Euclide

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

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

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$ .

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 : calcule $\mathrm{PGCD}(35 ; 14)$ .

7

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

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

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

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

PGCD

Attention : ne confonds pas avec le dernier quotient.

À propos de cette leçon