Diviseur de 2 entiers naturels
Soient d et n deux entiers naturels, d non nul. On dit que d est un diviseur de n s’il existe un entier q tel que :
n = d × q.
On dit alors également que :
- n est divisible par d ;
- n est un multiple de d ;
- d divise n.
12 = 3 × 4 :
- 3 est diviseur de 12 ;
- 12 est divisible par 3 ;
- 12 est un multiple de 3 ;
- 3 divise 12.
36 = 9 × 4 :
- 4 est diviseur de 36 ;
- 36 est divisible par 9 ;
- 36 est un multiple de 9 ;
- 9 divise 36.
On dit qu’un nombre entier est un nombre premier s’il n’admet que 2 diviseurs : 1 et lui-même.
2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19 ; etc. sont des nombres premiers.
Remarque : a = 1 × a ; 1 est diviseur de tout nombre entier.
La somme de deux multiples d’un même nombre entier est un multiple de ce nombre entier.
La différence, si elle existe, entre deux multiples d’un même nombre entier est un multiple de ce nombre entier.
En effet, si m et n sont deux multiples d’un nombre entier a tels que m = a × p, n = a × q et m > n, alors on a :
;
.
Diviseurs communs à deux entiers
Soient m et n deux entiers naturels non nuls. On appelle diviseur commun de m et de n un nombre entier qui divise m et n.
PGCD de deux nombres entiers
Parmi tous les diviseurs communs de deux nombres entiers, il y en a un qui est le plus grand. On l’appelle Plus Grand Commun Diviseur et on le note PGCD.
Le plus grand diviseur commun de 12 et 18 est 6 et le plus grand diviseur commun de 126 et 90 est 18.
On note : PGCD (12 ; 18) = 6 et PGCD (126 ; 90) = 18.
On dit que deux nombres entiers sont premiers entre eux si 1 est leur seul diviseur commun.
Deux nombres entiers dont le PGCD est égal à 1 sont premiers entre eux.
Attention !!! Deux nombres premiers entre eux ne sont pas forcément des nombres premiers.
Si une fraction est irréductible, alors son numérateur et son dénominateur sont premiers entre eux.
Soient a et b deux nombres entiers, b ≠ 0. Si a et b sont premiers entre eux, alors la fraction est irréductible.
Conséquence : On rend une fraction irréductible en la simplifiant par le PGCD de son numérateur et de son dénominateur.
PGCD (48 ; 15) = 3 donc 48 et 15 ne sont pas premiers entre eux.
PGCD (36 ; 25) = 1 donc 36 et 25 sont premiers entre eux et la fraction 36/25 est irréductible.
Algorithme de recherche du PGCD de deux nombres entiers
1) Algorithme des différences
On a vu précédemment que, si un nombre entier est un diviseur de deux autres nombres, alors il divise leur différence. Cela est donc vrai également pour leur PGCD. Le principe de cet algorithme est de calculer les différences successives entre des nombres que le PGCD recherché divise, jusqu’à ce que le résultat soit nul. Le PGCD des deux nombres est le dernier résultat non nul obtenu dans les différences successives.
429 – 156 = 273
273 – 156 = 117
156 – 117 = 39
117 – 39 = 78
78 – 39 = 39
39 – 39 = 0
PGCD (429 ; 156) = 39.
35 – 24 = 11
24 – 11 = 13
13 – 11 = 2
11 – 2 = 9
9 – 2 = 7
7 – 2 = 5
5 – 2 = 3
3 – 2 = 1
2 – 1 = 1
1 – 1 = 0
PGCD (35 ; 24) = 1 donc 35 et 24 sont premiers entre eux.