CHAPITRE
Accueil
Exercices
Fiches de cours
0 pts
Imprimer
Formules et Théorèmes
Démonstrations
À savoir refaire
1
Divisibilité
2
Division euclidienne et congruence
3
PGCD
4
Nombres premiers
3
PGCD
A
Définitions, propriétés et algorithme d’Euclide
Définition
Plus grand commun diviseur
Le plus grand diviseur commun (PGCD) de deux nombres entiers
a
a
a
et
b
b
b
est le plus grand nombre entier qui divise simultanément
a
a
a
et
b
b
b
.
Le PGCD de
a
a
a
et de
b
b
b
est noté
PGCD(a;b)
\text{PGCD(a;b)}
PGCD(a;b)
.
Exemple
Les diviseurs de
45
45
45
sont
1
1
1
;
3
3
3
,
5
5
5
;
9
9
9
;
15
15
15
et
45
45
45
.
Les diviseurs de
60
60
60
sont
1
1
1
;
2
2
2
;
3
3
3
;
4
4
4
;
5
5
5
;
6
6
6
;
10
10
10
;
15
15
15
;
20
20
20
;
30
30
30
et
60
60
60
.
Donc
PGCD
(
45
;
60
)
=
15
\text{PGCD}(45;60)=15
PGCD
(
45
;
60
)
=
15
.
Propriété
PGCD
Soient
a
a
a
,
b
b
b
et
c
c
c
des entiers naturels. On a les propriétés suivantes :
PGCD
(
a
;
0
)
=
a
\text{PGCD}(a;0)=a
PGCD
(
a
;
0
)
=
a
;
PGCD
(
a
;
1
)
=
1
\text{PGCD}(a;1)=1
PGCD
(
a
;
1
)
=
1
;
PGCD
(
a
c
;
b
c
)
=
c
×
PGCD
(
a
;
b
)
\text{PGCD}(ac\ ;bc)=c \times \text{PGCD}(a;b)
PGCD
(
a
c
;
b
c
)
=
c
×
PGCD
(
a
;
b
)
;
Si
a
∣
b
a \mid b
a
∣
b
, alors
PGCD
(
a
;
b
)
=
a
\text{PGCD}(a;b)=a
PGCD
(
a
;
b
)
=
a
.
Propriété
Propriété de l’algorithme d’Euclide
Soient
a
a
a
et
b
b
b
deux entiers naturels non nuls. Soit
r
r
r
le reste de la division euclidienne de
a
a
a
par
b
b
b
. Alors :
PGCD
(
a
;
b
)
=
PGCD
(
b
;
r
)
\text{PGCD}(a;b)=\text{PGCD}(b;r)
PGCD
(
a
;
b
)
=
PGCD
(
b
;
r
)
.
Exemple
Méthode de l’algorithme d’Euclide pour trouver le PGCD de deux nombres
Pour trouver
PGCD
(
510
;
238
)
\text{PGCD}(510;238)
PGCD
(
510
;
238
)
:
on effectue la division euclidienne de
510
510
510
par
238
238
238
:
510
=
238
×
1
+
272
510 = 238 \times 1 + 272
510
=
238
×
1
+
272
.
Donc
PGCD
(
510
;
238
)
=
PGCD
(
238
;
272
)
=
PGCD
(
272
;
238
)
\text{PGCD}(510;238)=\text{PGCD}(238;272)=\text{PGCD}(272;238)
PGCD
(
510
;
238
)
=
PGCD
(
238
;
272
)
=
PGCD
(
272
;
238
)
.
On réitère l’opération :
272
=
238
×
1
+
34
272 =238 \times 1 + 34
272
=
238
×
1
+
34
238
=
34
×
7
+
0
238=34 \times 7+0
238
=
34
×
7
+
0
Donc
PGCD
(
510
;
238
)
=
PGCD
(
272
;
238
)
=
PGCD
(
238
;
34
)
\text{PGCD}(510;238)=\text{PGCD}(272;238)=\text{PGCD}(238;34)
PGCD
(
510
;
238
)
=
PGCD
(
272
;
238
)
=
PGCD
(
238
;
34
)
.
Or
238
238
238
divise
34
34
34
, donc d’après 4),
PGCD
(
238
;
34
)
=
34
\text{PGCD}(238;34)=34
PGCD
(
238
;
34
)
=
34
.
Ainsi,
PGCD
(
510
;
238
)
=
34
\text{PGCD}(510;238)=34
PGCD
(
510
;
238
)
=
34
.
B
Théorème de Gauss et de Bézout
Définition
Nombres premiers entre eux
Deux nombres entiers naturels sont dits premiers entre eux si leur PGCD vaut
1
1
1
.
Théorème
Identité de Bézout
Soient
a
a
a
et
b
b
b
deux entiers naturels et
c
=
PGCD
(
a
;
b
)
c= \text{PGCD}(a;b)
c
=
PGCD
(
a
;
b
)
.
Il existe
α
\alpha
α
et
β
\beta
β
entiers relatifs tels que :
α
a
+
β
b
=
c
\alpha a + \beta b = c
α
a
+
β
b
=
c
.
Théorème
Théorème de Bézout
a
a
a
et
b
b
b
sont premiers entre eux si et seulement s’il existe deux entiers relatifs
α
\alpha
α
et
β
\beta
β
tels que :
α
a
+
β
b
=
1
\alpha a+\beta b =1
α
a
+
β
b
=
1
.
Exemple
Démontrons que pour entier naturel
n
n
n
,
2
n
+
1
2n+1
2
n
+
1
et
9
n
+
4
9n+4
9
n
+
4
sont premiers entre eux.
On cherche
a
a
a
et
b
b
b
tels que
a
(
2
n
+
1
)
+
b
(
9
n
+
4
)
=
1
a(2n+1) + b(9n+4)=1
a
(
2
n
+
1
)
+
b
(
9
n
+
4
)
=
1
, ce qui s'écrit aussi
(
2
a
+
9
b
)
n
+
(
a
+
4
b
)
=
1
(2a+9b)n + (a+4b)=1
(
2
a
+
9
b
)
n
+
(
a
+
4
b
)
=
1
.
2
a
+
9
b
=
0
2a+9b=0
2
a
+
9
b
=
0
car le terme de droite est indépendant de
n
n
n
.
On peut choisir
a
=
9
a=9
a
=
9
,
b
=
−
2
b=-2
b
=
−
2
(car on voit facilement que
2
×
9
+
9
×
(
−
2
)
=
0
2\times 9+9\times (-2)=0
2
×
9
+
9
×
(
−
2
)
=
0
).
On a alors
a
(
2
n
+
1
)
+
b
(
9
n
+
4
)
=
1
a(2n+1) + b(9n+4)=1
a
(
2
n
+
1
)
+
b
(
9
n
+
4
)
=
1
.
Donc la proposition est bien vérifiée.
Théorème
Théorème de Gauss
Soient trois entiers naturels
a
a
a
,
b
b
b
,
c
c
c
tels que
a
∣
b
c
a \mid bc
a
∣
b
c
et
a
a
a
,
b
b
b
premiers entre eux.
Alors
a
∣
c
a \mid c
a
∣
c
.
Remarque
Le théorème de Gauss permet de résoudre des équations diophantiennes, c'est-à-dire de la forme :
a
x
+
b
y
=
c
ax + by =c
a
x
+
b
y
=
c
.
(voir les exercices À savoir refaire).
M'inscrire
Me Connecter
Niveau 3ème >
Français
Histoire
Géographie
Mathématiques
SVT
Physique-Chimie
Espagnol
Mentions légales
Mes enfants
Fermer
6ème
5ème
4ème
3ème
2nde
Première
Terminale
Mon Profil
remplacer
Nom d'utilisateur
Prénom
Nom
Date de naissance
Niveau
6ème
5ème
4ème
3ème
2nde
Première
Terminale
Email
Email des Parents
Enregistrer
Changer mon mot de passe
Mon Profil
remplacer
Prénom
Nom
Matière
Allemand
Anglais
Arts plastiques
Espagnol
Français
Histoire-Géographie
Mathématiques
Musique
Philosophie
Physique-Chimie
SES
SVT
Email
Enregistrer
Changer mon mot de passe
Mon Profil
remplacer
Prénom
Nom
Email
Enregistrer
Changer mon mot de passe
Utilisation des cookies
Lors de votre navigation sur ce site, des cookies nécessaires au bon fonctionnement et exemptés de consentement sont déposés.