3- Le plus grand diviseur commun de deux entiers

3.1 Diviseurs d’un nombre

3.1.1 Exemples

1) On détermine le quotient et le reste de la division de 30 par 7.
30=7×4+2 donc le quotient q=4 et le reste r=2 (r≠0)
on dit alors que le nombre 7 ne divise pas 30 et on écrit 7∤30.

2) 52=4×13
on dit alors 4 divise 52 car le reste r=0
et on écrit 4|52 et on a aussi (13|52).

3.1.2 Définition

Soient n et d deux entiers naturels non nuls.
On dit que d est un diviseur de n s'il existe un entier naturel k tel que n=kd.

Remarque Si n=kd on dit aussi que k est un diviseur de n et n est un multiple de m et k.

3.2 Le plus grand diviseur commun de deux nombres

3.2.1 Définition

Soient n et m deux entiers naturels non nuls.
Le plus grand entier qui divise n et m à la fois est appelé le plus grand commun diviseur de n et m et est noté pgcd(n;m) ou n∧m.

3.2.2 Exemples

1) Les diviseurs de 21 sont 1; 3; 7; 21
et les diviseurs de 45 sont 1; 3; 5; 9; 15 et 45.

Les diviseurs commun de 21 et 45 sont donc 1 et 3 ainsi 18∧21=3.
2) Les diviseurs de 15 sont 1; 3; 5 et 15.
et les diviseurs de 28 sont 1; 2; 4; 7; 14 et 28.
Le seul diviseur commun de 15 et 28 est 1
on dit que 15 et 14 sont premiers entre eux et on écrit 15∧28=1
Remarque
1) 1 est un diviseur de tout entier naturel.
2) Tout entier naturel non nul est divisible par lui même.