Aller au contenu

Arithmétique/PGCD

Leçons de niveau 13
Une page de Wikiversité, la communauté pédagogique libre.
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
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]
descriptif indisponible
Wikipedia-logo-v2.svg
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