Voir la source de Arithmétique/PGCD

{{Chapitre
  | idfaculté  = mathématiques
  | numéro     = 2
  | page_liée  = Exercices/PPCM et PGCD
  | page_liée2 = Exercices/Fractions
  | précédent  = [[../Divisibilité et congruences dans Z/]]
  | suivant    = [[../Théorèmes de Bézout et Gauss/]]
  | niveau     = 13
}}
__TOC__
{{Clr}}
== Diviseurs communs à deux entiers naturels  ==
Deux entiers naturels non tous deux nuls ont toujours un nombre fini de diviseurs et donc de diviseurs communs (dont –1 et 1). Il existe donc un diviseur commun à ces deux nombres plus grand que les autres.

{{Définition|contenu={{Wikipédia|Plus grand commun diviseur de nombres entiers}}
Le PGCD de deux entiers naturels ''a'' et ''b'' non tous deux nuls, noté '''pgcd'''(''a'', ''b''), est leur plus grand diviseur commun. 
}}

'''Conséquence''' : <math>b\mid a \Leftrightarrow\operatorname{pgcd}\left(a,b\right)=b</math>.

== Lemme pour l'algorithme d'Euclide  ==
<!--éviter le nom "Lemme d'Euclide", car se nom désigne bien plus couramment un autre "lemme"-->
{{Lemme
  | contenu =
Soient <math>b,r\in\N^*</math> et <math>q\in\N</math>, alors : <math>\operatorname{pgcd}\left(bq+r,b\right)=\operatorname{pgcd}\left(b,r\right)</math>.
}}

{{Démonstration déroulante|contenu=
Il suffit de démontrer que <math>bq+r</math> et <math>b</math> ont mêmes diviseurs communs que <math>b</math> et <math>r</math>.

Soit <math>d</math> un diviseur de <math>bq+r</math> et <math>b</math>, alors <math>d</math> divise <math>(bq+r)-bq=r</math>.

Réciproquement, soit <math>d</math> un diviseur de <math>b</math> et <math>r</math>, alors <math>d</math> divise <math>bq+r</math>.
}}

== Algorithme d'Euclide  ==
{{Wikipédia|algorithme d'Euclide}}
Soient <math>a</math> et <math>b</math> deux entiers naturels tels que <math>b\ne0</math>.

{| class="wikitable" | valign="center" | align="center"
! Opération !! Reste <math>r</math> !! Commentaire
|- valign="center" | align="center"
| on divise <math>a</math> par <math>b</math>
| <math>r_0</math>
| <math>0\le r_0<b\text{ et }\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r_0)</math>
|- valign="center" | align="center"
| si <math>r_0\neq 0</math>, on divise <math>b</math> par <math>r_0</math>
| <math>r_1</math>
| <math>0\le r_1<r_0\text{ et }\operatorname{pgcd}(b,r_0)=\operatorname{pgcd}(r_0,r_1)</math>
|- valign="center" | align="center"
| …
| …
| …
|- valign="center" | align="center"
| si <math>r_n\neq 0</math>, on divise <math>r_{n-1}</math> par <math>r_n</math>
| <math>0</math>
| <math>\operatorname{pgcd}(r_{n-1},r_n)=r_n</math>
|}

{{Propriété
  | contenu =
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.
}}

{{Corollaire|contenu=Les diviseurs communs à deux entiers naturels ''a'' et ''b'' non tous deux nuls sont les diviseurs de pgcd(''a'', ''b'').
}}
Ceci fournit une définition alternative du PGCD.

== Propriétés du PGCD  ==

{{Propriété
  | contenu =
Si l’on multiplie deux entiers naturels non tous deux nuls ''a'' et ''b'' par un même entier naturel non nul ''k'', leur PGCD est multiplié par ''k'', c'est-à-dire :<div style="text-align: center;">
<math>\operatorname{pgcd}(ka,kb)=k\times\operatorname{pgcd}(a,b)</math>.</div>
}}

{{Démonstration déroulante|contenu=
L'entier ''k'' divise ''ka'' et ''kb'' donc aussi leur PGCD. L'entier ''d'' > 0 défini par ''pgcd''(''ka'', ''kb'') = ''kd'' vérifie alors :
<div style="text-align: center;"><math>\forall n\in\Z\quad n\mid a,b\iff kn\mid ka,kb\iff kn\mid pgcd(ka,kb)\iff n\mid d</math></div>
donc
<div style="text-align: center;"><math>\operatorname{pgcd}(a,b)=d=\operatorname{pgcd}(ka,kb)/k</math></div>.
}}


{{Exemple
  | titre   =Exemple : calcul de <math>\operatorname{pgcd}(12000,32000)</math>
  | contenu =
:<math>12000=12\times1000</math> et <math>32000=32\times1000</math>
donc <math>\operatorname{pgcd}(12000,32000)=1000\times\operatorname{pgcd}(12,32)=4000</math>.
}}

'''Conséquence : ''' si <math>k</math> est un entier naturel non nul, diviseur commun à <math>a</math> et <math>b</math>, alors <math>\operatorname{pgcd}\left(\frac ak,\frac bk\right )=\frac1k\times\operatorname{pgcd}(a,b)</math>.

== Extension du PGCD aux entiers relatifs  ==

{{Définition
  | contenu =
Le PGCD de deux entiers relatifs non nuls <math>a</math> et <math>b</math> est le PGCD de leurs valeurs absolues, c'est-à-dire <math>\operatorname{pgcd}(a,b)=\operatorname{pgcd}(|a|,|b|)</math>.
}}

{{Remarque
  | contenu =
* <math>\forall k \in \Z^*\quad\operatorname{pgcd}(ka,kb)=|k|\operatorname{pgcd}(a,b)</math>
* Les diviseurs communs à <math>a</math> et <math>b</math> sont encore les diviseurs de <math>\operatorname{pgcd}(a,b)</math>
}}

== Nombres premiers entre eux  ==

{{Définition
  | contenu ={{Wikipédia|Nombres premiers entre eux}}
Deux entiers relatifs <math>a</math> et <math>b</math> non tous deux nuls sont dits premiers entre eux si <math>\operatorname{pgcd}(a,b)=1</math>.
}}

{{Exemple
  | contenu =
<math>35</math> et <math>26</math> sont premiers entre eux, car leur seul diviseur commun positif est <math>1</math>.
}}

{{Propriété
  | contenu =
Soient <math>a</math> et <math>b</math> deux entiers relatifs non tous deux nuls, <math>d</math> leur PGCD, et <math>a',b'</math> les entiers définis par <math>a=da'</math> et <math>b=db'</math>. Alors, <math>a'</math> et <math>b'</math> sont premiers entre eux.
}}

{{Démonstration déroulante|contenu=
<math>d</math> est non nul et divise <math>a</math> et <math>b</math> donc :
*<math>a':=\frac ad</math> et <math>b':=\frac bd</math> sont bien définis et sont bien des entiers ;
*<math>\operatorname{pgcd}(a',b')=\frac{\operatorname{pgcd}(da',db')}d=\frac{\operatorname{pgcd}(a,b)}d=1</math>.
}}

{{Bas de page
  | idfaculté = mathématiques
  | précédent = [[../Divisibilité et congruences dans Z/]]
  | suivant   = [[../Théorèmes de Bézout et Gauss/]]
}}