« Arithmétique/PGCD » : différence entre les versions
Contenu supprimé Contenu ajouté
m Retrait des catégories en double |
. |
||
Ligne 1 :
{{Chapitre
| 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>
}} '''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> }} {{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 =
▲
}}
=== Algorithme d'Euclide ===
Soient <math>(a,b)\in \N^{*2}</math> tels que <math>a>b\,</math
{| 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>
|}
{{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.
}}
'''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>.
}}
{{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>).
▲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 :
<math>pgcd(ka,kb)=pgcd(kb,kr_0)=...=kr_n=k\times pgcd(a,b)\,</math>
}}
{{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 />▼
| contenu =
Donc <math>pgcd(12000,32000)=1000\times 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>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>
}}
| 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>
}}
{{Exemple
| contenu =
<math>35\,</math> et <math>26\,</math> sont premiers entre eux, car leur seul diviseur commun positif est 1.
}}
{{Propriété
| contenu =
<math>(a,b)\in \Z^{*2}</math
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>.
<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>.
▲Or <math>d\ge 1 \Rightarrow d\neq 0, pgcd(a',b')=1</math>
}}
{{Bas de page
|