On sait que pour a entier relatif, l'ensemble des multiples de a est l'ensemble
aZ = {...., -3a, -2a , -a, 0 , a , 2a , 3a ,....}
Cet ensemble est stable pour l'addition et la multiplication, c'est à dire que la somme et le produit d'éléments de aZ sont des éléments de aZ
De plus, si n appartient à aZ et si m est un entier relatif quelconque alors (nm) appartient à aZ . 
|a| est le plus petit élément non nul de aZ.

Diviseurs commun à a et b:
Dire que d est un diviseur de a revient à dire qu'il existe k dans Z tel que a =k.d.
Ceci ne signifie rien d'autre que a dZ.
Si a et b sont deux entiers relatifs, les diviseurs communs à a et à b sont donc les entiers d tels que a et b dZ.
Par la suite, on notera D(a , b) l'ensemble des diviseurs commun à a et b.
Deux cas peuvent alors se présenter:
  1 : les seuls diviseurs communs à a et b sont 1 et -1, ce qui signifie qu'il n'existe
      qu'un seul sous-ensemble de Z de la forme dZ contenant a et b, et ce sous
      ensemble est Z lui-même.
  2: a et b possèdent un diviseur commun autre que -1 et 1.
Dans le premier cas, a et b sont dits premiers entres eux.
D'après la décomposition en facteurs premiers, on peut alors dire:

Propriété 1:
a et b sont premiers entre eux si et seulement si pour tout p  entier premier,
" si a est divisible par p alors b n'est pas divisible par p" .
Ou encore:
a et b n'ont aucun diviseur premier en commun.
Par exemple:
a = 2*3*5*7   et  b = 121 = 11² n'ont aucun diviseur en commun donc ils sont premiers entre eux.

Dans le cas général, l'ensemble des diviseurs communs à a et b est un ensemble fini car tous les diviseurs communs d sont tels que |d| inférieurs à |a| et à |b|.

Cet ensemble posséde donc un plus grand élément.
On appelle Plus Grand Commun Diviseur de a et b cet élémént:
Notation: PGCD(a , b )
On peut remarquer que cette définition conduit à PGCD(a,0) = a , pour tout a entier relatif.
Remarquons aussi que dire que a et b sont premiers entre eux se traduit par :
PGCD(a , b ) = 1. 

Propriété 2:
Les entiers k et k ' tels que
a = k.PGCD(a,b) et b = k ' .PGCD(a,b)
sont premiers entre eux.
Cela se voit si on utilise la défintion même du PGCD.
Si k et k' ont un diviseur en commun n > 0 , alors on a écrire qu'il existe K et K' tels que k = nK et k ' = nK'  donc tels que
                       a = n .K . PGCD(a,b) et b = n.K'.PGCD(a,b).
Donc nPGCD(a,b) est un diviseur > 0 de a et de b.
Comme, par défintion, PGCD(a,b) est le plus grand des diviseurs > 0 , on a déduit que n = 1 et que k et k ' n'admettent donc aucun diviseur commun > 0 à part 1,
ils sont donc bien premiers entre eux.

Lien entre PGCD(a ,b) et Division Euclidienne
Remarquons que si deux couples d'entiers (a , b) et (c , d) ont même ensemble de diviseurs communs alors ils aussi même PGCD.
Autrement dit:  D( a , b ) = D( c , d ) PGCD(a,b) = PGCD(c,d).
Or, si on effectue la division euclidienne de b par a, on obtient :
b = Q.a + R, où R est compris entre 0 et |a|-1.
On remarque alors que tout diviseur commun à  a et b doit aussi diviser R  et que tout diviseur commun à a et R doit aussi diviser b.

On a donc D(a , b) = D( a , R ). Donc PGCD(a,b) = PGCD(a,R).

D'où
Propriété 3:
Pour tout couple d'entiers relatifs, on a : PGCD(a,b) = PGCD(a,R)
où R est le reste de la division euclidienne de b par a.

Cette propriété conduit à un algorithme relativement simple de recherche du PGCD de deux entiers relatifs a et b.
C'est le principe des divisions euclidiennes successives.
Prenons un exemple:
On cherche le PGCD de 123 et 81.
La division euclidienne de 123 par 81 donne : 123 = 1*81 + 42.
Donc, le reste de cette division est R = 42 et on a :
PGCD(123 , 81 ) = PGCD( 81 , 42 ).
La division euclidienne de 81 par 42 donne : 81 = 1*42 + 39.
Donc, le reste de cette division est 63 et on a:
PGCD( 81 , 42 ) = PGCD( 42 , 39 )
Comme 42 = 1*39 + 3 , on a  : PGCD(42 , 39 ) = 3.
On a alors 39 = 13*3. Le reste est R = 0, donc  : PGCD(39 , 3) = PGCD(3 , 0 ) = 3.
On en déduit alors que PGCD(123 , 82 ) = 3.
Par les divisions euclidiennes successives,
le dernier reste non nul obtenu est le PGCD.
 
Cet algorithme se présente de la façon suivante:
 

CONSEQUENCES
Propriété 4:
Il existe deux entiers relatifs U et V tels que  PGCD(a,b) = Ua + Vb.
Cela se voit en utilisant la recherche du PGCD par divisions euclidiennes successives.
Comme PGCD(a,b) = PGCD(a,R) où R est est le reste de la division euclidienne de a par b, et que R = b - Q.a,    R  est une combinaision linéaire de a et b.
Le reste de la division euclidienne de a par R est lui-même une combinaision linéaire de a et de R, donc de a et de b.   etc ...... Jusqu'à ce que l'on obtient le dernier reste non nul qui est le PGCD de a et de b.
Par exemple:
Pour a = 20 et b = 8.
20 = 2*8 + 4   et   8 = 2*4 .  PGCD(20,8) = 4.
Comme 20 = 2*8 + 4   on a    4 = 20 - 2*8 .

