Mathématiques • Seconde

Diviseurs et PGCD
Nombres Entiers

Infographie & Exercices
\( a|b \Leftrightarrow \exists q \in \mathbb{N}, b = a \times q \)
Division exacte
\( PGCD(a,b) = \max\{d \in \mathbb{N}^* | d|a \text{ et } d|b\} \)
Plus Grand Commun Diviseur
Algorithme d'Euclide
\(PGCD(a,b) = PGCD(b, r)\)
où \(r\) est le reste de la division euclidienne de \(a\) par \(b\)
Nombres Premiers entre eux
\(PGCD(a,b) = 1\)
Les seuls diviseurs communs sont 1 et -1
🎯
Définition : Un nombre entier naturel \(a\) est un diviseur de \(b\) si \(b\) est divisible par \(a\) sans reste.
🔢
Notation : \(a|b\) signifie "a divise b" ou "a est un diviseur de b".
📋
Méthode : Pour trouver les diviseurs d'un nombre, on teste les divisions successives jusqu'à sa racine carrée.
🔄
Algorithme d'Euclide : Méthode efficace pour calculer le PGCD de deux nombres.
💡
Conseil : Les diviseurs d'un nombre vont toujours par paires : si \(d\) divise \(n\), alors \(\frac{n}{d}\) aussi
🔍
Attention : Le PGCD est toujours positif et au maximum égal au plus petit des deux nombres
⚡
Astuce : Utiliser la décomposition en facteurs premiers pour trouver rapidement les diviseurs
🎯
Objectif : Le PGCD permet de simplifier des fractions et résoudre des problèmes d'arithmétique
Exercice 1
Trouver tous les diviseurs de 24
Exercice 2
Calculer PGCD(36, 24) avec l'algorithme d'Euclide
Exercice 3
Trouver PGCD(56, 42) par la méthode des diviseurs
Exercice 4
Simplifier la fraction 60/48
Exercice 5
Trouver tous les diviseurs de 30
Exercice 6
Calculer PGCD(84, 35) avec Euclide
Exercice 7
Trouver PGCD(100, 75) par Euclide
Exercice 8
Simplifier 84/126
Exercice 9
Trouver PGCD(96, 72) par Euclide
Exercice 10
Déterminer si 15 et 28 sont premiers entre eux
Corrigé : Exercices 1 à 5
1 Trouver tous les diviseurs de 24
Définition :

Diviseur : Un entier a est un diviseur de b si b = a × q avec q ∈ ℕ.

Méthode de recherche des diviseurs :
  1. Tester les divisions successives de 1 à √24 ≈ 4.9
  2. Si d divise 24, alors 24/d est aussi un diviseur
  3. Lister les paires de diviseurs
Étape 1 : Calcul de √24

√24 ≈ 4.9, donc on teste de 1 à 4

Étape 2 : Test des divisions
  • 24 ÷ 1 = 24 → 1 et 24 sont diviseurs
  • 24 ÷ 2 = 12 → 2 et 12 sont diviseurs
  • 24 ÷ 3 = 8 → 3 et 8 sont diviseurs
  • 24 ÷ 4 = 6 → 4 et 6 sont diviseurs
Étape 3 : Vérification

On continue jusqu'à √24, soit environ 4.9

Testons 5 : 24 ÷ 5 = 4.8 → non entier, donc 5 n'est pas diviseur

Réponse finale :

Les diviseurs de 24 sont : {1, 2, 3, 4, 6, 8, 12, 24}

Règles appliquées :

• Propriété : Si d divise n, alors n/d divise aussi n

• Efficacité : On ne teste que jusqu'à √n

• Vérification : 1 × 24 = 24, 2 × 12 = 24, etc.

2 Calculer PGCD(36, 24) avec l'algorithme d'Euclide
Algorithme d'Euclide :

PGCD(a,b) = PGCD(b, r) où r est le reste de la division euclidienne de a par b.

Étapes de l'algorithme d'Euclide :
1
Faire la division euclidienne de a par b
2
Remplacer a par b et b par le reste r
3
Répéter jusqu'à ce que le reste soit 0
4
Le dernier diviseur non nul est le PGCD
Étape 1 : Division de 36 par 24

