Initiation à l'arithmétique/PGCD

Une page de Wikiversité.


PGCD
Nuvola apps edu mathematics-p.svg
Chapitre 2
Leçon : Initiation à l'arithmétique
Chap. préc. : Divisibilité
Chap. suiv. : Nombres premiers


Icon falscher Titel.svg

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.

Sommaire

[modifier] Plus grand diviseur commun de deux entiers positifs

Définition

Parmi les diviseurs communs de deux nombres a et b, il y en a toujours un « plus grand », noté PGCD(a, b)

[modifier] Exemple : pgcd(24, 36)

Les diviseurs de 24 sont : 1, 2, 3, 4, 6, 8, 12, 24

Les diviseurs de 36 sont : 1, 2, 3, 4, 6, 9, 12, 18, 36

Les diviseurs communs de 24 et 36 sont : 1, 2, 3, 4, 6, 12

donc le plus grand diviseur commun de 24 et 36 est : pgcd(24, 36)= 12

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

Le mot algorithme vient du mathématicien arabe du Ⅺe siècle Al Kwarismi.

Euclide est un savant grec (Alexandrie) du Ⅲe 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 entiers par le calcul.

[modifier] Propriété de transmission du PGCD

Propriété

Dans une division euclidienne :

a = b\times q + r

où a : dividende ; b : diviseur ; q : quotient ; r : reste

Si r est non nul alors pgcd(a;b)=pgcd(b;r)\,

[modifier] Exemple

49=14\times3 + 7

pgcd(49;14)=pgcd(14;7)=7\,

[modifier] Algorithme d’Euclide : Exemple

On veut le PGCD de 702 et 273.

On effectue les divisions successives :

702 = 273\times2 + 156

273 = 156\times1 + 117

156 = 117\times1 + 39

117 = 39\times3 + 0

Le dernier reste non nul est 39 donc pgcd(702 ; 273) = 39\,

[modifier] Applications du pgcd

[modifier] Nombres premiers entre eux

[modifier] Définition

Définition

Deux nombres entiers sont premiers entre eux si leur seul diviseur commun est 1.

[modifier] pgcd de deux nombres premiers entre eux

Propriété

Si deux nombres sont premiers entre eux, alors leur pgcd vaut 1 et réciproquement si le pgcd de deux nombres est 1 alors ils sont premiers entre eux.

[modifier] Exemple

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

[modifier] Contre-exemple

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


[modifier] Rendre une fraction irréductible

Définition

Une fraction irréductible est une fraction qu'on ne peut pas simplifier davantage.


Propriété

Dans une fraction irréductible, le numérateur (en haut) et le dénominateur (en bas) sont premiers entre eux.


Méthode : Pour rendre une fraction irréductible, il suffit de simplifier par le pgcd du numérateur et du dénominateur.

[modifier] Exemple

Pour rendre irréductible la fraction \frac{75}{60}

Calculons avec l'algorithme d'Euclide le pgcd(75;60)\,

75 = 60\times 1 + 15

60 = 15\times 4 + 0

donc pgcd(75 ; 60) = 15\,

donc \frac{75}{60} = \frac{5\times 15}{4\times 15}=\frac{5}{4}

et cette dernière fraction est irréductible.

[modifier] Exercice

Nuvola apps edu mathematics-p.svg Voir les exercices sur : Sujet de brevet.
Crystal Clear action back.png Divisibilité
Récupérée de « http://fr.wikiversity.org/wiki/Initiation_%C3%A0_l%27arithm%C3%A9tique/PGCD »