Objectifs

• Comprendre la définition du PGCD et des entiers premiers entre eux.
• Maîtriser l'algorithme d'Euclide pour calculer le PGCD.
• Apprendre l'algorithme étendu pour obtenir les coefficients de Bézout.
• Savoir appliquer ces outils (tester la coprimalité, résoudre certaines équations).

Notions clés

PGCD (plus grand commun diviseur)

Définition :

Si \(a\) et \(b\) sont deux entiers non nuls, le PGCD de \(a\) et \(b\) est le plus grand entier positif qui divise à la fois \(a\) et \(b\). On le note \(\gcd(a,b)\).

Divisibilité et nombres premiers entre eux

On dit que \(a\) et \(b\) sont premiers entre eux si \(\gcd(a,b)=1\).

Relation de Bézout

Théorème : il existe des entiers \(u,v\) tels que \(u a + v b = \gcd(a,b)\). Ces \(u,v\) sont appelés coefficients de Bézout.

Algorithme d'Euclide (calcul du PGCD)

Principe : répéter les divisions euclidiennes jusqu'à obtenir un reste nul. Le dernier reste non nul est le PGCD.

Diagramme (flux de calcul) :

flowchart LR
  A[Début : a,b] --> B{b = 0 ?}
  B -- oui --> C[PGCD = a]
  B -- non --> D[Calculer r = a mod b]
  D --> E[a ← b\na ← b\nb ← r]
  E --> B

Algorithme formel :

1. Écrire la division : \(a = q_1 b + r_1\) avec \(0 \le r_1 < |b|\).
2. Remplacer \(a\) par \(b\) et \(b\) par \(r_1\), répéter jusqu'à obtenir un reste nul.
3. Le PGCD est le dernier reste non nul.

Exemple résolu — cherche d'abord :

Calcul écrit (aligné) :

On a :

Algorithme étendu et coefficients de Bézout

Avec l'algorithme d'Euclide, on peut remonter les divisions pour écrire le PGCD comme une combinaison linéaire des nombres de départ. C'est l'algorithme étendu.

Exemple résolu — cherche d'abord :

Calcul aligné :

Applications rapides

• Simplifier une fraction : \(\dfrac{a}{b}=\dfrac{a/\gcd(a,b)}{b/\gcd(a,b)}\).
• Tester si une équation \(ax+by=c\) a des solutions entières : il faut que \(\gcd(a,b)\) divise \(c\).
• Calculer le PPCM : \(\mathrm{lcm}(a,b)=\dfrac{|a\,b|}{\gcd(a,b)}\).

Erreurs fréquentes

• Confondre le rôle des restes et des quotients dans l'algorithme : c'est le dernier reste non nul qui est le PGCD.
• Oublier que le PGCD est pris positif (on retient toujours la valeur absolue si nécessaire).
• Penser que la relation de Bézout donne des coefficients uniques — ils ne sont pas uniques, on peut ajouter des multiples appropriés.

Récapitulatif

Pour calculer \(\gcd(a,b)\) : utiliser l'algorithme d'Euclide (divisions successives). Pour obtenir des \(u,v\) tels que \(u a + v b = \gcd(a,b)\), remonter les égalités (algorithme étendu).

Cartes mémo