36 = 24 × 1 + 12

(car 24 × 1 = 24, et 36 - 24 = 12)

Donc PGCD(36, 24) = PGCD(24, 12)

Étape 2 : Division de 24 par 12

24 = 12 × 2 + 0

(car 12 × 2 = 24, et 24 - 24 = 0)

Étape 3 : Conclusion

Le reste est 0, donc le PGCD est le dernier diviseur non nul : 12

Réponse finale :

PGCD(36, 24) = 12

Règles appliquées :

• Algorithme d'Euclide : PGCD(a,b) = PGCD(b, r)

• Terminaison : L'algorithme s'arrête quand le reste est 0

• Résultat : Le PGCD est le dernier diviseur non nul

• Vérification : 12 divise 36 (36 = 12 × 3) et 24 (24 = 12 × 2)

3 Trouver PGCD(56, 42) par la méthode des diviseurs
Définition du PGCD :

PGCD(a,b) est le plus grand entier qui divise à la fois a et b.

Méthode des diviseurs :
  1. Trouver tous les diviseurs de a
  2. Trouver tous les diviseurs de b
  3. Identifier les diviseurs communs
  4. Choisir le plus grand (PGCD)
Étape 1 : Trouver les diviseurs de 56

√56 ≈ 7.5, donc on teste de 1 à 7

  • 56 ÷ 1 = 56 → diviseurs : 1, 56
  • 56 ÷ 2 = 28 → diviseurs : 2, 28
  • 56 ÷ 4 = 14 → diviseurs : 4, 14
  • 56 ÷ 7 = 8 → diviseurs : 7, 8

Diviseurs de 56 : {1, 2, 4, 7, 8, 14, 28, 56}

Étape 2 : Trouver les diviseurs de 42

√42 ≈ 6.5, donc on teste de 1 à 6

  • 42 ÷ 1 = 42 → diviseurs : 1, 42
  • 42 ÷ 2 = 21 → diviseurs : 2, 21
  • 42 ÷ 3 = 14 → diviseurs : 3, 14
  • 42 ÷ 6 = 7 → diviseurs : 6, 7

Diviseurs de 42 : {1, 2, 3, 6, 7, 14, 21, 42}

Étape 3 : Trouver les diviseurs communs

Intersection de {1, 2, 4, 7, 8, 14, 28, 56} et {1, 2, 3, 6, 7, 14, 21, 42}

Diviseurs communs : {1, 2, 7, 14}

Étape 4 : Trouver le plus grand

Le plus grand diviseur commun est 14

Réponse finale :

PGCD(56, 42) = 14

Règles appliquées :

• Définition : PGCD(a,b) est le plus grand diviseur commun

• Effet : 14 divise 56 (56 = 14 × 4) et 42 (42 = 14 × 3)

• Comparaison : La méthode des diviseurs est plus longue mais plus intuitive

4 Simplifier la fraction 60/48
Fraction irréductible :

Une fraction est irréductible si le numérateur et le dénominateur sont premiers entre eux (PGCD = 1).

Méthode de simplification :
  1. Calculer PGCD(numérateur, dénominateur)
  2. Diviser le numérateur et le dénominateur par leur PGCD
  3. La fraction obtenue est irréductible
Étape 1 : Calculer PGCD(60, 48) avec Euclide

60 = 48 × 1 + 12

48 = 12 × 4 + 0

Donc PGCD(60, 48) = 12

Étape 2 : Diviser numérateur et dénominateur par 12

Numérateur : 60 ÷ 12 = 5

Dénominateur : 48 ÷ 12 = 4

Étape 3 : Écrire la fraction simplifiée

60/48 = 5/4

Étape 4 : Vérifier que la fraction est irréductible

PGCD(5, 4) = 1 car 5 est premier et 4 = 2², donc ils n'ont pas de facteurs communs

Réponse finale :

60/48 = 5/4

Règles appliquées :

• Simplification : Diviser par le PGCD rend la fraction irréductible

• Application : Utiliser l'algorithme d'Euclide pour trouver rapidement le PGCD

• Vérification : PGCD(5, 4) = 1 donc 5/4 est irréductible

5 Trouver tous les diviseurs de 30
Ensemble des diviseurs :

