PGCD : cours d'arithmétique en terminale spécialité en PDF.

Le PGCD deux deux entiers naturels, dans ce cours de maths en terminale spécialité, nous aborderons l’algorithme d’Euclide et les nombres premiers entre eux.

I. Le plus grand commun diviseur ( PGCD )

1.Le PGCD de deux entiers naturels

Par convention, lorsqu’on parlera de diviseurs d’un entier naturel, il s’agira toujours de diviseurs positifs.

Diviseurs communs à deux nombres :

$\star$ Pour tout entier naturel a, on note $D(a)$ l’ensemble de ses diviseurs. $D(1)=\left \{ 1 \right \}$ , $D(0)=\mathbb{N}$ .

$D(a)$ contient toujours 1 et a.

Lorsque $a\neq0$ , le plus grand élément de $D(a)$ est a.

$\star$ Pour tous entiers naturels a et b non nuls, on note $D(a,b)$ l’ensemble des diviseurs communs à a et b.

L’ensemble $D(a,b)$ est non vide : il contient toujours 1.

De plus, tous les nombres qu’il contient sont inférieurs ou égaux à a et b.

Donc $D(a,b)$ a un plus grand élément appelé le plus grand commun diviseur et noté le PGCD de a et b.

Exemple :

$D(6)=\left \{ 1,2,3,6 \right \}$

Définition 1 :

a et b sont deux entiers naturels.Le Plus Grand Commun Diviseur à a et b est noté $PGCD(a,b)$ .

Conséquences :

Si b divise a alors pgcd(a,b)=b.En effet, tout diviseur de b est un diviseur de a donc $D(b)cD(a)$ .

Comme b est le plus grand élément de $D(b)$ , alors b est le $PGCD(a,b)$ .

2.Recherche du PGCD : l’algorithme d’Euclide.

a et b sont deux entiers naturels non nuls, a>b .Lorsque b ne divise pas a, pour déterminer le $PGCD(a,b)$ , on utilise l’algorithme d’Euclide.

Base de l’algorithme d’Euclide :

Théorème 1 :

a et b sont deux entiers naturels non nuls tel que la division euclidienne de a par b se traduise par $a=bq+r$ avec $0\leq r<b$ .Alors $D(a,b)=D(b,r)$ ce qui entraîne que $PGCD(a,b)=PGCD(b,r)$ .

Algorithme d’Euclide :

Algorithme d'Euclide

On définit ainsi une suite $(r_n)$ telle que $0\leq ...<r_{k+1}<r_k<...r_2<r_1<r_0<b$ .

Cette suite est une suite décroissante et strictement positive d’entiers naturels.Donc c’est une suite finie et il existe un entier n tel que $r_n\neq0$ et $r_{n+1}=0$ .