Cours maths Terminale S

Pgcd

Le cours commence par la révision de la division euclidienne dans ℕ , puis étend la définition de cette division à ℤ . La notion de PGCD de deux nombres entiers est abordée ainsi que les méthodes pour le calculer. Il finit avec le théorème de Gauss.

 

1/ Division euclidienne

Division euclidienne dans ℕ :

Soient a ∈ ℕ et b ∈ ℕ *
Il existe un unique couple ( q , r ) d’entiers naturels tels que :
a = b x q + r avec 0 ≤ r

q est le quotient, r le reste, b le diviseur et a le dividende.

Propriété :

« b divise a » si et seulement si « le reste de la division euclidienne de a par b est nul ».

Division euclidienne dans ℕ :

Soient a ∈ ℤ et b ∈ ℤ *
Il existe un unique couple ( q , r ) d’entiers relatifs tels que :
a = b x q + r avec 0 ≤ r

Remarques :

1) si a et b sont des naturels, le couple obtenu dans les deux divisions est le même
2) dans tous les cas, r est un entier naturel

 

2/ PGCD

Soient a et b deux entiers naturels non nuls.
Notons D(a) l’ensemble des diviseurs de a et D(b) celui des diviseurs de b.

L’ensemble de leurs diviseurs communs est noté : D(a,b) , D(a,b) = D(a) ∩ D(b)
1 divise a et b donc D(a,b) n’est pas vide.

De plus, a et b admettant un nombre fini de diviseurs,leurs diviseurs communs sont en nombre fini. D(a,b) étant un sous ensemble fini et non vide de ℕ , il admet donc un plus grand élément d.

Définition du PGCD de deux entiers naturels non nuls :
Si a et b sont deux entiers naturels non nuls, alors ils possèdent un plus grand diviseur commun, d, aussi appelé plus grand commun diviseur et donc noté : d = pgcd (a,b)     ou     d = a ^ b

Remarques :

1) pgcd (a,b) = pgcd (b,a)
2) si a et b sont des entiers relatifs non nuls : pgcd (a,b) = pgcd (lal,lbl)

 

3/ Recherche du PGCD : diviseurs communs

Chercher le pgcd de deux entiers c’est par définition, chercher le plus grand de leurs diviseurs communs.

D’où la première méthode de recherche du pgcd :

Méthode n° 1 :

- trouver l’ensemble des diviseurs de chaque nombre.
- lister les diviseurs communs dans l’ordre croissant et prendre le plus grand.

Remarque:

il existe plusieurs façons de trouver les diviseurs d’un nombre.

Exemple : recherchons le pgcd de 150 et 120.

Utilisons la technique vue au collège, qui consiste à écrire le nombre comme le produit de deux facteurs.

Les diviseurs communs à 150 et 120 sont donc :
1, 2, 3, 5, 6, 10, 15, 30.

D’où : pgcd (120 , 150) = 30

 

3/ Recherche du PGCD : décomposition en facteurs premiers

Une autre façon de trouver l’ensemble des diviseurs d’un nombre est d’utiliser sa décomposition en produit de facteurs premiers.

Rappels :

Si la décomposition en facteurs premiers de a est :
Alors, tout diviseur d de a s’écrit :
avec pour tout i compris entre 1 et m : 0 < ϒ i

Mais si l’on possède les décompositions de a et de b, il est alors inutile de rechercher l’ensemble des diviseurs communs pour n’en garder que le plus grand.

En effet, si on appelle p₁, p₂, ... , p_n les facteurs premiers figurant soit dans la décomposition de a soit dans celle de b alors a et b s’écrivent :


Avec pour tout i compris entre 1 et n : αi ≥ 0 et βi > 0
Alors, si d\a et d\b la décomposition de d ne peut comporter que des p_i
d’où si d diviseur commun à a et b :
Avec pour tout i compris entre 1 et n : 0 ≤ ϒ i

Remarque :