L'ensemble des diviseurs d'un nombre n est noté D(n) et contient tous les entiers qui divisent n sans reste.

Méthode systématique :
  1. Calculer √30 ≈ 5.48
  2. Tester les divisions de 1 à 5
  3. Pour chaque diviseur trouvé, inclure son complémentaire
Étape 1 : Calcul de √30

√30 ≈ 5.48, donc on teste de 1 à 5

Étape 2 : Test des divisions
  • 30 ÷ 1 = 30 → diviseurs : 1, 30
  • 30 ÷ 2 = 15 → diviseurs : 2, 15
  • 30 ÷ 3 = 10 → diviseurs : 3, 10
  • 30 ÷ 5 = 6 → diviseurs : 5, 6
Étape 3 : Vérification des autres nombres

Testons 4 : 30 ÷ 4 = 7.5 → non entier, donc 4 n'est pas diviseur

Testons 6 : 30 ÷ 6 = 5 → déjà trouvé avec 5

Étape 4 : Ordonner les diviseurs

On ordonne les diviseurs trouvés : 1, 2, 3, 5, 6, 10, 15, 30

Réponse finale :

Les diviseurs de 30 sont : D(30) = {1, 2, 3, 5, 6, 10, 15, 30}

Règles appliquées :

• Propriété : Les diviseurs vont par paires : si d divise n, alors n/d aussi

• Efficacité : On ne teste que jusqu'à √n

• Vérification : Chaque paire multipliée redonne 30

Corrigé : Exercices 6 à 10
6 Calculer PGCD(84, 35) avec Euclide
Algorithme d'Euclide étendu :

On applique la division euclidienne répétée jusqu'à obtenir un reste nul. Le dernier reste non nul est le PGCD.

Étape 1 : Division de 84 par 35

84 = 35 × 2 + 14

(car 35 × 2 = 70, et 84 - 70 = 14)

Donc PGCD(84, 35) = PGCD(35, 14)

Étape 2 : Division de 35 par 14

35 = 14 × 2 + 7

(car 14 × 2 = 28, et 35 - 28 = 7)

Donc PGCD(35, 14) = PGCD(14, 7)

Étape 3 : Division de 14 par 7

14 = 7 × 2 + 0

(car 7 × 2 = 14, et 14 - 14 = 0)

Étape 4 : Conclusion

Le reste est 0, donc le PGCD est le dernier diviseur non nul : 7

Réponse finale :

PGCD(84, 35) = 7

Règles appliquées :

• Algorithme d'Euclide : PGCD(a,b) = PGCD(b, r)

• Itération : On répète jusqu'à ce que r = 0

• Vérification : 7 divise 84 (84 = 7 × 12) et 35 (35 = 7 × 5)

• Propriété : PGCD(84, 35) = 7 signifie que 84 et 35 ne partagent pas d'autres diviseurs communs que les multiples de 7

7 Trouver PGCD(100, 75) par Euclide
Application de l'algorithme d'Euclide :

On utilise la division euclidienne répétée : a = b × q + r, avec 0 ≤ r < b.

Étape 1 : Division de 100 par 75

100 = 75 × 1 + 25

(car 75 × 1 = 75, et 100 - 75 = 25)

Donc PGCD(100, 75) = PGCD(75, 25)

Étape 2 : Division de 75 par 25

75 = 25 × 3 + 0

(car 25 × 3 = 75, et 75 - 75 = 0)

Étape 3 : Conclusion

Le reste est 0, donc le PGCD est le dernier diviseur non nul : 25

Étape 4 : Vérification

25 divise 100 : 100 ÷ 25 = 4

25 divise 75 : 75 ÷ 25 = 3

Donc 25 est un diviseur commun

Réponse finale :

PGCD(100, 75) = 25

Règles appliquées :

• Division euclidienne : a = b × q + r, avec 0 ≤ r < b

• Algorithme : PGCD(a,b) = PGCD(b,r) jusqu'à r = 0

• Optimisation : L'algorithme d'Euclide est plus rapide que la méthode des diviseurs

8 Simplifier 84/126
Fraction irréductible :

Une fraction est irréductible lorsque le numérateur et le dénominateur sont premiers entre eux (PGCD = 1).

