Le Plus Grand Commun Diviseur (ou PGCD) de deux entiers

 

I. Qu' est ce le PGCD de manière intuitive ?

Objectif: Calculer le pgcd de 14 et 42

 

a) Qu' est ce un diviseur ?

On dit que b est un diviseur de a, s'il existe un nombre q tel que

a = b x q

Par exemple, 14 = 2 x 7. Les nombres 2 et 7 sont des diviseurs de 14.

b) Diviseurs communs de 14 et 42?

Les diviseurs de 14 sont : 1, 2, 7, et 14.

Les diviseurs de 42 sont : 1, 2, 3, 6, 7, 14, 21 et 42.

Les diviseurs communs de ces deux nombres sont: 1, 2, 7, et 14.

c) Que pouvez-vous dire du pgcd de 14 et 42?

Le plus grand nombre de la liste des diviseurs communs de 14 et 42 est : 14.

14 est donc le pgcd de 14 et 42.

d) Que pouvez-vous dire du pgcd de 14 et 3?

Le pgcd de ces deux nombres vaut 1. Par conséquent, les nombres 14 et 3 sont premiers entre eux.

Deux nombres sont premiers entre eux, si leur pgcd vaut 1.

 

II. Comment calculer un PGCD avec deux grands nombres entiers?

Rappel de la division euclidienne de a par b:

 

On le calcule à l'aide de l'algorithme d'Euclides. Voici à quoi ressemble cet algorithme:

Cet algorithme s'arrête.

Application: Calcul du pgcd de 270 et de 378

III. A quoi sert un PGCD ?

1) Elle sert à transformer une fraction sous sa forme irréductible

Sachant que pgcd(648,972) = 324, on a :

2) Elle sert à résoudre des problèmes de composition.