PGCD de deux entiers

Cette fiche de révision vous propose une synthèse du cours sur le Plus Grand Commun Diviseur (PGCD) de deux entiers et des exemples pour mieux comprendre comment utiliser cet outil. Notre professeur vous propose donc de revoir les propriétés du...

Document rédigé par un prof PGCD de deux entiers

Le contenu du document

Cette fiche de révision vous propose une synthèse du cours sur le Plus Grand Commun Diviseur (PGCD) de deux entiers et des exemples pour mieux comprendre comment utiliser cet outil. Notre professeur vous propose donc de revoir les propriétés du PGCD mais aussi d'effectuer des petits exercices pour vous assurer d'avoir bien compris le fonctionnement pour votre épreuve de Spé Maths au Bac.

 

Le But de ce chapitre est de rechercher les diviseurs positifs communs à deux entiers positifs a et b.

I - Les diviseurs communs à deux entiers positifs

On note D(a) l'ensemble des diviseurs de a. D(a) ne contient que des nombres inférieurs ou égaux à a. Si a>1 : D(a) contient toujours 1 et a. Le plus grand élément de D(a) est a.
D(a ;b) est l'ensemble des diviseurs communs à a et à b. Il contient un plus grand élément : c'est le pgcd de a et de b .
Remarque :
-Tout entier divise 0 mais 0 ne divise aucun entier.
- Si b divise a, alors PGCD (a ;b)=b
-Si a=b, D(a ;b) = D(a) ou D(b).

1 - Exercice

a et b sont deux naturels tels que a? b
Démontrer :
D(a ;b) = D(b ;a-b)
*On va démontrer que tout nombre d de D(a-b ; b) est dans D(a ;b), et réciproquement, c'est-à-dire D(a-b ;b) D(a ;b) et D(a ;b) C D(a-b ;b) .
*Si d ? D(a ;b) :
- d divise b
- d divise a - b
? Alors d ? D (b ; a-b)
* Si d ? D(a-b ; b) :
- d divise a-b
- d divise b
?Alors d divise (a-b)+b = a et d ? D(a ;b)

2 - Appliquer plusieurs fois ce résultat pour démontrer que les diviseurs communs de 168 et 264 sont ceux de 24

D(168 ;264)=D(96 ;168)=D(72 ;96)=D(24 ;72)=D(48 ;72)=D(24 ;48)=D(24 ;24) = D(24)
D(24) = { 1 ;24 ;2 ;12 ;3 ;8 ;4 ;6 }
PGCD(168 ;264) = 24.

3 - Recherche du PGCD par l'algorithme d'Euclide

Remarque préliminaire : Effectuer la division euclidienne de a par b. Alors les diviseurs communs de a et de b sont aussi les diviseurs communs de b et de r.
Démonstration :
avec a=b*q+r et D(a ;b) = D(b ;r)
0?r
Hypothèse d ? D(a ;b)
d divise a et b
Or r=a-b*q
donc d divise cette combinaison de a et b.
Ainsi : d divise r.
d divise a
d divise b alors d ? D(b ;r).
d divise r
Hypothèse : d ? D(b ;r)
Alors d divise b et r
donc d divise b*q+r. (b*q+r est a)
Ainsi d divise a
d divise b alors d ? D(a ;b).
d divise r
L'algorithme d'Euclide : Lorsque b ne divise pas a, le PGCD de a et de b est le dernier reste non nul.
1 2 3 4 5
6
PGCD (a ;b) = PGCD (b ;r) = ... = PGCD (R ;0) = R Dernier reste non nul.
La suite des restes est une suite décroissante d'entiers positifs qui converge vers 0.
Exemple :
a = 138 807 et b = 52 089
Trouver PGCD(a ;b).
1 2 3
4 5
PGCD(138 807 ; 52 089) = 291
Quels sont alors les diviseurs communs à a et à b.
Ce sont les diviseurs de 291.
D(291)={1 ;3 ;97 ;291}
Exercice : a et b sont 2 naturels. A = 630. PGCD(a ;b)=105. 600
Trouver b :
Solution :
b est un multiple de 105.
b=105*k (k ? N)
D'où : 600<105k<1100
Les valeurs possibles de k sont 1 ;6 ;7 ;8 ;9 ;10.
*Si k=6, b=630, PGCD(a ;b)=630 ? 105
Alors k =6 ne convient pas.
*Si k=7, b=735, PGCD(a ;b)=105
Alors k =7 convient.
*Si k=8, b=840, PGCD(a ;b)=210 ? 105
Alors k=8 ne convient pas.
*Si k=9, b=945, PGCD(a ;b)=315? 105
Alors k=9 ne convient pas.
*Si k=10, b=1050, PGCD(a ;b)=210 ? 105
Alors k=10 ne convient pas.
Donc la seule solution est b=735

II - Récurrence

Pour démontrer qu'une propriété P(n) est vérifiée à partir d'un certain rang n0 (c'est-à-dire pour tout naturel n tel que n ? n0 ) , on procède ainsi :
- Initialisation : on établit que P0 est vraie.
- Transmission ou caractère héréditaire :
on démontre que pour tout naturel p ? n0 , si la propriété est vraie au rang p (hypothèse de récurrence) alors la propriété est vraie au rang p+1.
-Conclusion : la propriété Pn est alors vraie pour tout n ? n0.
Exemple :
Démontrer : pour tout n ?2, 2n?2n.
*Initialisation :
n =2, 22 ?2*2 vrai.
*Caractère héréditaire :
On suppose que P(n) est vraie, c'est-à-dire : 2n ? 2n (hypothèse de récurrence)
Est-ce que P(n+1) est vraie ?
Je dois démontrer si : 2n+1 ? 2(n+1)
X2 2n ? 2n
2n+1 ? 4n
A-t-on : 4n ? 2( n+1) ?
4n ? 2n+2
n ? 1 oui car n ? 2
Conclusion : 2n+1 ? 2( n+1) , P(n+1) est vraie.
Alors P(n) est vraie pour tout n? 2.
Fin de l'extrait

Vous devez être connecté pour pouvoir lire la suite

Télécharger ce document gratuitement

Donne ton avis !

Rédige ton avis

Votre commentaire est en attente de validation. Il s'affichera dès qu'un membre de Bac S le validera.
Attention, les commentaires doivent avoir un minimum de 50 caractères !
Vous devez donner une note pour valider votre avis.

Nos infos récentes du Bac S

Communauté au top !

Vous devez être membre de digiSchool bac S

Pas encore inscrit ?

Ou identifiez-vous :

Mot de passe oublié ?