Étape 1 : Calculer PGCD(84, 126) avec Euclide

126 = 84 × 1 + 42

84 = 42 × 2 + 0

Donc PGCD(84, 126) = 42

Étape 2 : Diviser numérateur et dénominateur par 42

Numérateur : 84 ÷ 42 = 2

Dénominateur : 126 ÷ 42 = 3

Étape 3 : Écrire la fraction simplifiée

84/126 = 2/3

Étape 4 : Vérifier que la fraction est irréductible

PGCD(2, 3) = 1 car 2 et 3 sont des nombres premiers distincts

Étape 5 : Vérification finale

2/3 est bien irréductible puisque 2 et 3 n'ont pas de diviseurs communs autres que 1

Réponse finale :

84/126 = 2/3

Règles appliquées :

• Simplification : Diviser par le PGCD(numérateur, dénominateur)

• Irréductibilité : Une fraction est irréductible si PGCD(num, den) = 1

• Application : L'algorithme d'Euclide permet de trouver rapidement le PGCD

9 Trouver PGCD(96, 72) par Euclide
Algorithme d'Euclide itéré :

On applique la division euclidienne successivement : a = b × q + r, puis on remplace (a,b) par (b,r).

Étape 1 : Division de 96 par 72

96 = 72 × 1 + 24

(car 72 × 1 = 72, et 96 - 72 = 24)

Donc PGCD(96, 72) = PGCD(72, 24)

Étape 2 : Division de 72 par 24

72 = 24 × 3 + 0

(car 24 × 3 = 72, et 72 - 72 = 0)

Étape 3 : Conclusion

Le reste est 0, donc le PGCD est le dernier diviseur non nul : 24

Étape 4 : Vérification algébrique

96 = 24 × 4 et 72 = 24 × 3

Donc 24 divise à la fois 96 et 72

Et PGCD(4, 3) = 1, donc 24 est effectivement le plus grand diviseur commun

Réponse finale :

PGCD(96, 72) = 24

Règles appliquées :

• Algorithme d'Euclide : PGCD(a,b) = PGCD(b, r) avec r = a mod b

• Terminaison : L'algorithme s'arrête quand le reste est 0

• Propriété fondamentale : Le PGCD ne change pas lorsqu'on remplace a par b et b par r

10 Déterminer si 15 et 28 sont premiers entre eux
Nombres premiers entre eux :

Deux nombres sont premiers entre eux si leur PGCD = 1, c'est-à-dire s'ils n'ont pas de diviseur commun autre que 1.

Méthode de vérification :
  1. Calculer PGCD(15, 28) avec l'algorithme d'Euclide
  2. Si le résultat est 1, les nombres sont premiers entre eux
  3. Si le résultat est > 1, ils ne le sont pas
Étape 1 : Division de 28 par 15

28 = 15 × 1 + 13

(car 15 × 1 = 15, et 28 - 15 = 13)

Donc PGCD(28, 15) = PGCD(15, 13)

Étape 2 : Division de 15 par 13

15 = 13 × 1 + 2

(car 13 × 1 = 13, et 15 - 13 = 2)

Donc PGCD(15, 13) = PGCD(13, 2)

Étape 3 : Division de 13 par 2

13 = 2 × 6 + 1

(car 2 × 6 = 12, et 13 - 12 = 1)

Donc PGCD(13, 2) = PGCD(2, 1)

Étape 4 : Division de 2 par 1

2 = 1 × 2 + 0

(car 1 × 2 = 2, et 2 - 2 = 0)

Étape 5 : Conclusion

Le reste est 0, donc le PGCD est le dernier diviseur non nul : 1

Comme PGCD(15, 28) = 1, les nombres sont premiers entre eux

Réponse finale :

Oui, 15 et 28 sont premiers entre eux car PGCD(15, 28) = 1

Règles appliquées :

• Définition : a et b sont premiers entre eux ⟺ PGCD(a,b) = 1

• Application : Si deux nombres sont premiers entre eux, on ne peut pas simplifier leur fraction

• Exemple : 15/28 est déjà irréductible car PGCD(15, 28) = 1

Diviseurs, PGCD Nombres entiers : multiples, diviseurs et nombres premiers