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

Pour de petits nombres comme $12$ et $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$ et $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$ et $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$ et $\text{PGCD}(168, 1260) = 84$, donc le PGCD des trois nombres est $84$.

Ressources enseignants

Algorithme d'Euclide

Q: 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.

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

Avancé25 minLeçon

Partager dans Classroom

Fiche d'exercices à imprimer

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.

Essaie tout de suite

Dans l'algorithme d'Euclide, tu écris

a = q \times b + r

avec

0 \le r < b

. Quel couple divises-tu ensuite ?

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

Visuel interactif

Les plus grands carrés dans un rectangle : choisis un couple

Premier nombreDeuxième nombre

Rectangle 1071 × 462

Appuie sur Étape suivante pour découper les plus grands carrés possibles.

À toi : écris le quotient et le reste de chaque ligne

Premier nombreDeuxième nombre

Rectangle 168 × 120

Combien de fois 120 entre-t-il dans 168, et que reste-t-il ?

168 =× 120 +

Bac à sable interactif

Calculatrice d'expressions

Essaie ceux-ci :

Historique

Aucun calcul pour l'instant

Exercices pratiques

18 exercices

Problème 1 sur 18

Facile

Dans l'algorithme d'Euclide, tu écris

a = q \times b + r

avec

0 \le r < b

. Quel couple divises-tu ensuite ?

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

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.

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$

Défi du jourUn problème, trois essais

Plus sur ce sujet

Définition

Exemples résolus

Erreurs courantes

Visuel interactif

Bac à sable interactif

Calculatrice d'expressions

Historique

Exercices pratiques

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)