[PDF] I PGCD et PPCM de deux nombres entiers

View - Download I PGCD et PPCM de deux nombres entiers

Previous PDF

Next PDF

TS (spécialité)PGCD - PPCM - Gauss et Bézout2011-2012

I PGCD et PPCM de deux nombres entiers

I.1 Préliminaires

?Préliminaires

On 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-2012

I.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-2012

Ré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 Gauss

II.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-2012

II.2 Théorème de Gauss

Théorème 3Soita,betc, trois entiers relatifs non nuls. Siadivisebcet siaetbsont premiers entre eux, alors

adivisec

En 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.1

Proprié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)

2. Avec les notations précédentes, on a :

M=Da?b?=ab?=a?betMD=ab

?Prouver queDa?b?est un multiple commun àaet àb. ?Prouver queM Dest un entier, divisible para?et parb?. Conclure queMest un multiple deDa?b?à l"aide d"une conséquence du théorème de Gauss (exercice 2) ?Déduire de ce qui précéde queM=Da?b?et les autres égalités.

3. L"ensemble des diviseurs communs àaetbest l"ensemble des diviseurs deD.

4. L"ensemble des multiples communs àaetbest l"ensemble des multiples deM.

My Maths Space4 sur 5

TS (spécialité)PGCD - PPCM - Gauss et Bézout2011-2012 III.2Équation Diophantienneax+by=k×PGCD(a;b) Il s"agit de déterminer tous les couples (x;y) tels que :ax+by=k×PGCD(a;b).

A partir d"un exemple ...

On considère l"équation

(E) : 17x-33y= 1

1. Déterminer une solution particulière de (E).

2. En déduire une solution particulière de (E1) : 17x-33y= 5.

3. Résoudre (E1) dansZ×Z. (c"est à dire trouver tous les couples deZ×ZvérifiantE1)

My Maths Space5 sur 5

quotesdbs_dbs29.pdfusesText_35

[PDF] CHAPITRE I TRIGONOMETRIE

[PDF] E = m c2 l équation de Poincaré, Einstein et Planck

[PDF] SECOND DEGRÉ - Maths-et-tiques

[PDF] Démonstrations combinatoires

[PDF] 1 Démonstrations du formulaire de trigonométrie - Free

[PDF] Primitives et intégrales

[PDF] Charlemagne sur Internet - Statim

[PDF] III- Raisonnement par récurrence

[PDF] Raisonnement par récurrence - Math France

[PDF] Planche no 2 Raisonnement par récurrence : corrigé - Math France

[PDF] Planche no 2 Raisonnement par récurrence : corrigé - Math France

[PDF] RÉUSSIR L 'ÉPREUVE DE PHYSIQUE Baccalauréat 2015 - MENFP

[PDF] Intégration et primitives - Lycée d 'Adultes

[PDF] Démonstration de la formule de conjugaison pour les dioptres

[PDF] La théorie de la relativité générale - UdPPC