Si c divise b et b divise a, alors c divise a.

Exemple : 2 divise 6, 6 divise 12, donc 2 divise 12.

Si d divise a et d divise b, alors d divise toute combinaison linéaire ma + nb (où m et n sont des entiers).

Exemple : 3 divise 12 et 3 divise 18, donc 3 divise 12 + 18 = 30.

Chaque nombre entier positif a un nombre fini de diviseurs positifs.

Exemple : Diviseurs de 20 = {1, 2, 4, 5, 10, 20}

Pour tout entier n > 0, 1 et n sont toujours des diviseurs de n.

On appelle ces diviseurs les diviseurs triviaux de n.

Vérifications : 18 = 1×18 = 2×9 = 3×6

Vérifications : 24 = 1×24 = 2×12 = 3×8 = 4×6

Diviseurs de 18 : {1, 2, 3, 6, 9, 18}

Diviseurs de 24 : {1, 2, 3, 4, 6, 8, 12, 24}

Diviseurs communs : {1, 2, 3, 6}

Le plus grand est 6, c'est le PGCD(18, 24).

1. 1 Trouver tous les diviseurs de chaque nombre
2. 2 Identifier les diviseurs communs
3. 3 Choisir le plus grand diviseur commun

Exemple : Calculons PGCD(15, 25)

• Diviseurs de 15 : {1, 3, 5, 15}
• Diviseurs de 25 : {1, 5, 25}
• Diviseurs communs : {1, 5}
• Le plus grand est 5, donc PGCD(15, 25) = 5

L'algorithme d'Euclide repose sur la propriété : PGCD(a, b) = PGCD(b, a mod b)

Exemple : Calculons PGCD(56, 42)

• 56 = 42 × 1 + 14
• 42 = 14 × 3 + 0
• Donc PGCD(56, 42) = 14

Pour calculer PGCD(a, b) :

1. 1 Décomposer a et b en facteurs premiers
2. 2 Prendre les facteurs communs avec leur plus petit exposant
3. 3 Multiplier ces facteurs

Exemple : PGCD(24, 36)

• 24 = 2³ × 3
• 36 = 2² × 3²
• PGCD(24, 36) = 2² × 3 = 4 × 3 = 12

PGCD(a, b) = PGCD(b, a)

Le PGCD est symétrique par rapport aux deux nombres.

Si b divise a, alors PGCD(a, b) = b

Exemple : PGCD(12, 4) = 4 car 4 divise 12

Pour deux entiers a et b strictement positifs :

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

Exemple : PGCD(12, 18) = 6, donc PPCM(12, 18) = (12 × 18) / 6 = 36

Deux nombres a et b sont dits premiers entre eux si PGCD(a, b) = 1.

Exemples : PGCD(7, 11) = 1, donc 7 et 11 sont premiers entre eux.

PGCD(8, 15) = 1, donc 8 et 15 sont premiers entre eux.

On utilise la propriété : PGCD(a, b) = PGCD(b, r) où r est le reste de la division euclidienne de a par b.

On répète ce processus jusqu'à obtenir un reste nul.

1. 1 168 = 70 × 2 + 28, donc PGCD(168, 70) = PGCD(70, 28)
2. 2 70 = 28 × 2 + 14, donc PGCD(70, 28) = PGCD(28, 14)
3. 3 28 = 14 × 2 + 0, donc PGCD(28, 14) = 14

Donc PGCD(168, 70) = 14.

Il existe des entiers u et v tels que :

Cette identité est utile pour résoudre certaines équations diophantiennes.

Pour simplifier une fraction, on divise le numérateur et le dénominateur par leur PGCD.

Exemple : Simplifions \( \frac{24}{36} \)

• PGCD(24, 36) = 12
• \( \frac{24}{36} = \frac{24 \div 12}{36 \div 12} = \frac{2}{3} \)

On veut carreler une surface rectangulaire de dimensions 24 cm × 36 cm avec des carreaux carrés de la plus grande taille possible sans découpe.

La taille du carreau est PGCD(24, 36) = 12 cm.

On utilisera donc des carreaux de 12 cm × 12 cm.

• Cryptographie (algorithme RSA)
• Calculs en arithmétique modulaire
• Algorithmes de compression
• Génération de nombres pseudo-aléatoires

1. PGCD(20, 30) : 20 = 2² × 5, 30 = 2 × 3 × 5 → PGCD = 2 × 5 = 10
2. PGCD(35, 49) : 35 = 5 × 7, 49 = 7² → PGCD = 7
3. PGCD(48, 60) : 48 = 2⁴ × 3, 60 = 2² × 3 × 5 → PGCD = 2² × 3 = 12
4. PGCD(17, 19) : 17 et 19 sont premiers → PGCD = 1

On cherche PGCD(36, 24) :

• 36 = 2² × 3²
• 24 = 2³ × 3
• PGCD(36, 24) = 2² × 3 = 12

Dimension de chaque carré : 12 cm × 12 cm

Nombre de carrés : (36 ÷ 12) × (24 ÷ 12) = 3 × 2 = 6 carrés

1. 1 Décomposer chaque nombre en facteurs premiers
2. 2 Identifier les facteurs communs
3. 3 Prendre chaque facteur commun avec son plus petit exposant
4. 4 Multiplier ces facteurs pour obtenir le PGCD

• Utiliser l'algorithme d'Euclide pour les grands nombres
• Si un nombre divise l'autre : PGCD = le plus petit nombre
• Si les nombres sont premiers entre eux : PGCD = 1
• Vérifier le résultat en s'assurant qu'il divise les deux nombres

• 1 Confondre PGCD et PPCM : le PGCD est le plus grand diviseur commun, pas le plus petit multiple
• 2 Ne pas prendre les exposants les plus petits dans la décomposition en facteurs premiers
• 3 Oublier que le PGCD est toujours ≤ au plus petit des deux nombres
• 4 Ne pas vérifier que le résultat divise les deux nombres

• PGCD(6, 12) ≠ 12 mais 6 (car 6 divise 12)
• PGCD(7, 14) = 7 (le plus petit nombre car l'un divise l'autre)
• PGCD(5, 7) = 1 (car 5 et 7 sont premiers entre eux)

b est diviseur de a si il existe un entier k tel que a = b × k

Le PGCD de deux nombres est le plus grand entier qui divise ces deux nombres

• Liste des diviseurs (pour petits nombres)
• Algorithme d'Euclide (méthode efficace)
• Décomposition en facteurs premiers (méthode générale)

• PGCD(a, b) × PPCM(a, b) = a × b
• PGCD(a, ka) = PGCD(a, k) (si k est entier positif)
• PGCD(a, b) = 1 si a et b sont premiers entre eux