Arithmétique/PGCD

Une page de Wikiversité.


PGCD
Nuvola apps edu mathematics-p.svg
Chapitre 2
Leçon : Arithmétique
Chap. préc. : Divisibilité et congruences dans Z
Chap. suiv. : Nombres premiers


Icon falscher Titel.svg

En raison de limitations techniques, la typographie souhaitable du titre, « Arithmétique : PGCD
Arithmétique/PGCD », n'a pu être restituée correctement ci-dessus.

Sommaire

[modifier] Diviseurs communs à 2 entiers naturels

2 entiers naturels non nuls ont toujours un nombre fini de diviseurs et donc de diviseurs communs (dont -1 et 1). Il existe donc un diviseur commun à ces 2 nombres plus grand que les autres.


Définition

\forall (a,b) \in \mathbb{N}^{*2}, le PGCD de a et b est noté pgcd(a,b)\,


Conséquence : b|a \Leftrightarrow pgcd(a,b) = b

[modifier] Lemme d'Euclide

Lemme d'Euclide

(a,b) \in \mathbb{N}^{*2}
Si des entiers naturels q et r, avec r \ne 0\,, sont tels que a = bq+r\,, alors :
pgcd(a,b) = pgcd(b,r)\,


Démonstration

d désigne un diviseur commun à a et b. De r = a-bq\,, on en déduit que d divise r. Ainsi tout diviseur commun à a et b est un diviseur commun à b et r.
Réciproquement, d' désigne un diviseur commun à b et r. De a = bq+r\,, on déduit que d' divise a. Ainsi tout diviseur commun à b et r est un diviseur commun à a et b.
En conclusion, a et b ont les mêmes diviseurs communs que b et r donc pgcd(a,b) = pgcd(b,r)\,


[modifier] Algorithme d'Euclide

Soient (a,b)\in \mathbb{N}^{*2} tels que a>b\,

Opération Reste r\, Commentaire
on divise a\, par b\, r_0\, 0\le r_0<b \mbox{ et } pgcd(a,b)=pgcd(b,r_0)
si r_0\neq 0, on divise b\, par r_0\, r_1\, 0\le r_1<r_0 \mbox{ et } pgcd(b,r_0)=pgcd(r_0,r_1)
… … …
si r_n\neq 0, on divise r_{n-1}\, par r_n\, 0\, pgcd(r_{n-1},r_n)=r_n\,



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.


Conséquence : Les diviseurs communs à deux entiers naturels non nuls a\, et b\, sont les diviseurs de pgcd(a,b)\,.

[modifier] Propriétés du PGCD

Propriété

Si on multiplie deux entiers naturels non nuls a\, et b\, par un même entier naturel k\,, leur PGCD est multiplié par k\,, c'est-à-dire :
pgcd(ka,kb) = k\times pgcd(a,b).



Démonstration

Si a=bq+r\, avec 0\le r<b, alors ka=kbq+kr\, (car k\in \mathbb{N}).
Donc kr\, est le reste de la division de ka\, par kb\, d'après l'unicité de l'écriture. Avec les notations utilisées au paragraphe #Algorithme d'Euclide et en multipliant chaque membre des égalités par k\,, on obtient :
pgcd(ka,kb)=pgcd(kb,kr_0)=...=kr_n=k\times pgcd(a,b)\,



Calcul de pgcd(12000,32000)\,

12000=12\times 1000 et 32000=32\times 1000
Donc pgcd(12000,32000)=1000\times pgcd(12,32)=4000.\,


Conséquence : si k\, est un entier naturel non nul, diviseur commun à a\, et b\,, alors pgcd\left (\frac{a}{k},\frac{b}{k}\right )=\frac{1}{k}\times pgcd(a,b).

[modifier] Extension du PGCD aux entiers relatifs

Définition

a\, et b\, désignent deux entiers relatifs non nuls. Le PGCD de a\, et b\, est égal au PGCD de |a|\, et |b|\,, c'est-à-dire pgcd(a,b)=pgcd(|a|,|b|).\,


Remarques :

  • \forall k \in \mathbb{Z}^*, pgcd(ka,kb)=|k|pgcd(a,b)
  • Les diviseurs communs à a\, et b\, sont encore les diviseurs de pgcd(a,b)\,

[modifier] Nombres premiers entre eux

Définition

Dire que deux entiers relatifs non nuls a\, et b\, sont premiers entre eux signifie que pgcd(a,b)=1.\,



Exemple

35\, et 26\, sont premiers entre eux, car leur seul diviseur commun positif est 1.



Propriété

(a,b)\in \mathbb{Z}^{*2}
Si d=pgcd(a,b)\, alors il existe des entiers relatifs a'\, et b'\, premiers entre eux tels que a=da'\, et b=db'\,.



Démonstration

d|a \Rightarrow \exists a'\in \mathbb{Z} tel que a=da'\,. De même, \exists b'\in \mathbb{Z} tel que b=db'\,.
Donc : d=pgcd(a,b)=pgcd(da',db')=d\times pgcd(a',b')
Or d\ge 1 \Rightarrow d\neq 0, pgcd(a',b')=1


Crystal Clear action back.png Divisibilité et congruences dans Z
Récupérée de « http://fr.wikiversity.org/wiki/Arithm%C3%A9tique/PGCD »