Plus grand commun diviseur

Cours maths 3ème

Plus grand commun diviseur :

Ce cours a pour objectifs de travailler autour des définitions de multiples et diviseurs d’un nombre et d’introduire la notion de PGCD et les algorithmes de recherche du PGCD de deux nombres (algorithme des différences et algorithmes d’Euclide).
► Sommaire cours maths 3ème

      A voir aussi :

► Sommaire par thèmes
► Sommaire par notions
► menu 600 VIDEOS       
 

Diviseurs et multiples



Définitions
:
Pour deux nombres entiers n et d non nuls, d est un diviseur de n signifie qu’il existe un nombre entier q tel que n = q × d.
On dit aussi que n est divisible par d ou que n est un multiple de d.

Remarque :
Si d est un diviseur de n alors le reste de la division euclidienne de n par d est égal à zéro.

Exemples :
7 est un diviseur de 91 car 91 = 7 × 13.
De même, 13 est un diviseur de 91.

Remarque importante :
1 est un diviseur de tout nombre entier.


Applications


1)
324 est divisible par :



2) 1 140 est divisible par :



3) 945 est un multiple de :



4) 523 480 est un multiple de :


Plus grand diviseur commun

Définition :
Un diviseur commun à deux ou plusieurs nombres entiers est un nombre entier qui divise chacun d’eux.

Exemple :
36 = 12 × 3 et 24 = 12 × 2.  Donc 12 est un diviseur commun à 36 et à 24.

Définition :
Si a et b désignent deux nombres entiers, on note PGCD (a ; b) le plus grand des diviseurs positifs à a et b.

Exemple :  Rechercher le PGCD de 24 et 36

La liste des diviseurs de 24 est : 


La liste des diviseurs de 36 est :

24 et 36 ont 6 diviseurs communs : 1 ; 2 ; 3 ; 4 ; 6 et 12

Le plus grand d’entre eux est 12 donc PGCD (24 ; 36) = 12


Problème


Quel est le PGCD de 1 326 et 546 ?

Méthode
: on cherche tous les diviseurs de 1 326 puis tous les diviseurs de 546 et ainsi nous pourrons déterminer le plus grand diviseur commun.

Problème
: la recherche de TOUS les diviseurs d’un nombre entier est souvent longue et fastidieuse.

Solution : nous allons voir des algorithmes de recherche qui nous permettront un travail plus rapide.


Algorithme des différences



Exemple : Déterminer PGCD (1 326 ; 546).

1) Soustraire le plus petit des deux nombres au plus grand :


2) On prend les deux plus petits et on recommence :


3) On continue jusqu’à obtenir un résultat nul :



Le plus grand diviseur est le dernier reste non nul dans la succession des différences de l’algorithme

Ici, PGCD ( 1 326 ; 546) = 78


Algorithme d'Euclide : méthode



  • 1) On effectue la division euclidienne du plus grand des deux nombres par le plus petit.
  • 2) On effectue la division euclidienne du diviseur par le reste de la division précédente, jusqu’à ce que le reste de la division soit égal à zéro.
  • 3) Le PGCD est le dernier reste non nul dans la succession des divisions euclidiennes.



Algorithme d'Euclide : exemple



Exemple : Déterminer PGCD (1 326 ; 546).



Le dernier reste non nul est 78
Donc PGCD ( 1 326 ; 546) = 78.

Remarque
 : On peut schématiser l’algorithme ainsi :
1 326 = 2 × 546 + 234
546 = 2 × 234 + 78
234 = 3 × 78 + 0



Remarque sur le Plus Grand Commun Diviseur



Remarque : Pour déterminer PGCD ( 1 326 ; 546), il a fallut :

- 7 soustractions avec la méthode des différences
- 3 divisions avec l’algorithme d’Euclide.


L’algorithme d’Euclide est la méthode la plus performante pour déterminer le PGCD de deux nombres.
 

         Cours complémentaires :

► Opérations sur les
écritures frctionnaires

► Fractions irréductibles
► Sommaire cours maths 3ème

           A voir aussi :

► Sommaire par thèmes
► Sommaire par notions
  • Une offre 100% satisfait

    Vous résiliez quand vous voulez et sans pénalités jusqu'au 4ème cours inclus

  • Une solution économique

    -50% sur tous nos cours, vous n'avancez plus l'avoir fiscal! Aucun impact sur votre niche fiscale

  • Des cours à partir de 2.80€

    Educastream vous propose toutes les formules pour tous les budgets