Pour a = 100 et b = 36.
On a  : 100 = 2*36 + 28   donc 28 = 100 - 2*36 = a - 2b
On a : 36 = 28 + 8            donc   8 = 36 - 28 = b - (a - 2b) = 3b - a
On a : 28 = 3*8 + 4          donc  4 = 28 - 3*8 = (a - 2b) - 3(3b - a) = 4a - 11b
On a : 8 = 2*4                  donc, le dernier reste non nul est 4.
Le PGCD de 100 et 36 est alors 4.
On a de plus la relation : PGCD(a,b) = Ua + Vb avec   U = 4  et V = -11.
 

Un Autre Algorithme de Recherche du PGCD
Une façon de trouver le PGCD de a et b, repose sur le résultat suivant qui est assez évident si on revient à la définition du PCDG.

PGCD( a , b) = PGCD( b , | b - a| ).

Si on définit alors la suite (U) par les relations:

U ₀ = a  et  U ₁ = b
Pour tout n entier naturel , U _n+2 = |U _n+1  - U _n |

alors on peut démontrer qu'il existe un indice no terme tel que U _no  = 0.
Le terme qui précéde U _no est alors le PGCD de a et b.

La mise en place cet algorithme est très simple:

Donner a et b
LABEL 0
|b - a| c
a b
c a
Si c > 0 alors ALLER en 0
AFFICHER b

Biensur, cet algorithme, peut être assez long à "tourner" si l'écart entre les valeurs initiales a et b est grand.

Lien entre PGCD(a,b) et Decomposition entre Facteurs Premiers
Les entiers naturels a et b admettent chacun une décomposition en facteurs premiers
sous la forme :

Le PGCD(a,b) admet alors pour décomposition en facteur premiers:

Par exemple:
Si a = 7350  et  b = 1645, la décomposition en facteurs premiers de ces deux entiers est :
                        7350 = 2*3* 5² * 7²          et    1645 = 5 * 7 * 47.
Le PGCD de 7350 et 1645 est alors :  PGCD(7350 , 1645 ) = 5 * 7 = 35

Comme conséquence directe de cette propriété, on peut alors énoncer:

Propriété 5:
Deux entiers sont premiers entre eux si et seulement si pour tout nombre premier p,
p intervient dans la décomposition de ces entiers avec un exposant non nul dans au moins un des entiers,
OU ENCORE
si l'exposant de p est non nul dans la décomposition de l'un des entiers, alors l'exposant de p est nul dans la décomposition de l'autre entier.
 

L'ensemble des multiples de a, a étant un entier relatif, est l'ensemble noté aZ.
aZ = {... , -3a , -2a , -a , 0 , a , 2a , 3a , ... }
Pour a et b entiers dans Z, les ensembles aZ et bZ ont au moins un élément en commun qui est | ab |.
L'intersection de ces deux ensembles est donc non vide et n'est pas restreint à 0 si a et b sont non nuls.
Cette intersection n'est rien d'autre que l'ensemble des entiers relatifs qui sont à la fois multiples de a et de b.
aZ   bZ = ensemble des multiples de a et de b.
Si a ou b est nul, alors cet ensemble se réduit à {0}.
Dans les autres cas, il posséde au moins un élément > 0. Donc il posséde un plus petit élément > 0.
Cet élément s'appelle "LE PLUS PETIT COMMUN MULTIPLE " de a et b.
NOTATION : PPCM( a , b ).

Par exemple, pour a =  20 et b = 12, on a :
20Z = { ... , -60 , -40 , -20 , 0 , 20 , 40 , 60 , 80 , 100 , 120 , .... }
12Z = {... , -72 , -60 , -48 , -24 , -12 , 0 , 12 , 24 , 48 , 60 , 72 , .... }
L'intersection de ces deux ensembles est :
20Z 12Z = { ... , -60 , 0 , 60 , .....}
Le PPCM de 20 et 12 est donc 60.

Propriété 1
Un entier relatif m est un multiple commun à a et à b
si et seulement si il est un multiple du PPCM de a et b.
Autrement dit:
aZ   bZ =  PPCM(a , b)Z.
Pour vérifier ce résultat, il suffit d'utiliser le principe de la Division Euclidienne.
Remarquons que si m est un multiple de PPCM(a,b) alors il est aussi un multiple de a et de b.
C'est la réciproque qui est moins évidente:
Soit m un multiple commun à a et à  b  et soit N est le PPCM de a et b.
Si m = Q.N + R  est la division euclidienne de m par N, on a :
                                0 < R < N      ou encore 0 < m - Q.N < N.   
Or, (m - Q.N ) est aussi un multiple de a et b.
Comme il est positif mais que N est le plus petit mutiple commun à et à b, on en déduit que
                   (m - Q.N = R = 0) donc que m est bien un multiple de N.

Conséquences:
-1: Si b est un multiple de a alors PPCM(a,b) = | b |
-2: Pour tout (n , a , b ) triplet de Z , PPCM(na , nb) = |n|PPCM(a,b)

Propriété 2
Si a et b sont deux entiers naturels admettant les décompositions en facteurs premiers
 
Alors le PPCM de a et b admet pour décomposition en facteurs premiesr:

Où les exposants n_i sont définis par :    
                      n_i = Sup(a_i , b_i ) = le plus grand des entiers a_i et b_i

Par exemple:
300 = 2² * 3 * 5²    et    520 = 2³ * 5 * 13
Donc PPCM(300 , 520) = 2³ * 3 * 5² * 13 = 7800

Propriété 3: Lien entre PGCD et PPCM
Pour tout couple (a , b) de Z , on a: PGCD(a , b).PPCM(a , b ) = | ab |