Arithmétique/PGCD

Début de la boite de navigation du chapitre
PGCD
Icône de la faculté
Chapitre no 2
Leçon : Arithmétique
Chap. préc. :Divisibilité et congruences dans Z
Chap. suiv. :Théorèmes de Bézout et Gauss

Exercices :

PPCM et PGCD
Exercices :Fractions
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Arithmétique : PGCD
Arithmétique/PGCD
 », n'a pu être restituée correctement ci-dessus.

Diviseurs communs à deux entiers naturelsModifier

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.


Conséquence :  .

Lemme pour l'algorithme d'EuclideModifier

Début d'un lemme
Fin du lemme


Algorithme d'EuclideModifier

Wikipédia possède un article à propos de « algorithme d'Euclide ».

Soient   et   deux entiers naturels tels que  .

Opération Reste   Commentaire
on divise   par      
si  , on divise   par      
si  , on divise   par      

Ceci fournit une définition alternative du PGCD.

Propriétés du PGCDModifier


Début de l'exemple
Fin de l'exemple


Conséquence : si   est un entier naturel non nul, diviseur commun à   et  , alors  .

Extension du PGCD aux entiers relatifsModifier



Nombres premiers entre euxModifier


Début de l'exemple
Fin de l'exemple