Plus Grand Commun Dénominateur (PGCD) |cours de spé maths terminale

Cours et code réalisé par Vincent Maffet

I PGCD de deux entiers

1) Diviseurs communs à deux entiers naturels

a) définition

Soit a et b deux entiers naturels non nuls. Le plus grand diviseur commun à a et b est appelé PGCD de a et b. On le note PGCD(a;b)

b) PGCD et decomposition en produit de facteurs premiers

Théorème :

Le PGCD(a;b) est égal au produit des facteurs premiers communs aux décompositions de a et de b, chacun d'eux étant affecté du plus petit exposant avec lequel il figure dans les décompositions de a et de b.

c) Proposition fondamentale

Proposition :

Soit deux entiers naturels a et b tels que a>b et r le reste de la division euclidienne de a par b

- Si r=0 alors les diviseurs communs à a et b sont les diviseurs de b et PGCD(a;b)=b

- si r≠0 alors les diviseurs communs à a et b sont les diviseurs communs à b et r et PGCD(a;b)=PGCD(b;r)

Démonstration :

- Si r=o alors b divise a soit d un diviseur commun à a et b, alors d divise b

Réciproquement, si d divise b, comme b divise a, d divise a et d est un diviseur commun à a et b

Conclusion, les diviseurs communs à a et b sont les diviseurs de b et PGCD(a;b)=b

- Si r≠0 alors a=bq+r avec 0<r<b

Soit d un diviseur commun à a et b, alors d divise a-bq, c'est à dire d divise r et d est donc un diviseur commun à b et r

2) Calcul du PGCD de deux entiers naturels non nuls : Algorithme d'Euclide

Soit a et b deux entiers naturels non nuls avec a>b

Après un nombre fini de diviseurs, on obtient un reste nul car les restes sont des entiers positifs qui vont en décroissant strictement :

0<r_n<r_n+1<...<r₂<r₁<r₀

PGCD(a;b)=PGCD(b;r₀)=PGCD(r₀;r₁)=...=PGCD(r_n-1;r_n)=r_n, r_n étant le dernier reste non nul

Propriété :

Lorsque b ne divise pas a, le PGCD des entiers naturels non nuls a et b est égal au dernier reste non nul obtenu par l'algorithme d'Euclide

Algorithme d'Euclide

Cf. page algorithme

Propriété :

Les diviseurs communs à deux entiers naturels non nuls a et b sont les diviseurs du PGCD(a;b)

Démonstration

d divise a et b ⇔ d divise b et r₀

d divise b et r₀ ⇔ d divise r₀ et r₁

|

d divise r_n et r_n-1 ⇔ d divise r_n car r_n divise r_n-1

3) Propriété du PGCD

Propriété :

Soit a ∈ N*, b ∈ N* et k ∈ N*

PGCD(ka;kb)=k*PGCD(a;b)

Démonstration :

a=bq+r₀ avec 0≤r₀<b

Alors ka=kbq+kr₀ avec 0≤kr₀<kb

kr₀ est le reste de la division euclidienne de ka par kb d'après l'unicité de l'écriture,

PGCD(ka;kb)=PGCD(kb;kr₀)=PGCD(kr₀;kr₁)=...=kr_n=PGCD(a;b)*k

4) Extension du PGCD aux entiers relatifs

Définition :

Soit a et b deux entiers relatifs non nuls

PGCD(a;b)=PGCD(|a|;|b|)

Remarques :

- Pour tout k ∈ Z*, PGCD(ka;kb)=|k|PGCD(a;b)

- LEs diviseurs communs à a et b sont les diviseurs du PGCD(a;b)

5) Nombres premiers entre eux

définition :

Dire que deux entiers relatifs non nuls a et b sont premiers entre eux signifie PGCD(a;b)=1

Propriété :

Soit a et b deux entiers relatifs non nuls

Si d=PGCD(a;b) alors il existe 2 entiers relatifs a' et b' premiers entre eux tels que a=da' et b=db'

Démonstration (exigible) :

d divise a donc il existe un entier relatif a' tel que a=da'

d divise b donc il existe un entier relatif b' tel que b=db'

d=PGCD(da';db')=d*PGCD(a';b')

d>0 donc PGCD(a';b')=1

-

Partagez ce cours !

Suivez Vincent Maffet sur google + ( cours inspiré de celui fait par le professeur de la classe)