« Arithmétique/PGCD » : différence entre les versions

{{Définition

| contenu =

'''Conséquence''' : <math>b|a \Leftrightarrow pgcd(a,b) = b</math>

 

=== Lemme d'Euclide ===

{{Théorème

 

{{Cadre définition|titre=Démonstration|contenu=d désigne un diviseur commun à a et b. De <math>r = a-bq\,</math>, on en déduit que d divise r. Ainsi tout diviseur commun à a et b est un diviseur commun à b et r.<br />Réciproquement, d' désigne un diviseur commun à b et r. De <math>a = bq+r\,</math>, on déduit que d' divise a. Ainsi tout diviseur commun à b et r est un diviseur commun à a et b.<br />En conclusion, a et b ont les mêmes diviseurs communs que b et r donc <math>pgcd(a,b) = pgcd(b,r)\,</math>|cbord=#69BD69|cfondtitre=#CAEDC7|cfondtexte=#EDFEE9}}<br />

 

=== Algorithme d'Euclide ===

{| border="1" | valign="center" | align="center"

! Opération !! Reste <math>r\,</math> !! Commentaire

}}<br />

{{Principe|titre=Démonstration|contenu=

Donc <math>kr\,</math> est le reste de la division de <math>ka\,</math> par <math>kb\,</math> 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 <math>k\,</math>, on obtient :<br />

<math>pgcd(ka,kb)=pgcd(kb,kr_0)=...=kr_n=k\times pgcd(a,b)\,</math>

}}<br />

'''Remarques :'''

* Les diviseurs communs à <math>a\,</math> et <math>b\,</math> sont encore les diviseurs de <math>pgcd(a,b)\,</math>

 

{{Propriété

| contenu =

Si <math>d=pgcd(a,b)\,</math> alors il existe des entiers relatifs <math>a'\,</math> et <math>b'\,</math> premiers entre eux tels que <math>a=da'\,</math> et <math>b=db'\,</math>.

}}<br />

{{Principe|titre=Démonstration|contenu=

Donc : <math>d=pgcd(a,b)=pgcd(da',db')=d\times pgcd(a',b')</math><br />

Or <math>d\ge 1 \Rightarrow d\neq 0, pgcd(a',b')=1</math>