Guide de l'enseignant: Algorithme d'Euclide

Trouve le PGCD de deux nombres par des divisions euclidiennes successives, puis utilise-le pour simplifier des fractions et calculer le PPCM.

Présenter la leçon Partager dans Classroom Voir la page élève

Utiliser cette leçon en classe

Gratuit, sans compte élève.

Partager avec les élèves

Les élèves ouvrent la leçon et s'entraînent avec une correction immédiate.

Fiche d'exercices à imprimer

Tous les exercices sur papier, avec un corrigé séparé.

Fiche d'exercices Corrigé

Quiz de classe

10 questions sur Facteurs & Multiples. Les élèves participent avec un prénom, vous voyez tous les scores.

Pour les enseignants

Objectifs d'apprentissage

Écrire une division euclidienne sous la forme $a = q \times b + r$ avec $0 \le r < b$
Calculer le PGCD de deux nombres avec l'algorithme d'Euclide et avec la méthode des soustractions successives
Expliquer pourquoi $\text{PGCD}(a, b) = \text{PGCD}(b, r)$ et relier l'algorithme au découpage d'un rectangle en carrés
Utiliser le PGCD pour rendre une fraction irréductible et calculer $\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$
Déterminer si deux nombres sont premiers entre eux et comparer l'algorithme à la décomposition en facteurs premiers

Prérequis

• Plus grand commun diviseur (PGCD) : le trouver en listant les diviseurs et par décomposition en facteurs premiers
• Plus petit commun multiple (PPCM) et sa signification
• Décomposition en facteurs premiers, nombres premiers et nombres composés
• Division euclidienne de nombres entiers

Amorces de discussion

1. Pourquoi l'algorithme s'arrête-t-il toujours ? Que deviennent les nombres à chaque étape ?
2. Si $d$ divise $48$ et $18$ , pourquoi doit-il aussi diviser $48 - 2 \times 18 = 12$ ?
3. Quand préférerais-tu la décomposition en facteurs premiers, et quand l'algorithme d'Euclide ?
4. Pourquoi des nombres de Fibonacci voisins comme $144$ et $89$ demandent-ils autant d'étapes ?
5. Comment le découpage d'un rectangle en carrés montre-t-il les mêmes étapes que les divisions ?

Idées reçues courantes

Le PGCD est le dernier nombre écrit, souvent le reste $0$ ou un quotient

Remédiation: Repère q et r de chaque ligne avec des couleurs différentes. Entoure le diviseur de la ligne dont le reste est $0$ et vérifie qu'il divise les deux nombres de départ.

Après la première division, on continue avec le grand nombre de départ

Remédiation: Utilise l'image du rectangle : une fois les carrés découpés, la grande longueur a disparu et il ne reste que le rectangle b sur r.

L'algorithme est une astuce qui marche par hasard

Remédiation: Montre avec $48$ , $18$ et $12$ que tout diviseur commun de $48$ et $18$ divise $12$ , et que tout diviseur commun de $18$ et $12$ divise $48$ . Liste les deux ensembles de diviseurs communs : ils sont égaux.

Idées de différenciation

Pour les élèves en difficulté:

• Commencer par la méthode des soustractions sur de petits couples comme (35, 14) avant de diviser
• Utiliser des rectangles en papier quadrillé et découper réellement les carrés
• Fournir un tableau avec les colonnes a, b, q, r à remplir ligne par ligne

Pour les élèves au niveau:

• Appliquer l'algorithme à des couples de trois ou quatre chiffres comme (1071, 462)
• Rendre irréductibles des fractions comme $\frac{391}{667}$ grâce au PGCD
• Calculer des PPCM avec $\frac{a \times b}{\text{PGCD}(a, b)}$ et les vérifier

Pour les élèves avancés:

• Démontrer en général que $\text{PGCD}(a, b) = \text{PGCD}(b, r)$
• Chercher pourquoi des nombres de Fibonacci voisins demandent le plus d'étapes
• Découvrir l'algorithme d'Euclide étendu : écrire $\text{PGCD}(a, b)$ sous la forme $x \times a + y \times b$

Alignement aux standards

6.NS.B.4 (CCSS.MATH.CONTENT.6.NS.B.4)
Trouver le plus grand commun diviseur et le plus petit commun multiple de deux nombres entiers
6.NS.B.2 (CCSS.MATH.CONTENT.6.NS.B.2)
Diviser avec aisance des nombres à plusieurs chiffres avec l'algorithme posé
MP.7 (CCSS.MATH.PRACTICE.MP7)
Repérer et utiliser des structures

