La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Sujets
Informations
Publié par | Oliv94 |
Publié le | 17 octobre 2013 |
Nombre de lectures | 1 628 |
Langue | Français |
Extrait
PGCD ET PPCM
I. Plus grand commun diviseur
Par convention, dans ce paragraphe, lorsque l’on parlera de diviseurs d’un entier naturel, il s’agira toujours des
diviseurs positifs.
1. Diviseurs communs à deux entiers positifs
Notation: pour tout entier naturela, on note(a) l’ensemble des diviseurs dea.
Exemple : (14) = (5) = .
Remarques :
· Sia ¹0 alors(ane contient que des entiers naturels inférieurs ou égaux à) a
· Sia 1, alors(a) contient 1 eta
>
·Le plus grand élément de(a) estaet le plus petit est 1
· (1) ne contient que l’élément 1.
Notation : (a;b) est l’ensemble des diviseurs communs àaetb. Ainsi(a;b) =(a)Ç (b)
Exemple : et(7 ; 14) = ..(3 ; 5) =
Remarques :
· (a;b) est un ensemble non vide, il contient toujours 1
· (a;bcar il contient tous les nombres inférieurs ou égaux à) contient un plus grand élément aet àbsia ¹
0 et si b¹0 et inférieur àasib= 0.
Notation: Le plus grand diviseur commun àaetbest noté PGCD
Exemple :a= 24 etb= 18. Trouvez les diviseurs communs deaetbet déduisez en leur PGCD
2. Conséquences immédiates
Prop :
· (a; 0) =(a tout) pouraentier naturel
· Sib/a alors PGCD(a;b) =b
Démonstration :
Page1sur5
Exemple :PGCD(3 ; 12) =
3. Calcul du PGCD
Prop :Effectuons la division euclidienne deaparb, on obtienta=bq+r 0 et r<b.
Alors(a;b) =(b;r).
Dém :
Exemple :Calcul PGCD(202 ; 138) par l’Algorithme d’Euclide
Th :L’ensemble des diviseurs communs àaetbdeux entiers positifs est l’ensemble des diviseurs de leur
PGCD.
ApplicationTrouver les diviseurs communs à 5238 et 2037
Remarque :Tout diviseur deaet debest un diviseur de leur PGCD.
II. Propriétés du PGCD
s premier entre eux lorsque leur PGCD vaut 1
Définition :Deux entiers naturels sont dit
Exemple : premier entre eux. sont2 et 3
Page2sur5
Théorème : a,betddes entiers naturels non nuls. Les trois propriétés suivantes sont équivalentes
1. d PGCD(a;b)
=
2. dest un diviseur deaetbet les quotientsnetn’ tels quea=ndetb=n’dsont premiers entre eux.
3. dest un diviseur deaetbet il existe deux entiers relatifsuetvtels queau+bv=d.
Démonstration :
Exemple :20 est-il le PGCD de 240 et 700 ?
Corollaire :Sid= PGCD(a;b) oùaetbdeux entiers naturel, alors quel que soit l’entier naturel non nuln,
dn= PGCD(na;nb)
Démonstration :
III. Théorème de Bezout.
Théorème de Bezout : aetbdeux entiers naturels non nuls.
aetbpremiers entre eux si et seulement si il existe deux entiers relatifssont uetvtel queau+bv= 1.
Démonstration :
Exemple :montrer quea= 47 etv= 35 sont premier entre eux
Méthode : On utilise l’algorithme d’Euclide et à chaque étape on écrit le reste sous formeau+bv
Page3sur5
IV.
Applications
1. Théorème de Gauss
Théorème de Gauss : a,betctrois entiers naturels non nuls tels quesont a/bcetaetbpremier entre eux
alorsa/c.
Dém :
Exemple :
· un nombre est divisible par 2 et 5. Comme 2 et 5 sont premier entre eux alors il est divisible par 10.
· Par contre 60 est divisible par 4 et 6 mais pas par 24. En effet 4 et 6 ne sont pas premier entre eux.
2. Fractions irréductibles
Définition :Soientaetbdeux entiers avecbnon nul. Lorsqueaetbpremier entre eux, on dit alors que lasont
fractionabest irréductible.
Th :fraction est égale à une fraction irréductible.Toute
Dém :
V. Equationax+by=c
Définition :soienta,b,ctrois entiers, l’équationax+by=c,oùxetysont les inconnues de, est appelée
équation diophantienne.
Th :l’équationax+by=cune solution si et seulement si le PGCD(admet a;b) divisec.
Dém :
Page4sur5
Exemples :Méthode de résolution d’une équation diophantien
a) Résoudre dans, l’équation : E1( x # ∗+ y 1 ).
b) Résoudre dans : E, l’équation1( x # ∗+ y 1 −.
VI. Plus petit commun multiples.
ne
:
Th-Déf: Soientaetbdeux entiers naturels non nuls.Aetbadmettent un plus petit commun multiple positif.
On le note PPCM(a;b).
Th : aetbdeux entiers naturels non nul,d= PGCD(a;b) etm= PPCM(a;b!alors :
1. dm=ab
2. tout multiple commun àaetbest un multiple dem.
Dém :
Th : a,b,mtrios entiers naturels non nul.
Dire quem= PPCM(a;b) équivaut à dire quemest un multiple deaet debtel que les quotients demparaet
bsoient premiers entre eux.
Page5sur5