Le plus grand diviseur commun (PGCD) de deux nombres entiers $a$ et $b$ est le plus grand nombre entier qui divise simultanément $a$ et $b$.

• Le PGCD de $a$ et de $b$ est noté $\text{PGCD(a;b)}$.

Les diviseurs de $45$ sont $1$ ; $3$, $5$ ; $9$ ; $15$ et $45$.
Les diviseurs de $60$ sont $1$ ; $2$ ; $3$ ; $4$ ; $5$ ; $6$ ; $10$ ; $15$ ; $20$ ; $30$ et $60$.

Donc $\text{PGCD}(45;60)=15$.

Soient $a$, $b$ et $c$ des entiers naturels. On a les propriétés suivantes :

1. $\text{PGCD}(a;0)=a$ ;
2. $\text{PGCD}(a;1)=1$ ;
3. $\text{PGCD}(ac\ ;bc)=c \times \text{PGCD}(a;b)$ ;
4. Si $a \mid b$, alors $\text{PGCD}(a;b)=a$.

Soient $a$ et $b$ deux entiers naturels non nuls. Soit $r$ le reste de la division euclidienne de $a$ par $b$. Alors :

•  $\text{PGCD}(a;b)=\text{PGCD}(b;r)$.

Pour trouver $\text{PGCD}(510;238)$ :

• on effectue la division euclidienne de $510$ par $238$ :
  • $510 = 238 \times 1 + 272$.
  • Donc $\text{PGCD}(510;238)=\text{PGCD}(238;272)=\text{PGCD}(272;238)$.
• On réitère l’opération :
  • $272 =238 \times 1 + 34$
  • $238=34 \times 7+0$
  • Donc $\text{PGCD}(510;238)=\text{PGCD}(272;238)=\text{PGCD}(238;34)$.
  • Or $238$ divise $34$, donc d’après 4), $\text{PGCD}(238;34)=34$.
• Ainsi, $\text{PGCD}(510;238)=34$.

Deux nombres entiers naturels sont dits premiers entre eux si leur PGCD vaut $1$.

Soient $a$ et $b$ deux entiers naturels et $c= \text{PGCD}(a;b)$.
Il existe $\alpha$ et $\beta$ entiers relatifs tels que :

• $\alpha a + \beta b = c$.

$a$ et $b$ sont premiers entre eux si et seulement s’il existe deux entiers relatifs $\alpha$ et $\beta$ tels que :

• $\alpha a+\beta b =1$.

Démontrons que pour entier naturel $n$, $2n+1$ et $9n+4$ sont premiers entre eux.

• On cherche $a$ et $b$ tels que $a(2n+1) + b(9n+4)=1$, ce qui s'écrit aussi $(2a+9b)n + (a+4b)=1$.
• $2a+9b=0$ car le terme de droite est indépendant de $n$. 
• On peut choisir $a=9$, $b=-2$ (car on voit facilement que $2\times 9+9\times (-2)=0$).
• On a alors $a(2n+1) + b(9n+4)=1$.
• Donc la proposition est bien vérifiée.

Soient trois entiers naturels $a$, $b$, $c$ tels que $a \mid bc$ et $a$, $b$ premiers entre eux.

• Alors $a \mid c$.

Le théorème de Gauss permet de résoudre des équations diophantiennes, c'est-à-dire de la forme : $ax + by =c$. 
(voir les exercices À savoir refaire).