Ressources de la leçon

visualDu rectangle aux carrés
Vue interactive qui découpe un rectangle a sur b en carrés les plus grands possibles tout en écrivant chaque ligne a = q × b + r
activityCarrés sur papier quadrillé
Les élèves tracent un rectangle de 48 sur 18 sur du papier quadrillé et découpent aux ciseaux les plus grands carrés jusqu'à ce qu'il ne reste que des carrés identiques
gameCourse au PGCD
Une équipe utilise la décomposition en facteurs premiers, l'autre l'algorithme d'Euclide, sur des couples comme (1071, 462) et (391, 667)
worksheetExercices sur les lignes d'Euclide
Compléter quotients et restes, puis simplifier des fractions et calculer des PPCM à partir du PGCD

Contenu de la leçon

Tout ce que voient les élèves : définition, exemples, erreurs fréquentes, applications. Touchez pour ouvrir.

Définition

L'algorithme d'Euclide est une méthode rapide pour trouver le plus grand commun diviseur (PGCD) de deux nombres entiers, sans lister les diviseurs ni faire d'arbre de facteurs.

Divise le plus grand nombre

a

par le plus petit nombre

b

et écris le résultat sous forme de division euclidienne :

a = q \times b + r, \quad 0 \le r < b

Ici,

q

est le quotient et

r

est le reste. Ensuite, **remplace le couple

(a, b)

par

(b, r)

** et divise à nouveau. Recommence jusqu'à obtenir un reste égal à

0

. Le dernier reste non nul (le diviseur de la dernière ligne) est le PGCD.

Exemple :

\text{PGCD}(48, 18)

$48 = 2 \times 18 + 12$
$18 = 1 \times 12 + 6$
$12 = 2 \times 6 + 0$

Le reste vaut

0

, donc

\text{PGCD}(48, 18) = 6

Pourquoi ça marche : si un nombre

d

divise à la fois

a

b

, il divise aussi

r = a - q \times b

. Et si

d

divise à la fois

b

r

, il divise aussi

a = q \times b + r

. Les couples

(a, b)

(b, r)

ont donc exactement les mêmes diviseurs communs, et donc le même PGCD :

\text{PGCD}(a, b) = \text{PGCD}(b, r)

Les nombres diminuent à chaque étape, donc l'algorithme s'arrête toujours.

Exemples résolus

Un rectangle mesure

48

sur

18

. Découpe à chaque fois les plus grands carrés possibles. Quel est le côté des carrés qui tombent juste à la fin ?

Découpe des carrés de côté 18 sur la longueur

Deux carrés

18 \times 18

rentrent, il reste

12

48 = 2 \times 18 + 12

→ Rectangle restant

18 \times 12

Découpe des carrés de côté 12 dans le reste

Un carré

12 \times 12

rentre, il reste

6

18 = 1 \times 12 + 6

→ Rectangle restant

12 \times 6

Découpe des carrés de côté 6

Deux carrés

6 \times 6

rentrent exactement :

12 = 2 \times 6 + 0

→ Il ne reste rien

Pave tout le rectangle avec le dernier carré

6

divise

48

18

\frac{48}{6} \times \frac{18}{6} = 8 \times 3

→

24

carrés de côté

6

le recouvrent

Réponse: Les carrés de côté $6$ tombent juste, donc $\text{PGCD}(48, 18) = 6$ . Chaque découpe correspond à une ligne de l'algorithme.

Erreurs courantes

Garder l'ancien grand nombre : après $48 = 2 \times 18 + 12$ , continuer avec $48$ et $12$

Pourquoi c'est faux: L'algorithme marche parce que $\text{PGCD}(a, b) = \text{PGCD}(b, r)$ . Le nombre $a$ ne sert plus après la première division.

Correct: Le couple suivant est $(18, 12)$ : l'ancien diviseur et le reste. Donc $18 = 1 \times 12 + 6$ .

Donner $0$ ou le dernier quotient comme PGCD

Pourquoi c'est faux: La dernière ligne a un reste égal à $0$ , ce qui indique seulement qu'il faut s'arrêter. Le quotient compte combien de carrés rentrent, ce n'est pas un diviseur commun.

Correct: Le PGCD est le dernier reste non nul, c'est-à-dire le diviseur de la dernière ligne. Dans $12 = 2 \times 6 + 0$ , c'est $6$ .