si p_i n’apparaît pas dans une des décompositions alors min (α i ; β i)
D’où : ϒ i = 0 , et ce facteur n’apparaît alors pas dans la décomposition de d.
Le plus grand diviseur étant celui qui a les puissances les plus grandes : Avec pour tout i compris entre 1 et n : ϒ i = min (α i ; β i)
D’où :

Méthode n° 2 :

- décomposer chaque nombre en produit de facteurs premiers.
- affecter aux facteurs premiers communs l’exposant le plus petit.
Application : reprenons l’exemple de a = 150 et b = 120.

150 = 21 x 31 x 52 120 = 23 x 31 x 51

D'où pgcd (120 , 150) = 21 x 31 x 51 = 30

 

3/ Recherche du PGCD : algorithme d’Euclide

Il existe enfin une troisième méthode qui consiste à réaliser une suite de divisions euclidiennes jusqu’à obtention d’un reste nul.

Montrons tout d’abord deux résultats intermédiaires
Soient a et b deux entiers naturels non nuls.
Si a = b x q + r avec q et r entiers naturels non nuls alors pgcd (a,b) = pgcd (b,r)

Si d\a et d\b alors d\a-b x q donc d\r d’où :

Si d\r et d\b alors d\b x q + r donc d \ a d’où :

Ayant les mêmes diviseurs communs, les deux couples ont donc le même plus grand diviseur commun.

si b \ a alors pgcd (a,b) = b

Si d est un diviseur commun à a et b alors d divise b. Or b non nul, d’où d ≤ b
De plus, b est un diviseur commun à a et b.
b est donc le plus grand diviseur commun à a et b.

La division euclidienne de a par b s’écrit : a = b x q₁ + r₁ avec 0 ≤ r₁
Soit r₁ = 0 auquel cas b \ a et alors pgcd (a,b) = b
soit r₁ ≠ 0 On a alors : pgcd (a,b) = pgcd (b,r₁)
et la division euclidienne de b par r₁ s’écrit : b = r₁ x q2 + r2 avec 0 ≤ r2 1

Soit r₂ = 0 auquel cas r₁ \b et alors pgcd (b,r₁) = r₁ d'où pgcd (a,b) = r₁
Soit r₂ ≠ 0 On a alors : pgcd (b,r₁) = pgcd (r₁, r₂)
et la division euclidienne de r₁ par r₂ s’écrit : r₁ = r₂ x q₃ +r₃ avec 0 ≤ r₃2

On construit ainsi une suite (rn) d’entiers naturels.
Avec pour tout n : rn+1 + rn , donc cette suite est strictement décroissante.
Or une suite strictement décroissante d’entiers naturels est obligatoirement finie.

Par conséquent, la suite s’arrête à un rang p, rang pour lequel on a donc : r_p = 0
D'où r_p −1 \ r_p −2 et donc pgdc (r_p −2, r_p −1) = r_p-1

Par cette suite de divisions euclidiennes on obtient donc le pgcd qui est le dernier reste non nul.
Cette procédure de recherche du pgcd est appelée algorithme d’Euclide.

D’où :

 

Théorème de l'algorithme d'Euclide :

Soient a et b deux entiers naturels non nuls.
Si b divise a alors pgcd (a,b) = b
Sinon pgcd (a,b) est le dernier reste non nul
dans les divisons euclidiennes successives du diviseur par le reste.

D’où :

Méthode n° 3 :

- effectuer les divisions successives de l’algorithme d’Euclide.
- le dernier reste non nul est le pgcd de a et de b.

Remarques :

1) Que l’on divise a par b ou b par a n’a aucune importance.
En effet, si a Et donc dans l’algorithme d’Euclide la division suivante est : b divisé par a.
Autant donc toujours diviser dès le départ le plus grand nombre par le plus petit, étant donné de plus que : pgcd (a,b) = pgcd (b,a)

2) Si une des divisions a un reste égal à 1 alors pgcd (a,b) = 1 car le reste suivant strictement inférieur à 1 ne peut être que nul.

