Leçons de niveau 13

Arithmétique/PGCD

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
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 naturels[modifier | modifier le wikicode]

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'Euclide[modifier | modifier le wikicode]

Début d'un lemme


Fin du lemme


Algorithme d'Euclide[modifier | modifier le wikicode]

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 PGCD[modifier | modifier le wikicode]



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 relatifs[modifier | modifier le wikicode]





Nombres premiers entre eux[modifier | modifier le wikicode]



Début de l'exemple


Fin de l'exemple