Écrire un reste trop grand, comme $1071 = 1 \times 462 + 609$

Pourquoi c'est faux: L'égalité est vraie, mais $609 > 462$ , donc $462$ rentre encore une fois. Le reste doit être plus petit que le diviseur.

Correct: Prends le plus grand quotient possible : $1071 = 2 \times 462 + 147$ avec $147 < 462$ .

Prendre $a \times b$ comme PPCM

Pourquoi c'est faux: $a \times b$ est toujours un multiple commun, mais en général pas le plus petit : $84 \times 120 = 10080$ compte deux fois le diviseur commun $12$ .

Correct: Divise par le PGCD : $\text{PPCM}(84, 120) = \frac{84 \times 120}{12} = 840$ .

Pourquoi c'est important

L'algorithme d'Euclide a plus de 2300 ans (Euclide l'a décrit vers 300 av. J.-C.) et il reste l'un des algorithmes les plus utilisés au monde :

Grands nombres : décomposer $1071$ ou $391$ en facteurs premiers est long, mais trois ou quatre divisions donnent le PGCD tout de suite. Pour des nombres de plusieurs centaines de chiffres, la décomposition est pratiquement impossible, alors que l'algorithme d'Euclide se termine en quelques milliers d'étapes rapides au plus.
Fractions : pour simplifier $\frac{391}{667}$ , il faut $\text{PGCD}(391, 667) = 23$ , difficile à voir en décomposant mais rapide avec l'algorithme.
PPCM : dès que tu connais le PGCD, $\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$ . Un seul algorithme donne donc les deux.
Carrelage, engrenages et écrans : le plus grand carreau carré pour un sol, le moment où deux engrenages se retrouvent dans la même position et la raison pour laquelle un écran $1920 \times 1080$ est au format $16:9$ se ramènent tous au PGCD.
Sécurité sur Internet : des systèmes de chiffrement comme RSA utilisent une version étendue de cet algorithme chaque fois que tu ouvres un site sécurisé.

Applications dans le monde réel

Carreler un sol avec les plus grands carreaux carrés

Un carreleur veut couvrir un sol rectangulaire avec des carreaux carrés identiques sans en couper aucun. Le plus grand côté possible est le PGCD des deux longueurs.

Exemple:

Un panneau de $48$ cm sur $18$ cm est recouvert exactement par des carrés de $6$ cm : $\text{PGCD}(48, 18) = 6$ , soit $8 \times 3 = 24$ carreaux.

1Essaie par toi-même

Le sol d'un couloir mesure $168$ cm sur $120$ cm. Il doit être couvert de carreaux carrés identiques, sans découpe et sans espace.

Quel est le côté, en cm, du plus grand carreau carré qui convient ?

Étape 1 : Écris l'expression mathématique

Calcule $\text{PGCD}(168, 120)$ avec l'algorithme d'Euclide :

Engrenages et cycles qui se répètent

Quand deux roues dentées tournent ensemble, les mêmes deux dents se retrouvent après un nombre de dents égal au PPCM des nombres de dents. L'algorithme d'Euclide donne le PGCD, et le PPCM s'en déduit.

Exemple:

Des roues de $18$ et $48$ dents : $\text{PGCD} = 6$ , donc les mêmes dents se retrouvent après $\frac{18 \times 48}{6} = 144$ dents.

2Essaie par toi-même

Le plateau d'un vélo a $84$ dents et un petit pignon a $36$ dents. Deux dents marquées se touchent maintenant.

Après combien de dents les deux dents marquées se touchent-elles à nouveau ?

Étape 1 : Écris l'expression mathématique

Calcule $\text{PPCM}(84, 36) = \frac{84 \times 36}{\text{PGCD}(84, 36)}$ :

Le format des écrans

Une définition d'écran comme $1920 \times 1080$ devient un format en divisant les deux nombres par leur PGCD.

Exemple:

$1280 \times 1024$ : $\text{PGCD}(1280, 1024) = 256$ , donc le format est $5:4$ .

3Essaie par toi-même

Un écran a $1920$ pixels sur $1080$ . Pour écrire son format, tu divises les deux nombres par leur PGCD.

Combien vaut $\text{PGCD}(1920, 1080)$ ?

Étape 1 : Écris l'expression mathématique

Applique l'algorithme d'Euclide à $1920$ et $1080$ :

Points clés

1Algorithme d'Euclide : divise $a$ par $b$ sous la forme $a = q \times b + r$ avec $0 \le r < b$ , puis remplace $(a, b)$ par $(b, r)$ jusqu'à obtenir un reste nul
2Le PGCD est le dernier reste non nul, c'est-à-dire le diviseur de la dernière ligne
3Ça marche parce que $\text{PGCD}(a, b) = \text{PGCD}(b, r)$ : les deux couples ont les mêmes diviseurs communs
4Géométriquement, on découpe un rectangle $a \times b$ en carrés les plus grands possibles ; le côté du dernier carré est le PGCD
5La méthode des soustractions successives retire encore et encore le plus petit nombre ; la division en est le raccourci
6On l'utilise pour rendre une fraction irréductible, pour calculer $\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$ et pour savoir si deux nombres sont premiers entre eux (PGCD $= 1$ )

Questions fréquentes

Est-ce que l'ordre des nombres compte ?

Non. Si tu commences avec le plus petit nombre, la première ligne est du type

18 = 0 \times 48 + 18

, ce qui échange simplement les deux nombres. Commencer par le plus grand évite cette étape.

L'algorithme d'Euclide est-il plus rapide que la décomposition en facteurs premiers ?

Pour de petits nombres comme

12

18

, les deux méthodes sont rapides. Pour de grands nombres, oui, de très loin : tu n'as besoin de trouver aucun nombre premier.

\text{PGCD}(1071, 462)

demande trois divisions, alors que la décomposition exige

1071 = 3^2 \times 7 \times 17

462 = 2 \times 3 \times 7 \times 11

Que signifie un PGCD égal à 1 à la fin ?

Les deux nombres sont alors premiers entre eux : ils n'ont aucun diviseur commun autre que

1

. Deux nombres de Fibonacci voisins comme

144

89

sont toujours premiers entre eux, et ce sont eux qui demandent le plus d'étapes pour leur taille.

Puis-je l'utiliser pour trois nombres ?

Oui, deux par deux :

\text{PGCD}(a, b, c) = \text{PGCD}(\text{PGCD}(a, b), c)

. Par exemple,

\text{PGCD}(840, 1176) = 168

\text{PGCD}(168, 1260) = 84

, donc le PGCD des trois nombres est

84

Glossaire

Algorithme d'Euclide: Méthode pour le PGCD de deux nombres : faire la division euclidienne, remplacer le couple par (diviseur, reste), recommencer jusqu'à un reste nul
Division euclidienne: L'écriture $a = q \times b + r$ avec $0 \le r < b$ , par exemple $1071 = 2 \times 462 + 147$
Quotient: Le nombre $q$ de fois que $b$ rentre entièrement dans $a$
Reste: Le nombre $r$ qui reste après la division, toujours plus petit que le diviseur
Premiers entre eux: Deux nombres dont le PGCD vaut $1$ , comme $144$ et $89$
Plus petit commun multiple (PPCM): Le plus petit nombre positif divisible par les deux nombres ; $\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$

Carte des formules

Division euclidienne

a = q \times b + r, \quad 0 \le r < b

Une ligne de l'algorithme : $q$ est le quotient, $r$ le reste

Étape clé

\text{PGCD}(a, b) = \text{PGCD}(b, r)

Remplace le couple par (diviseur, reste) et recommence jusqu'à $r = 0$

PPCM à partir du PGCD

\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}

Multiplie les nombres et divise par leur PGCD

Nombres premiers entre eux

\text{PGCD}(a, b) = 1

Les nombres n'ont aucun diviseur commun autre que $1$

Plus sur ce sujet

Guide de l'enseignant: Algorithme d'Euclide

Utiliser cette leçon en classe

Pour les enseignants

Pour les élèves en difficulté:

Pour les élèves au niveau:

Pour les élèves avancés:

Contenu de la leçon

Définition

Exemples résolus

Erreurs courantes

Pourquoi c'est important

Applications dans le monde réel

Carreler un sol avec les plus grands carreaux carrés

Engrenages et cycles qui se répètent

Le format des écrans

Points clés

Questions fréquentes

Glossaire

Carte des formules

Division euclidienne

Étape clé

PPCM à partir du PGCD

Nombres premiers entre eux

Plus sur ce sujet

Diviseurs et multiples

Décomposition en facteurs premiers

Nombres premiers et composés

Plus Grand Commun Diviseur (PGCD)