Chapitre IV PGCD Maths Expertes
Chapitre 4
PGCD
Table des matières
1 Introduction 2
1.1 Dé nitions et propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Algorithme d'Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Nombres premiers entre eux 3
2.1 Dé nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Théorème de Bezout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Théorème et Gauss et applications 5
3.1 Théorème de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
[Link] page 1 Lycée Jean Rostand
Chapitre IV PGCD Maths Expertes
1 Introduction
1.1 Dé nitions et propriétés
Dé nition 1 :
Soient a et b deux entiers relatifs non tous les deux nuls.
L'ensemble des diviseurs communs de a et de b est une partie non vide de Z (elle contient
1) et majorée par le maximum de |a| et |b|.
Cet ensemble admet donc un plus grand élément appelé Plus Grand Commun Diviseur
de a et b noté PGCD(a, b).
Exemple 1 :
Pour a = 105 et b = 42, la liste des diviseurs est respectivement : {1, 3, 5, 7, 15, 21, 35, 105}
et {1, 2, 3, 6, 7, 14, 21, 42}.
Les diviseurs commun sont donc : {1, 3, 7, 21}.
Le plus grand est donc 21. Il s'agit donc du PGCD...
Exercice 1 :
Donner la liste des diviseurs communs de 12 et de 30, en déduire PGCD(12, 30).
Déterminer PGCD(24, 18).
Propriété 1 :
Soient a et b deux entiers relatifs non tous les deux nuls.
# PGCD(a, b) =PGCD(|a|, |b|)
# PGCD(a, b) =PGCD(b, a)
# PGCD(a, 0) = a car 0 est multiple de tout entier.
# Si b divise a, alors PGCD(a, b) = |b|.
Exercice 2 :
Déterminer PGCD(−24, −18).
Déterminer PGCD(0, 82).
Déterminer PGCD(30, 5).
1.2 Algorithme d'Euclide
Dans cette partie, a et b sont deux entiers naturels non nuls tels que b ne divise pas a et a > b.
Exercice 3 : Pour a et b deux entiers, et r le reste de la division euclidienne de a par b.
Montrer que les diviseurs communs de a et b sont les diviseurs communs de b et r.
[Link] page 2 Lycée Jean Rostand
Chapitre IV PGCD Maths Expertes
Théorème 1 :
Algorithme d'Euclide
# On note q et r le quotient et le reste de la division euclidienne de a par b.
On a : PGCD(a, b) =PGCD(b, r).
# La suite des divisions euclidiennes du diviseur par le reste de la division précédente
nit par s'arrêter.
Division de a par b : a = b × q 0 + r0 avec 0 ≤ r0 < b
Division de b par r0 : b = r0 × q1 + r1 avec 0 ≤ r1 < r0 .
Division de r0 par r1 : r0 = r1 × q2 + r2 avec 0 ≤ r2 < r1 .
Division de rn−2 par rn−1 : rn−2 = rn−1 × qn + rn avec 0 ≤ rn−1 < rn .
Division de rn−1 par rn : rn−1 = rn × qn+1 + 0.
On a alors : PGCD(a, b) = rn
Exercice 4 :
Déterminer PGCD(9, 27).
Déterminer PGCD(27, 59).
Déterminer le PGCD de 450 et de 198.
Propriété 2 :
Pour tous entiers naturels a, b et k , on a : PGCD(ka, kb) = k PGCD(a, b).
Exercice 5 :
Déterminer PGCD(240, 180).
Déterminer les entiers naturels inférieurs à 450 tels que PGCD(n, 270) = 45.
Propriété 3 :
Soient a et b deux entiers relatifs non tous les deux nuls.
d est un diviseur commun de a et b si et seulement si d divise PGCD(a, b).
2 Nombres premiers entre eux
2.1 Dé nition
Dé nition 2 :
Soient a et b deux entiers relatifs non nuls.
On dit que a et b sont premiers entre eux si et seulement si PGCD(a, b) = 1.
[Link] page 3 Lycée Jean Rostand
Chapitre IV PGCD Maths Expertes
Exemple 2 :
PGCD(15, 8) = 1 donc 15 et 8 sont premiers entre eux.
∀a ∈ Z, PGCD(a, 1) = 1 donc 1 est premier avec tous les entiers.
Remarques :
# Il ne faut pas confondre nombres premiers entre eux et nombres premiers.
Les nombres 15 et 8 sont premiers entre eux mais aucun des deux n'est premier. Par contre,
deux nombres premiers sont premiers entre eux.
a
# Une fraction irréductible q s'écrit de manière unique sous la forme : q = avec a ∈ Z et
b
b ∈ N∗ et PGCD(a, b) = 1.
Propriété 4 :
Soient a et b deux entiers relatifs non nuls.
# Si d =PGCD(a, b) et a0 et b0 les entiers tels que a = da0 et b = db0 alors a0 et b0 sont
premiers entre eux.
# S'il existe d ∈ N, et a0 et b0 des entiers premiers entre eux tels que a = da0 et b = db0 ,
alors d est le PGCD(a, b).
Exemple 3 :
36 = 12 × 3 et 60 = 12 × 5 et 3 et 5 sont premiers entre eux, donc PGCD(36, 60) = 12.
ab = 300
Exercice 6 : Déterminer l'ensemble des couples (a, b) ∈ N tels que
2
PGCD(a, b) = 5
2.2 Théorème de Bezout
Propriété 5 :
Tout sous-ensemble non vide de N admet un plus petit élément.
Théorème 2 :
Théorème de Bezout
Soit (a, b) un couple d'entiers relatifs non nuls.
a et b sont premiers entre eux si et seulement si il existe deux entiers relatifs u et v tels
que :
au + bv = 1
Exemple 4 :
Pour a = 13 et b = 16, on a 5 × 13 − 4 × 16 = 1, donc a et b sont premiers entre eux.
[Link] page 4 Lycée Jean Rostand
Chapitre IV PGCD Maths Expertes
Exercice 7 :
1. Déterminer deux entiers u et v tels que 29u + 12v = 1.
2. Montrer que pour tout n ∈ Z, les entiers (2n + 1) et (3n + 2) sont premiers entre eux.
Remarques :
# Le théorème de Bezout donne l'existence des entiers u et v mais ne donne par leurs valeurs.
# Il n'y a pas unicité des entiers u et v tels que au + bv = 1.
Théorème 3 :
Identité de Bezout
Pour tout couple (a, b) ∈ (Z∗ )2 , il existe (u, v) ∈ Z2 tel que au + bv =PGCD(a, b).
Exercice 8 : Une équation diophantienne est une équation à coe cients entiers dont on
cherche une solution entière ou rationnelle.
On s'intéresse à l'équation diophantienne 84x + 18y = 6.
Cette équation admet-elle des solutions ?
Propriété 6 :
Soient a, b et c trois entiers tels que a et b ne sont pas simultanément nuls.
L'équation ax + by = c admet des couples d'entiers (x; y) solutions si et seulement si le
nombre c est un multiple de PGCD(a; b).
Exercice 9 :
1. Les équations suivantes ont-elles des solutions entières :
a. 12x + 4y = 32 b. 2x + 6y = 3
2. Après avoir justi é son existence, déterminer un entier a tel que 30a ≡ 1[23].
3 Théorème et Gauss et applications
3.1 Théorème de Gauss
Théorème 4 :
Soient a, b et c trois entiers relatifs non nuls.
Si a divise bc et si a et b sont premiers entre eux, alors a divise c.
Exercice 10 : Déterminer les couples d'entiers relatifs (x; y) tels que 2(x − 1) = 3y
Exercice 11 :
1. Déterminer le PGCD de 65 et 91.
2. Résoudre dans Z2 , l'équation : 65x = 91y .
Exercice 12 : Résoudre l'équation (E) : 4x + 3y = 2
[Link] page 5 Lycée Jean Rostand