Défintion:
Deux entiers a et b sont dits "Premiers entre Eux"
si les seuls diviseurs qu'ils aient en commun sont 1 et -1.
Par exemple, 10 et 21 sont premiers entre eux.
En revanche, 10 et 25 sont tous deux divisibles par 5 donc ils ne sont pas premiers entre eux.
On remarque tout de suite que :

1. Si p est premier, alors pour tout a non-multiple de p, a et p sont premiers entre eux.
2. Deux nombres premiers distincts sont premiers entre eux.
3. Dire que a et b sont premiers entre revient à dire que PGCD(a,b) = 1.
4. Comme PGCD(a,b).PPCM(a,b) = | ab |,
   dire que a et b sont premiers entre eux revient à dire que PPCM(a,b) = | ab |.
5. a et b sont premiers entre eux si et seulement si pour tout p premier, si p est un diviseur de a alors p n'est pas un diviseur de b.

On a vu que qu'il existe U et V dans Z tels que PGCD(a,b) = Ua + Vb. (Voir le rappel)
On en déduit alors le THEOREME de BACHET-BEZOUT:

Théorème de Bachet-Bezout:
Les entiers a et b sont premiers entre eux si et seulement si
il existe u et v dans Z tels que au + bv = 1. C'est l'idendité de Bachet-Bezout
De plus, parmi les couples (u,v) vérifiant l'identité de Bachet-Bezout,
il en existe un tel que | u | < | b |  et  | v | < | a |

La détermination des entiers u et v peut se faire en utilisant l'Algorithme d'Euclide.

Exemples:
 a: Pour les entiers  a = 40  et  b = 21, effectuons le division euclidienne de 21 par 40.
     40 = 1*21 + 19.
     Puis effectuons la division euclidienne de 21 par 19.
     21 = 1*19 + 2,  et enfin la division euclidienne de 19 par 2.
     19 = 9*2 + 1.
     Le PGCD de 40 et 21 est donc 1, ils sont premiers entre eux.
     De plus, on a :
     19 = 40 - 21 = a - b   donc   2 = 21 - 19 = b  - ( a - b) = 2b - a.
     1 = 19 - 9*2  d'où  :   1 = (a - b)  - 9*(2b - a) = 10a - 19b .
     On a donc 40u + 21v = 1 avec u = 10  et   v = -19.

  b: Prenons a = 100    et   b = 121.
     121 = 1*100 + 21    ,     100  =  4*21  +  16   ,   21 = 1*16 + 5  ,  16 = 3*5 + 1
     On a bien PGCD(100,121) = 1  ,  100 et 121 sont premiers entre eux.
     De plus , 21 = b - a  , donc , 16 = a - 4*(b - a) = 5a - 4b
     donc ,  5 = 21 - 16 = (b - a) - (5a - 4b) = 5b - 6a
     d'où ,  1 = 16 - 3*5 = (5a - 4b) - 3*(5b - 6a) = 23a - 19b.
     On a donc 100u + 121v = 1  avec u = 23  et  v = -19.

En utilisant la Décomposition en Facteurs Premiers, on déduit alors

Propriété 2:
a et b étant deux entiers, ils sont premiers entre eux si et seulement si
pour tout nombre premier p, Si l'exposant de p dans la décomposition de a est > 0
Alors l'exposant de p dans la décomposition de b est = 0.

Exemples:
  a: 100 = 2² . 5²   et   121 = 11².   On retrouve que 100 et 121 sont premiers entre eux.
  b: 40 = 2³ . 5     et     21 = 3 . 7    .      40 et 21 sont premieres entre eux.  

Une conséquence directe du Théorème de Bachet-Bezout est le fait que
Si a est premier avec b et c alors a est premier avec (bc).
Effectivement, dire que a et b sont premiers entre eux revient à dire qu'il existe u et v tels que
au +  bv = 1.
De même, a et c sont premiers entre eux revient à dire qu'il existe t et w tels que
at + cw = 1.
En multipliant ces deux égalités, on obtient alors:
(au + bv)(at + cw) = 1.    En développant, on a alors:
a²ut + acuw + abvt + bcvw = 1   ou encore:
a(aut + cuw + bvt) + bc(vw) = 1.
Il existe donc bien U et V dans Z tels que aU + bcV = 1.
Réciproquement:
Si a et bc sont premiers entre eux, il existe u et v dans Z tels que au + bcv = 1.
On a donc, en particulier : au + b(cv) = 1.
a et b sont alors premiers entre eux.

 D'où

Propriété 3:
a est premier avec b et c  si et seulement si a est premier avec (bc).
On en déduit alors, par récurrence:
  a:  a est premier avec un produit d'entiers si et seulement si a est premier avec chacun des       facteurs.
  b: a et b sont premiers entre eux si et seulement si pour tout n et tout m entiers > 0,
       aⁿ  et b^m sont premiers entre eux

Un conséquence directe de ce résultat est :

Théorème de Gauss
Si a n'est pas premier avec bc et s'il est premier avec b alors  a n'est pas premier avec c.
En particulier,
Si a est un diviseur de bc  si a et b sont premiers entre eux alors a est un diviseur de c.

Le  Théorème de Gauss peut se vérifier directement en utilisant Bachet-Bezout.
Supposons que a devise bc et que a et b soient premiers entre eux.
Ces deux hypothèses se traduisent par:
  a: Il existe q dans Z tel que bc = qa
  b: Il existe u et v dans Z tels que au + bv = 1.
On a donc, en multipliant par c.
  acu + bcv = c    ou encore    acu + qav = c   d'où   a(cu + qv) = c.
a est donc bien un diviseur de  c.
 

Supposons maintenant que a soit divisible par b et c et que b et c soient premiers entre eux.
Cela se traduit par:
  a: Il existe q et q' dans Z tels que a = q.b  et   a = q'.c
  b: Il existe u et v dans Z tels que  bu + cv = 1.
En multipliant par a, on obtient alors:
abu + acv = a    d'où     (q'.c)bu + (q.b)cv = a et donc  bc(q'.u + q.v) = a.
a est donc divisible par bc.

D'où:
Propriété 5:
Si a est divisible par b et c et si b et c sont premiers entre eux
Alors a est divisible par bc.

Par exemple:
  a: Un nombre a est divisible par 2 et par 3 si et seulement si a est divisible par 2*6 = 6.
  b: Un nombre a est divisible par 35 si et seulement si a est divisible par 5 et 7.