Arithmétique : PGCD et PPCM

📋 Plan du Cours

1. Décomposition en facteurs premiers
2. Algorithme des soustractions
3. Algorithme d’Euclide et propriétés
4. Relation entre PGCD et PPCM

📖 1. Décomposition en facteurs premiers

📝 Points essentiels

• Pour déterminer le PGCD de 900 et 360 par décomposition, on écrit $900=2^2\times3^2\times5^2$ et $360=2^3\times3^2\times5$, puis on retient les facteurs premiers communs avec leurs plus petits exposants.

• La décomposition en facteurs premiers donne $\operatorname{PGCD}(900{,}360)=2^2\times3^2\times5=180$.

📖 2. Algorithme des soustractions

📝 Points essentiels

• Pour deux entiers naturels non nuls a>b, l’algorithme des soustractions remplace successivement le couple (a,b) par (a-b,b) jusqu’à obtenir une différence nulle ; le dernier reste non nul est le PGCD.

💡 Astuce mémo

Soustraire jusqu’à obtenir 0 : le dernier reste non nul donne le PGCD.

📖 3. Algorithme d’Euclide et propriétés

📝 Points essentiels

📌 Si $\operatorname{PGCD}(a,b)=1$, alors a et b sont premiers entre eux et la fraction $\frac{a}{b}$ est irréductible.

• Dans l’algorithme d’Euclide, si r est le reste de la division de a par b avec a>b, on remplace successivement (a,b) par (b,r) jusqu’à obtenir un reste nul ; le dernier reste non nul est le PGCD.