Un article détaille la définition du PGCD de deux nombres entiers. Voici quelques propriétés qui sont à la base d’algorithmes de recherche de ce PGCD : l’algorithme des différences et l’algorithme d’Euclide qui en est une amélioration.

Théorème

Pour tout nombre $a$ et tout nombre $b$, entiers non nuls avec $a > b$,
– PGCD($a ;a$) = $a$
– PGCD($a ;0$) = $a$
– PGCD($a ;b$) = PGCD($b ;a-b$)

Démonstration

– Soit un nombre entier $a$ non nul,
les diviseurs de $a$ et de $a$ sont bien sûr les diviseurs de $a$
or, $a$ est le plus grand de ses diviseurs
donc PGCD($a ;a$) = $a$

– Soit un nombre entier $a$ non nul,
les diviseurs de ${0}$ sont tous les nombres entiers non nuls
donc les diviseurs communs de ${0}$ et de $a$ sont les diviseurs de $a$ ; $a$ étant le plus grand de ses diviseurs, on a donc PGCD($a ;0$) = $a$

– Soient $a$ et $b$ deux nombres entiers non nuls tels que $a>b$
considérons un diviseur commun de $a$ et de $b$.
Le schéma suivant montre, à partir d’un exemple, comment ce diviseur commun partage $a$ et $b$ :

Pour réaliser ce schéma, nous avons pris les nombres 108 et 60 et 6 qui est un des diviseurs communs de ces deux nombres. Des schémas similaires peuvent être réalisés pour n’importe quels autres nombres entiers non nuls.

Ce schéma nous montre que tout diviseur commun de $a$ et de $b$ est aussi un diviseur commun de $a-b$ : c’est une unité commune aux deux segments qui représentent $a$ et $b$, on retrouve cette unité dans leur différence.

Plus précisément, avec 6 qui est un diviseur commun de 108 et de 60, on a 108 = 6à—18 et 60 = 6à—10
or, 108−60 = 6à—18 − 6à—10 = 6à—(18−10) en utilisant la distributivité
donc 6 est un diviseur de 108−60.

In versement, le même schéma nous montre que tout diviseur commun de $b$ et de $a-b$ est un diviseur de $a$ puisque $a$ est la somme de $b$ et de $a-b$ ; l’unité qui mesure à la fois $b$ et $a-b$ mesure leur somme qui est $a$.

Plus précisément, avec 12 qui est un diviseur commun de 60 et de 48 (la différence entre 108 et 60), on a 60 = 12à—5 et 48 = 12à—4
or, 108 = 60 + 48 = 12à—5 + 12à—4 = 12à—(5 + 4) en utilisant encore la distributivité
donc 12 est un diviseur de 108.

Ainsi, les diviseurs communs de $a$ et de $b$ sont les diviseurs communs de $b$ et de $a-b$ : ces deux ensembles de diviseurs étant identiques, ils ont le même plus grand élément

donc PGCD($a ;b$) = PGCD($b ;a-b$).CQFD