Définitions

Toutes les propositions enoncées ici seront démontrées ultérieurement  dans le chapitre consacré aux entiers relatifs.
Si m et n désignent deux entiers naturels, les 'diviseurs communs' à m et n sont les nombres qui divisent m et n simultanément.
Si D(x) désigne l'ensemble des diviseurs de x. Les diviseurs communs à m et n sont les éléments de l'intersection D(m) ∩ D(n).
Vous pouvez générer maintenant quelques exemples:
Donner deux entiers 0 < m,n ≤ 100000   m: n:
Diviseurs communs à m et n:
Message d'erreur éventuel:
Cette définition engendre quelques remarques.
La dernière remarque nous permet de poser la définition suivante:
Si m et n désignent des entiers naturels non nuls, on appelle 'PGCD' de m et n (notation pgcd(m,n)) le plus grand diviseur commun à m et n.
Vous pouvez maintenant générer quelques exemples:
Donner deux entiers 0 <  m,n ≤ 100000   m: n:
PGCD de m et n:
Message d'erreur éventuel:

Cette notion a de l'importance dans de nombreux problèmes d'arithmétique liés à la périodicité  mais aussi pour le problème très simple de la simplification des fractions (voir ensemble ℚ ).

Remarquons qu'une conséquence théorème d'unicité du paragraphe précédent consacré à la décomposition en facteurs premiers est la suivante:
Les diviseurs de n sont exactement les nombres dont la décomposition ne fait apparaître que les facteurs premiers de n avec un exposant inférieur ou égal à celui avec lequel ils apparaissent dans la décomposition de n.
A partir de la décomposition de n nous avons donc une caractérisation explicite de l'ensemble des diviseurs de n.
Si  n = p 1 r 1 p 2 r 2 ..... p k r k Alors D(n)={ m ∈ ℕ | ∃ (s1 ,s2 ,...,sk ) ∈ ℕk | (∀ i  0 ≤ i ≤ k  0 ≤ si ≤ ri )  ∧  m = p 1 s 1 p 2 s 2 ..... p k s k }

Cette caractérisation nous donne une formule permettant le calcul du PGCD de deux nombres à partir de leurs décompositions respectives.
Pour obtenir  pgcd(m,n) il faut:
Exemple: le pgcd de 23 32 54 71 et 33 51 111 est 32 51

Conséquence importante:
Les diviseurs communs à m et n sont exactement les diviseurs de leur PGCD.
Et nous avons aussi:
Si n est un multiple de m alors pgcd(m,n)=m.

Généralisation

La notion de pgcd s'étend à des ensembles finis de nombres avec une propriété d'associativité.
pgcd(m,n,r) = pgcd(m,pgcd(n,r))

Algorithme d'Euclide

Signalons encore, pour trouver lePGCD de deux nombres m et n, l'algorithme d'Euclide .
Cet algorithme est  fondé sur le fait que si d divise m et n alors d divise aussi le reste de la division de m par n.
Supposons donc que m > n on a alors:
pgcd(m,n)=pgcd(n,r) où r est le reste de la division de m par n.
L'algorithme d'Euclide s'arrête dès qu'un des deux nombres est un multiple de l'autre, et cela arrive forcément parce que le plus petit des deux entiers forme une suite décroissante strictement, donc à la limite (si on n'a pas trouvé de couple où un nombre est un multiple de l'autre) il finira avec la valeur 1.

Vous pouvez voir avec ce programme comment fonctionne cet algorithme.
Donner deux entiers 0 <  m,n ≤ 100000   m: n:
Appels récursifs d'Euclide:
Message d'erreur éventuel:

Café Python

Ce programme donne deux formes de l'algorithme d'Euclide.