diviseur et PGCD

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 .

Exemples :

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.

Propriétés : 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 de 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 > n , alors on a :
m + n = a×p + a×q ; m — n = a×p — a×q

m + n = a × (p + q) ; m — n = a(p — q)

Diviseurs communs à deux entiers

Définition

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 ….. .

On note : PGCD (12 ; 18) = 6 et PGCD (126 ; 90) = …..

Définition

On dit que deux nombres entiers sont premiers entre eux si 1 est leur seul diviseur commun .

Propriétés

P1 : 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.

P2 : Une fraction est irréductible si son numérateur et son dénominateur sont premiers entre eux .

P3 : 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 .

Exemples :

PGCD (48 ; 15) = 3 donc 48 et 15 ne sont pas premiers entre eux.

PGCD (36 ; 25) = 1 donc 36 et 25 sont premier 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 divisions successives .

Exemples :

429 – 156 = 273                                              35 – 24 = 11
273 – 156 = 117                                              24 – 11 = 13
156 – 117 = 39                                                13 – 11 = 2
117 – 39 = 78                                                  11 – 2 = 9
78 – 39 = 39                                                    9 – 2 =7
39 – 39 = 0                                                      7 – 2 = 5
PGCD (429 ; 156) = 39                                    5 – 2 = 3
                                                                        3 –2 = 1
                                                                        2 – 1 = 1
                                                                        1 – 1 = 0
                                                                        PGCD (35 ; 24) = 1
35 et 24 sont premiers entre eux .


webmaster - à propos - Copyright 2007-2016. Tous droits réservés.