Application : reprenons l’exemple de a = 150 et b = 120.
150 = 120 x 1 + 30
120 = 30 x 4 + 0
Donc : pgcd (150 , 120) = 30

 

4/ Nombres premiers entre eux

Définition :

Soient a et b deux entiers relatifs non nuls.
a et b sont dits premiers entre eux si pgcd (a,b) = 1

Remarques :

1) deux nombres premiers entre eux ont donc 1 pour seul diviseur commun.
2) si a est un nombre premier et que a ne divise pas b alors a et b sont premiers entre eux.

 

Théorème de Bézout :

a et b sont premiers entre eux
si et seulement si
il existe u et v entiers relatifs tels que : a x u + b x v = 1

Remarques :

1) Le couple (u,v) n’est pas unique.

2) Ce couple peut être trouvé en « remontant » les divisons de l’algorithme d’Euclide.
Cette technique sera vue dans le module sur les équations diophantiennes.

3) Selon les livres, les professeurs et les moments de la scolarité, le théorème de Bézout peut comporter un contenu différent. La version qui en est donnée ici suffit pour la terminale.

Démonstration du théorème de Bézout :

Sens direct : supposons a et b premiers entre eux.
E l’ensemble des nombres naturels non nuls s’écrivant a x u + b x v avec u et v entiers relatifs
n’est pas vide donc il admet un plus petit élément n. n = a x u' + b x v'
La division euclidienne de a par n s’écrit : a = b x q + r avec : 0 ≤ r Donc : a = (a x u' + b x v') x q + r d'où r = a(1 - u' x q) + b(-v' x q)

r est donc un entier naturel de la forme a x u + b x v

Or r Par conséquent r = 0 et n divise donc a.

De même on peut démontrer que n divise b.
n est donc un diviseur commun à a et b, or 1 étant le seul : n = 1

Et donc 1 peut s’écrire : 1 = a x u' + b x v'
avec u’ et v’ entiers relatifs.

Sens réciproque : supposons que 1 s’écrive : 1 = a x u + b x v
* Si d entier naturel, diviseur commun à a et b,
d divise alors toute combinaison linéaire de a et de b
donc : d\ a x u + b x v
D’où d\1 or le seul diviseur entier naturel de 1 est 1
donc d = 1.
a et b possèdent donc un seul diviseur commun qui est 1, ils sont premiers entre eux.

Soient a et b deux entiers relatifs non nuls.

Propriété n° 1

Quel que soit k, entier naturel non nul : si pgcd (a,b) = 1 alors pgcd (ka,kb) = k
si k est un relatif non nul : (ka,kb) = lkl

Démonstration :

k divise ka et kb donc k est un diviseur commun à ka et kb.
D’après le théorème de Bézout : il existe u et v entiers relatifs tels que : a x u + b x v = 1

Donc : ka x u + kb x v = k
Si d est un entier naturel diviseur commun à ka et kb, d divise donc k.
d divise k avec k non nul donc d ≤ k

k est donc le plus grand diviseur commun à ka et kb.

 

Propriété n° 2

pgcd (a,b) = d
⇔
il existe a’ et b’ entiers relatifs tels que : a = da’ et b = db’ avec pgcd (a',b') = 1

Démonstration :

Sens direct : soit d = pgcd (a,b)
d \ a donc il existe a’ entier relatif tel que : a = da’
De même, b peut s’écrire b = db’
Soit d diviseur commun à a’ et b’
Alors : a’ = d’a’’ et b’ = d’b’’

Donc a = (dd’)a’’ et b = (dd’)b’’et dd’ est donc un diviseur commun à a et b.
Si d’ > 1 alors dd’ > d ce qui est absurde car d est le plus grand diviseur commun à a et b.
Donc d' Le seul diviseur commun à a’ et b’ est 1 donc ils sont premiers entre eux.

Sens réciproque :
pgcd (a,b) = pgcd (da',db') = d
D’après la propriété n°1.

Remarques :

1) Cette propriété est très utile pour ramener la résolution de problèmes au cas plus simple de nombres premiers entre eux.

