« Arithmétique/PGCD » : différence entre les versions
Contenu supprimé Contenu ajouté
mise à jour |
mAucun résumé des modifications |
||
Ligne 11 :
{{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.
}}
Ligne 36 :
== Algorithme d'Euclide ==
{{Wikipédia|algorithme d'Euclide}}
Soient <math>a</math> et <math>b</math> deux entiers naturels tels que <math
{| class="wikitable" | valign="center" | align="center"
Ligne 63 :
}}
}}
Ceci fournit une définition alternative du PGCD.
Ligne 71 :
{{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>
}}
Ligne 79 :
<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>
}}
{{Exemple
| |||