Divisibilité et arithmétique : PGCD et algorithmes associés

I. Notions de divisibilité

Soient \(a\) et \(b\) deux entiers. On dit que \(a\) est divisible par \(b\) si il existe un entier \(k\) tel que :

Divisibilité : \(b \mid a \) si et seulement si \(a= b imes k\), avec \(k \in \mathbb{Z}\).

Exemples :

• \(12 \mid 36\) car \(36 = 12 imes 3\).
• \(5 mid 14\) car il n'existe pas d'entier \(k\) tel que \(14 = 5 imes k\).

II. Le plus grand commun diviseur (PGCD)

Le PGCD de deux entiers non nuls \(a\) et \(b\), noté \( ext{pgcd}(a, b)\), est le plus grand entier qui divise à la fois \(a\) et \(b\).

Exemple :
Pour \(a=36\) et \(b=24\), \( ext{pgcd}(36,24) = 12\).

III. L'algorithme d'Euclide

C'est un procédé efficace pour calculer le PGCD :

1. On divise \(a\) par \(b\), on note le reste \(r\) :
   \(a = b imes q + r\) avec \(0 \leq r < b\).
2. Si \(r=0\), alors \( ext{pgcd}(a,b) = b\).
3. Sinon, on remplace \(a\) par \(b\) et \(b\) par \(r\), puis on recommence le processus.

Ce processus se répète jusqu'à obtenir un reste nul. Le dernier divisor non nul est le PGCD.

IV. Exemple de calcul avec l'algorithme d'Euclide

Calculons \( ext{pgcd}(252,105)\) :

• 252 ÷ 105 = 2, reste 42 (
  \(252 = 105 imes 2 + 42\)).
• 105 ÷ 42 = 2, reste 21 (
  \(105=42 imes 2 + 21\)).
• 42 ÷ 21 = 2, reste 0 (
  \(42=21 imes 2 + 0\)).

Le dernier diviseur non nul est 21, donc \( ext{pgcd}(252,105) = 21\).

V. La propriété fondamentale

Le PGCD de deux nombres peut s'exprimer avec la multiplication de leurs facteurs premiers communs :

Si \(a = p_1^{a_1} p_2^{a_2} \dots p_n^{a_n}\) and \(b = p_1^{b_1} p_2^{b_2} \dots p_n^{b_n}\), alors :

\[ ext{pgcd}(a, b) = p_1^{\min(a_1, b_1)} p_2^{\min(a_2, b_2)} \dots p_n^{\min(a_n, b_n)}\]

VI. Conclusion

LePGCD est un outil fondamental en arithmétique pour analyser la divisibilité, simplifier des fractions et résoudre des équations. L'algorithme d'Euclide permet de calculer rapidement le PGCD de deux nombres, même très grands.