2) Elle peut également être utilisée pour trouver le PGCD de deux nombres écrits sous la forme d’un produit de deux facteurs.

Exemple : 55 = 5 x 11 et 65 = 5 x 13.
11 et 13 sont premiers entre eux donc d’après la réciproque le PGCD de 55 et 65 est 5.

Propriété n° 1 ( étendue )
Quel que soit k, entier naturel non nul : pgcd (ka,kb) = kpgcd (a,b)
si k est un relatif non nul : pgcd (ka,kb) = lklpgcd (a,b)
Cette propriété est particulièrement utile pour simplifier la recherche du pgcd de deux grands nombres ayant un diviseur commun évident.

Démonstration :

D’après la propriété n°2 :
* Si d = pgcd (a,b) alors a et b peuvent s’écrire : a = da’ et b = db’ avec pgcd (a',b') = 1
D’où : pgcd (ka,kb) = pgcd ((kd)a' , (kd)b') = kd d’après la propriété n°1.

Par conséquent : pgcd (ka , kb) = kpgcd (a,b)

 

Propriété n° 3 : ( extension du sens direct du Théorème de Bézout )

Si pgcd (a,b) = d alors il existe u et v entiers relatifs tels que : a x u + b x v = d

Démonstration :

D’après la propriété n° 2 :
d = pgcd (a,b) donc a et b peuvent s’écrire : a = da’ et b = db’ avec pgcd (a',b') = 1
D’où d’après le théorème de Bézout : il existe u et v entiers relatifs tels que : a' x u + b' x v = 1br> donc da' x u + db' x v = d Par conséquent d s’écrit : d = a x u + b x v

Peut-on étendre la réciproque du Théorème de Bézout ?
Soit d entier relatif non nul et différent de 1 tel que : a x u + b x v = d , d est-il le pgcd de a et de b ?

Prenons par exemple : a = 6 et a = 4. pgcd (4, 6 ) = 2
On peut écrire : 6 x 2 + 4 x (-2) = 4 alors que 4 n’est pas l pgcd de 4 et 6.
La réciproque est donc fausse, mais…

 

Propriété n° 4 :

Si d entier non nul peut s’écrire d = a x u + b x v avec u et v entiers relatifs alors : pgcd (a,b) divise d.

La démonstration en est évidente.
La contraposée sera utile pour la résolution des équations diophantiennes, à savoir :
« si pgcd (a,b) ne divise pas d alors d ne peut s’écrire sous la forme : d = a x u + b x v »
Nous y reviendrons dans le module concerné.

 

Propriété n° 5 :

Tout diviseur commun à a et b divise le pgcd de a et b.

Démonstration :

D’après Bézout direct étendu , il existe u et v entiers relatifs tels que : pgcd (a,b) = a x u + b x v
Or, si d est un diviseur commun à a et b, il divise toute combinaison linéaire de a et de b.

Donc d divise pgcd (a,b)
Et comme réciproquement, tout diviseur de d divise a et b, on en déduit donc que :

Les diviseurs communs à a et b sont les diviseurs du pgcd de a et b.

 

Théorème de Gauss :

soient a, b et c trois entiers relatifs non nuls.
Si a divise bc et a et b premiers entre eux alors a divise c.

Intuitivement ce théorème se comprend assez facilement :
Si a divise bc c’est qu’il peut être vu comme le produit de deux facteurs : l’un divisant b et l’autre divisant c.

Le premier facteur étant donc un diviseur commun à a et b et le second, un facteur commun à a et c.

Si a et b sont premiers entre eux, leur seul facteur commun est 1 et donc le second facteur vaut a.
a divise alors c.

Démonstration rigoureuse :

pgcd (ac , bc) = lcl pgcd (a,b) = lcl
Or a \ bc et a \ ac donc a est un diviseur commun à ac et bc.
Il divise donc leur pgcd qui est lcl

D’où : a \ c.

Remarque :

Ce théorème sera en particulier très utile pour résoudre les équations diophantiennes.