Des divisions euclidiennes successives pour aller plus vite.
www.ndolomath.com
Cours de Mathématiques : « PGCD : algorithme d’Euclide », proposé par ndolomathndolomath
Algorithme d’Euclide
💡 Idée principale : L’algorithme d’Euclide remplace les soustractions répétées par des divisions euclidiennes. Le PGCD de deux nombres est le dernier reste non nul.
Ce que tu vas apprendre
Effectuer une division euclidienne et écrire l’égalité .
Connaître la propriété .
Appliquer l’algorithme d’Euclide.
Reconnaître deux nombres premiers entre eux et rendre une fraction irréductible.
Pourquoi cette leçon ?
Avec l’algorithme des soustractions, on enlève parfois le même nombre dix ou vingt fois de suite. Une seule division euclidienne fait tout ce travail d’un coup : l’algorithme d’Euclide est donc beaucoup plus rapide pour les grands nombres.
Prérequis : vérifie tes bases
1
Effectue la division euclidienne de 158 par 12 et écris l’égalité obtenue.
2
Calcule par l’algorithme des soustractions.
3
Dans une division euclidienne, que peut-on dire du reste par rapport au diviseur ?
Situation problème : Les plants de cacao
M. Ateba, planteur à Mbalmayo, possède 1 274 plants de cacao et 546 plants de bananier. Il veut les répartir en rangées identiques, chaque rangée ayant le même nombre de cacaoyers et le même nombre de bananiers, en utilisant tous les plants. Combien de rangées au maximum peut-il faire, et comment sera composée chaque rangée ?
www.ndolomath.com
p1
Cours de Mathématiques : « PGCD : algorithme d’Euclide », proposé par ndolomathndolomath
Activité d’apprentissage
On reprend le calcul de .
Combien de fois peux-tu soustraire 546 de 1 274 ? Quel nombre obtiens-tu alors ?
Effectue la division euclidienne de 1 274 par 546. Compare le reste avec le nombre trouvé à la question 1.
Effectue la division euclidienne de 546 par ce reste, puis continue en divisant chaque diviseur par le reste obtenu, jusqu’à obtenir un reste nul.
Quel est le dernier reste non nul ? Vérifie que c’est bien un diviseur de 1 274 et de 546, puis réponds à M. Ateba.
R1
Division euclidienne
Pour tous entiers naturels et , avec , il existe un unique couple d’entiers tel que : est le quotient et le reste.
Exemple à traiter : Effectue la division euclidienne de 2 026 par 37, puis celle de 315 par 15.
R2 · Propriété du reste
Si avec , alors : Si , alors divise et .
Exemple à traiter : Sachant que , écris comme le PGCD de deux nombres plus petits.
www.ndolomath.com
p2
Cours de Mathématiques : « PGCD : algorithme d’Euclide », proposé par ndolomathndolomath
R3
Algorithme d’Euclide
1. On divise le plus grand nombre par le plus petit. 2. On divise le diviseur par le reste obtenu. 3. On recommence jusqu’à obtenir un reste nul. Le PGCD est le dernier reste non nul.
Exemple à traiter : Détermine et par l’algorithme d’Euclide.
R4
Nombres premiers entre eux
Deux entiers sont premiers entre eux lorsque leur PGCD est égal à 1. Pour rendre une fraction irréductible en une seule étape, on divise son numérateur et son dénominateur par leur PGCD.
Exemple à traiter : Les nombres 391 et 667 sont-ils premiers entre eux ? Rends irréductible la fraction .
Erreurs fréquentes
⚠ Garder le mauvais nombre
Le PGCD est le dernier reste non nul, pas le dernier quotient.
⚠ Diviser dans le mauvais sens
On divise toujours le diviseur précédent par le reste, et non l’inverse.
Exercice d’application
Calcule par l’algorithme d’Euclide.
Les nombres 525 et 352 sont-ils premiers entre eux ? Justifie.
Rends irréductible la fraction .
Une salle rectangulaire mesure 8,64 m sur 6,48 m. On veut la paver avec des dalles carrées identiques, les plus grandes possible, sans découpe. Quel est le côté d’une dalle, en cm ?
www.ndolomath.com
p3
Cours de Mathématiques : « PGCD : algorithme d’Euclide », proposé par ndolomathndolomath
À retenir
Algorithme d’Euclide : on enchaîne les divisions euclidiennes (diviseur ÷ reste) ; le PGCD est le dernier reste non nul. Deux nombres sont premiers entre eux si leur PGCD vaut 1.