Initiation à l'arithmétique/PGCD

Leçons de niveau 10
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 3
Leçon : Initiation à l'arithmétique
Chap. préc. :Division euclidienne
Chap. suiv. :Nombres premiers

Exercices :

Sujets de brevet
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Initiation à l'arithmétique : PGCD
Initiation à l'arithmétique/PGCD
 », n'a pu être restituée correctement ci-dessus.

Plus grand diviseur commun de deux nombres entiers positifs[modifier | modifier le wikicode]


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


Algorithme d’Euclide : une méthode pour trouver le PGCD[modifier | modifier le wikicode]

Le mot algorithme vient du mathématicien arabe du XIe siècle Al-Khwarizmi.

Euclide est un savant grec du IIIe siècle avant J.C., auteur des fameux Éléments.

Un algorithme est une procédure automatisée qui permet de trouver un résultat « sans réfléchir ». Par exemple, quand on pose une opération, on applique un algorithme.

L'algorithme d'Euclide est une méthode pour trouver le PGCD de deux nombres entiers par divisions euclidiennes successives.

Propriété de transmission du PGCD[modifier | modifier le wikicode]


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


Algorithme d’Euclide : exemple[modifier | modifier le wikicode]

On veut le PGCD de et .

On effectue les divisions successives :

 ;
 ;
 ;
.

Le dernier reste non nul est donc .

Applications du PGCD[modifier | modifier le wikicode]

Nombres premiers entre eux[modifier | modifier le wikicode]

Définition[modifier | modifier le wikicode]


PGCD de deux nombres premiers entre eux[modifier | modifier le wikicode]

Exemple[modifier | modifier le wikicode]

25 et 36 sont premiers entre eux (bien qu’aucun des deux ne soit premier !) car leur PGCD vaut 1.

Contre-exemple[modifier | modifier le wikicode]

24 et 36 ne sont pas premiers entre eux, car leur PGCD vaut 12 (leurs diviseurs communs sont donc : 1, 2, 3, 4, 6, 12).

Rendre une fraction irréductible[modifier | modifier le wikicode]



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