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

Contenu supprimé Contenu ajouté
m Retrait des catégories en double
.
Ligne 1 :
{{Chapitre
| titre = PGCD
| idfaculté = mathématiques
| numéro = 2
Ligne 10 ⟶ 9 :
=== 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.<br />
 
{{Définition
| contenu =
<math>\forall (a,b) \in \N^{*2}</math>, le PGCD de a et b est noté <math>pgcd(a,b)\,</math>
}}<br />
 
'''Conséquence''' : <math>b|a \Leftrightarrow pgcd(a,b) = b</math>
 
=== Lemme d'Euclide ===
 
{{Théorème
| titre = Lemme d'Euclide
| contenu =
<math>(a,b) \in \N^{*2}</math><br />Si des entiers naturels q et r, avec <math>r \ne 0\,</math>, sont tels que <math>a = bq+r\,</math>, alors :<br /><math>pgcd(a,b) = pgcd(b,r)\,</math>
}}<br />
 
{{Démonstration
{{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 />
| contenu =
{{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 ===
Soient <math>(a,b)\in \N^{*2}</math> tels que <math>a>b\,</math><br />
 
{| border="1" | valign="center" | align="center"
! Opération !! Reste <math>r\,</math> !! Commentaire
Ligne 42 ⟶ 52 :
| <math>pgcd(r_{n-1},r_n)=r_n\,</math>
|}
 
<br />
 
{{Propriété
| contenu =
Lorsque <math>b\,</math> ne divise pas <math>a\,</math>, le PGCD des entiers naturels non nuls <math>a\,</math> et <math>b\,</math> est égal au dernier reste non nul obtenu par l'algorithme d'Euclide.
}}<br />
 
'''Conséquence :''' Les diviseurs communs à deux entiers naturels non nuls <math>a\,</math> et <math>b\,</math> sont les diviseurs de <math>pgcd(a,b)\,</math>.
 
=== Propriétés du PGCD ===
 
{{Propriété
| contenu =
Si on multiplie deux entiers naturels non nuls <math>a\,</math> et <math>b\,</math> par un même entier naturel <math>k\,</math>, leur PGCD est multiplié par <math>k\,</math>, c'est-à-dire :<br />
<math>pgcd(ka,kb) = k\times pgcd(a,b)</math>.
}}<br />
 
{{Principe|titre=Démonstration|contenu=
{{Démonstration
Si <math>a=bq+r\,</math> avec <math>0\le r<b</math>, alors <math>ka=kbq+kr\,</math> (car <math>k\in \N</math>).<br />
| 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 />
Si <math>a=bq+r\,</math> avec <math>0\le r<b</math>, alors <math>ka=kbq+kr\,</math> (car <math>k\in \N</math>).<br />
 
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 />
 
{{Exemple|titre=Calcul de <math>pgcd(12000,32000)\,</math>|contenu=
{{Exemple
<math>12000=12\times 1000</math> et <math>32000=32\times 1000</math><br />
{{Exemple | titre = Calcul de <math>pgcd(12000,32000)\,</math>|contenu=
| contenu =
<math>12000=12\times 1000</math> et <math>32000=32\times 1000</math><br />
 
Donc <math>pgcd(12000,32000)=1000\times pgcd(12,32)=4000.\,</math>
}}<br />
 
'''Conséquence : ''' si <math>k\,</math> est un entier naturel non nul, diviseur commun à <math>a\,</math> et <math>b\,</math>, alors <math>pgcd\left (\frac{a}{k},\frac{b}{k}\right )=\frac{1}{k}\times pgcd(a,b).</math>
Ligne 72 ⟶ 92 :
{{Définition
| contenu =
 
<math>a\,</math> et <math>b\,</math> désignent deux entiers relatifs non nuls. Le PGCD de <math>a\,</math> et <math>b\,</math> est égal au PGCD de <math>|a|\,</math> et <math>|b|\,</math>, c'est-à-dire <math>pgcd(a,b)=pgcd(|a|,|b|).\,</math>
}}<br />
 
'''{{Remarques :'''
| contenu =
* <math>\forall k \in \Z^*, pgcd(ka,kb)=|k|pgcd(a,b)</math>
* Les diviseurs communs à <math>a\,</math> et <math>b\,</math> sont encore les diviseurs de <math>pgcd(a,b)\,</math>
}}
 
=== Nombres premiers entre eux ===
Ligne 83 ⟶ 105 :
{{Définition
| contenu =
 
Dire que deux entiers relatifs non nuls <math>a\,</math> et <math>b\,</math> sont premiers entre eux signifie que <math>pgcd(a,b)=1.\,</math>
}}<br />
 
{{Exemple
| contenu =
 
<math>35\,</math> et <math>26\,</math> sont premiers entre eux, car leur seul diviseur commun positif est 1.
}}<br />
 
{{Propriété
| contenu =
<math>(a,b)\in \Z^{*2}</math><br />
 
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=
<math>d|a \Rightarrow \exists a'\in \Z</math> tel que <math>a=da'\,</math>. De même, <math>\exists b'\in \Z</math> tel que <math>b=db'\,</math>.<br />
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>
}}
 
{{Démonstration
| contenu =
<math>d|a \Rightarrow \exists a'\in \Z</math> tel que <math>a=da'\,</math>. De même, <math>\exists b'\in \Z</math> tel que <math>b=db'\,</math>.<br />
 
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>
}}
 
{{Bas de page