[PDF] PGCD et PPCM de deux entiers :[PDF] Cinématique des fluides
[PDF] CHAPITRE I TRIGONOMETRIE
[PDF] E = m c2 l 'équation de Poincaré, Einstein et Plan
[PDF] Démonstrations exigibles au bac - Math France
[PDF] SECOND DEGRÉ - Maths-et-tiques
[PDF] SECOND DEGRÉ - Maths-et-tiques
[PDF] Démonstrations combinatoires
[PDF] 1 Démonstrations du formulaire de trigonométrie -
[PDF] Primitives et intégrales
[PDF] Charlemagne sur Internet - Statim
[PDF] ROC - Math France
[PDF] III- Raisonnement par récurrence
[PDF] Raisonnement par récurrence - Math France
[PDF] Planche no 2 Raisonnement par récurrence : corrigé
![[PDF] I PGCD et PPCM de deux nombres entiers - My MATHS SPACE](https://pdfprof.com/Listes/16/25379-16pgcdppcm_11_12.pdf.pdf.jpg "[PDF] I PGCD et PPCM de deux nombres entiers - My MATHS SPACE")
TS (spécialité)PGCD - PPCM - Gauss et Bézout2011-2012 I PGCD et PPCM de deux nombres entiers
I.1 Préliminaires
?PréliminairesOn a 282 = 14×19 + 16
Les formulations suivantes sont-elles vraies ou fausses? Dans la division euclidienne de 282 par 14, le quotient est 19et le reste est 16. Si un entierddivise 282, alorsddivise 14 et 16. Tout diviseur commun de 282 et 14 est un diviseur de 16. Le reste dans la division euclidienne de 282 par 14 est 2. Les diviseurs communs de 282 et 14 sont 1 et 2. ?Préliminaires Les formulations suivantes sont-elles vraies ou fausses? Deux nombres premiers distincts n"ont pas de diviseurs communs. L"ensemble des diviseurs communs à deux entiers non nuls estnon vide et majoré. Soitnun entier naturel non nul. Un diviseur commun à 2n-1 etn+ 3 divise 7. 7 est un diviseur commun à 2n-1 etn+ 3 lorsquenest congru à 4 modulo 7. Les multiples communs à 6 et à 14 sont des multiples de 6×14. L"ensemble des multiples communs à deux entiers naturels non nuls est non vide et minoré. I.2 Définition du PGCD de deux entiers relatifs non nuls aetbsont deux entiers relatifs non nuls.Définition 1L"ensemble des diviseurs communs àaetbadmetun plus grand élémentDappeléPGCDdea
et deb. On le noteD=PGCD(a;b)Détermination pratique du PGCD :
A la main, lorsque les nombres ne sont pas trop grands. ex : PGCD(420;1386)?A la calculatrice, l"instruction existe seulement pour desmodèles "sophistiqués". Pour les autres, il faut écrire
un programme qui repose sur l"algorithme d"Euclide (voir plus loin) Avec un ordinateur, utiliser un tableur et encore l"algorithme d"Euclide.I.3 Nombres premiers entre eux
Définition 2On dit que deux entiers relatifs non nulsaetbsontpremiers entre euxlorsque leur PGCD est égal
à 1. (on dit aussi "étrangers")
Résultat connu : Soitaetbdeux entiers relatifs non nuls. La fractiona best irréductible lorsqueaetbsont premiers entre eux.My Maths Space1 sur 5
TS (spécialité)PGCD - PPCM - Gauss et Bézout2011-2012I.4 Propriétés du PGCD
Soientaetbdeux entiers relatifs,a?= 0.
Propriété 1:
PGCD(a,0)=aet PGCD(a,1)=1;
PGCD(a,b)=PGCD(|a|,|b|);conséquence : On peut limiter l"étude du PGCD(a,b) au cas oùaetbsont des
entiers naturels.Sibdivisea, PGCD(a,b)=|b|;
Sibest premier et ne divise pasa, PGCD(a,b)=1 .I.5 Algorithme d"Euclide
1. Procédé
Théorème 1Soitaetbdeux entiers naturels non nuls. La suite des divisions euclidiennes :deaparb:a=bq0+r0;
debparr0(sir0?= 0) :b=r0q1+r1
der0parr1(sir1?= 0) :r0=r1q1+r2
dern-1parrn(sirn?= 0) :rn-1=rnqn+rn+1finit par s"arrêter, un des restesriétant nul. ledernier reste non nulest alors lePGCDdeaet deb.Exemple 1Calculer PGCD(1958;4539)
2. Exploitation numérique
?A l"aide d"untableur , programmer la recherche du PGCD de deux entiers naturels non nuls par l"algorithme
d"Euclide.?A l"aide du logiciel de codages d"algtorithmesAlgoBox , programmer la recherche du PGCD de deux nombres
entiers naturels non nuls.I.6 PPCM de deux entiers relatifs non nuls
aetbsont deux entiers relatifs non nuls.Définition 3L"ensemble des multiples communs strictement positifs deaet debadmetun plus petit élément
MappeléPPCMdeaet deb. On noteM=PPCM(a;b)
My Maths Space2 sur 5
TS (spécialité)PGCD - PPCM - Gauss et Bézout2011-2012Résultat connu : Le plus petit dénominateur commun de deux fractions est le PPCM des dénominateurs.
II Théorèmes de Bézout et théorème de GaussII.1 Théorème de Bézout
Théorème 2Soitaetbdeux entiers relatifs non nuls etDleur PGCD. Il existe deux entiers relatifsuetvtels
queau+bv=D. (Égalité de Bézout)?La démonstration s"appuie sur l"étude de l"ensembleBdes entiers naturels non nuls de la formeam+bn(avec
metndansZ).Découpage de la démonstration :
?Prouver queBcontient au moins un élément (non vide) et l"on notedle plus petit élément deB.
?Prouver queD?d. ?Prouver queddiviseaetddiviseb. ?Conclure.Propriété 2(
Importantes )
Tout diviseur commun àaetbdivise leur PGCD.
(L"ensemble des diviseurs communs àaetbest l"ensemble des diviseurs du PGCD) aetbsont premiers entre eux?il existe deux entiers relatifsuetvtels queau+bv= 1.L"équationax+by=d(dentier fixé non nul) admet des solutions entières si et seulement sidest un
multiple deD(d=kD) .a,betkdes entiers naturels non nuls :
PGCD(ka,kb)=k×PGCD(a,b) .
EXERCICE 1Montrer que, pour toutn?Z, 2n+1 et 3n+1 sont premiers entre eux. Même question avec 3n-2
et 5n-3.My Maths Space3 sur 5
TS (spécialité)PGCD - PPCM - Gauss et Bézout2011-2012II.2 Théorème de Gauss
Théorème 3Soita,betc, trois entiers relatifs non nuls. Siadivisebcet siaetbsont premiers entre eux, alors
adivisecEn d"autres termes :
a|bc
PGCD(a;b) = 1?
=?a|c EXERCICE 2Montrer que siaetbdivise un entiercet queaetbsont premiers entre eux alorsabdivisec.III Applications des deux théorèmes
III.1Propriétés du PGCD et du PPCM
aetbdeux entiers relatifs non nuls,Dleur PGCD etMleur PPCM.1. Il existe deux entiers
a?etb?premiers entre euxtels que : a=Da?etb=Db?(En d"autres termes, lorsque l"on divise deux nombres par leur PGCD, on obtient des quotients premiers entre eux)