Le plus grand commun diviseur ou PGCD

a, b, k¹0 sont des nombres entiers naturels.

1) Diviseurs d'un entier:

Quand

est un entier naturel, k est un diviseur de a.

On dit aussi que a est un multiple de k ou encore que a est divisible par k.

6 est un diviseur de 18 ;

3 est un diviseur de 18 et 18 = 3´6

2) Diviseurs communs à deux entiers naturels:

Si deux entiers a et b sont divisibles par un même entier k,

on dit que k est un diviseur commun de a et b.

36 = 12´3 et 24 = 12´2 donc 12 est un diviseur commun de 36 et 24.

On peut remarquer que 1 est un diviseur commun de tous les nombres entiers.

Si deux entiers ont pour seul diviseur commun 1, on dit qu'ils sont premiers entre eux.

3) Propriétés des diviseurs communs:

Si k est un diviseur commun aux entiers a et b, avec a>b,

alors k est aussi un diviseur de (a-b) et de (a+b).

65 = 13´5 et 26 = 13´2 , 13 est diviseur commun de 65 et 26

donc 65 + 26 = 91 et 65 - 26 = 39 sont divisibles par 13.

4) PGCD:

La liste des diviseurs de 24 est : 1; 2; 3; 4; 6; 8; 12; 24.

La liste des diviseurs de 36 est: 1; 2; 3; 4; 6; 9; 12; 18; 36.

36 et 24 ont pour diviseurs communs: 1; 2; 3; 4; 6 et 12.

Le plus grand diviseur commun de 36 et 24, ou de 24 et 36 est 12.

On le désigne par PGCD(36;24).

PGCD (36;24) = PGCD (24;36) = 12.

Propriété 1: Si a est diviseur de b ; alors PGCD(a;b) = a

Propriété 2: Pour a>b; PGCD(a;b) = PGCD(a-b;b)

5) Deux méthodes pour calculer le PGCD:

On cherche PGCD(261;203)

1. Méthode des soustractions:

Il y a deux nombres égaux dans la dernière soustraction, PGCD(261;203) = 29.

2. Méthode de la division, dite de l'algorithme d'Euclide:

On s'arrête quand le reste est nul; le PGCD est le dernier reste non nul. PGCD(261;203) = 29

6) Fractions irréductibles:

Quand le numérateur et le dénominateur d'une fraction sont premiers entre eux,

on dit que cette fraction est irréductible.

On dit aussi qu'on ne peut plus la simplifier.

En simplifiant la fraction par PGCD(a;b), on obtient une fraction irréductible.

Il est parfois utile d'appliquer d'abord les critères de divisibilité. est une fraction irréductible.