[PDF] PGCD et PPCM de deux entiers :

View - Download PGCD et PPCM de deux entiers :

Previous PDF

Next PDF

PGCD et PPCM de deux entiers :

Table des matières

IPlus grand commun diviseur de deux entiers :. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

IIDéterminationdu PGCD par l"algorithmed"Euclide. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

IIIEntierspremiers entre eux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

IVThéorème de Gauss et applications:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

VPetit théorème de Fermat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

VIPlus petit commun multiplede deux entiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

I Plus grand commun diviseur de deux entiers :

Définition :

Soientaetbdeux entiers naturels non nuls. On noteD(a) l"ensemble des diviseurs dea.

Le plusgrandélémentdeD(a)D(b), ensembledesdiviseurspositifscommunsàaet àb,est leplusgrand

commun diviseurdeaetb, ou encore PGCD deaetb. On le note pgcd(a;b) ou PGCD(a;b)

Casparticuliers :

pgcd(a;a)a;pgcd(1; a)=1 ; pgcd(a; 0)apouranon nul. Remarque :le PGCD de deux entiers naturels est un entier au moins égal à 1.

Propriété :

Soientaetbdeux entiers naturels au moins égaux à 2. Le PGCD deaetbest égal au produitdesfacteurspremierscommunsdeaet deb,avec pourchacund"eux, l"exposant le plus petit de ceux qu"il a dansaet dansb.

Démonstration ::

Soitdle PGCD deaet deb, naturels supérieurs ou égaux à 2. Commeddivisea, sa décomposition en facteurs

premiers est formée des facteurs premiers deaavec un exposant au plus égal à celui qu"ils sont dans dansa. De

même pourb.

Ainsi, la décomposition dedcomprend les facteurs premiers àaet àb, avec un exposant au plus égal au plus

petit des exposants dans les décompositions deaet deb.

Commedest le plus grand des diviseurs communs, ces exposants sont égaux au plus petit de ceux se trouvant

dans la décompositiondeaet deb.

Exemple :cherchons le PGCD de 700 et de 90.

Remarque :Soienaetbdes entiers relatifs non nuls simultanément. CommeD(a)D(a), le PGCD deaetbest le même que celui deaet deb. 1

TABLE DES MATIÈRES

On peut ainsi se restreindre aux entiers naturels.

Propriété :

1. Siadiviseb, alors pgcd(a;b)a

2. Propriété fondamentale :Soitanon nul tel queabqr. (division euclidienne deaparb).

Alors :D(a)D(b)D(b)D(r) et pgcd(a;b)=pgcd(b;r).

Démonstration ::

1. Siadiviseb, tout diviseur deaest un diviseur deb. Par conséquent :D(a)D(b)D(a) et le plus grand

élément deD(a) esta.

2. Pourdémontrerl"égalitédesdeuxensemblesED(a)D(b) etFD(b)D(r), onmontrequeEestinclus

dansFet queFest inclus dansE. SoitdE. Alorsddiviseb, doncddivisebqet commeddivisea,ddiviseabqr, doncdF. SoitdF.ddivisebdoncbq. Commeddiviser,ddivisebqradoncdE.

Les ensemblesEetFsont égaux, donc ils ont le même plus grand élément. Ainsi : pgcd(a;b)=pgcd(b;r).

Exercice 1 Déterminer le PGCD de 1960 et de 34300.

On a : 1960235172et 34300225273.

On en déduit que PGCD(1960 ; 34300)225172980

Exercice 2 Déterminer le PGCD de deux entiers dépendant den: Déterminer,selon les valeurs den, le PGCD deA2n1 et deBn5. Méthode :on utilisela propriétéfondamentale. Pouréliminern,oncalculeA2B.A2B2n12(n5)11doncA2B11.PGCD(A;B)=PGCD(B; 11). Comme 11 est un nombre premier, le PGCD deBet de 11 ne peut valoir que 1 ou 11.

PGCD(B; 11)11 si et seulement si 11 diviseB.

PGCD(B; 11)11B0(11)n50(11)n5(11).

On en conclut que le PGCD deAetBest 11 lorsquenest congru à 5 modulo 11 et à 1 dans les autres cas.

Exercice 3 Égalité de deux PGCD :

Soientaetbdeux entiers naturels non nuls. Soientx7a5bety4a3b. Montrer que le PGCD dexet deyest égal au PGCD deaet deb. Premièreméthode:7a5b(4a3b)(3a2b)doncpgcd(7a5b; 4a3b)=pgcd(4a3b; 3a2b).

3a2b2(ab)adonc pgcd(4a3b; 3a2b)=pgcd(ab;a)=pgcd(a;b)=pgcd(a;b).

On en déduit que : pgcd(x;y)=pgcd(a;b).

Deuxième méthode :Soitdle PGCD deaetb. Alorsddiviseaetb, donc 7a5bet 4a3bdoncd divise le PGCDddexety. Commeddivise 7a5bet 4a3b,ddivise 7(4a3b)4(7a5b)b. De même,ddivise 3(7a

Page 2/

10

TABLE DES MATIÈRES

5b)5(4a3b)a. Puisqueddiviseaetb, il divise leur PGCDd.

ddivisedetddivised. Doncdd. II Détermination du PGCD par l"algorithme d"Euclide

(Cet algorithme,c"est-à-dire une suite d"instructions,fut décrit par Euclide au IIIıème siècle avant JC)

Description de l"algorithme d"Euclide

Soientaetbdeux entiers naturels non nuls, avecab.

On diviseaparb.abq1r1, avec 0r1b.

Sir10, alors pgcd(a;b)bpuisquebdivisea.

Sir10, pgcd(a;b)=pgcd(b;r1). On effectue alors la division debparr1.

On a :br1q2r2, avec 0r2r1.

Sir20, alors pgcd(a;b)=pgcd(b;r1)r1.

Sir20, pgcd(b;r1)=pgcd(r1;r2).

Oncontinuela suitede divisionseuclidiennesendivisantunreste par lerestesuivant.Onobtientunesuite de restesr1,r2, ...rn, avecr1r2r3 0. Comme ce sont des entiers, il existe un reste qui est nul. Notonsrnle dernier reste non nul. Alors : pgcd(a;b)=pgcd(b;r1)=pgcd(r1;r2)=...=pgcd(rn1;rn)rn carrndivisern1

Propriété :

Le PGCD de deux entiers non nulsaetbtels quebne divise pasaest le dernier reste non nul de la suite des divisions de l"algorithmed"Euclide.

Corollaires :

1. L"ensemble des diviseurs communs à deux entiersaetbest l"ensemble des diviseurs de leur PGCD.

2. Soitaetbdeux entiers non nuls. Sikest un entier naturel non nul, pgcd (ka;kb)kpgcd (a;b).

Démonstration :

1.D(a)D(b)D(b)D(r1)D(r1)D(r2)D(rn)D(0)D(rn)D(d) puisquedrn.

2. On notedle PGCD deaetbetdcelui dekaetkb.

Commeddiviseaetb,kddivisekaetkb, donckddivise leur PGCDd, donckddivised. d k(kd). (kentier) d divisekaetkb, donckkddivisekaetkb; on en déduit quekddiviseaetb, donc leur PGCDd.kd divised, donck1 etdkd.

Page 3/

10

TABLE DES MATIÈRES

III Entiers premiers entre eux

Définition :

Deux entiers sont premiers entre eux lorsque leur PGCD est égal à 1.

Remarques:

Cela revient à dire que leurs seuls diviseurs sont -1 et 1.

Il ne faut pas confondre nombre premiers et nombres premiersentre eux. Par exemple, 15 et 22 sont pre-

miers entre eux, mais pas premiers.

Propriété :

Soientaetbdes naturels non nuls etdun diviseur commun deaetb. On poseadaetbdb. Le PGCD deaetbestdsi et seulement siaetbsont premiers entre eux.

Démonstration::

Sidest le PGCD deaetb, soitadaetbdb. On en déduit que : d=pgcd(a;b)=pgcd(da;db)=d pgcd(a;b). Commedest non nul, pgcd(a;b)1 etaetbsont premiers entre eux.

Si pgcd(a;b)1, alors pgcd(a;b)dpgcd(a;b)d

Exercice 1 Déterminer le PGCD de 8870 et de 3120. Réponse :on utilise l"algorithmed"Euclide : on trouve un PGCD égal à 10. Exercice 2 Écrire l"algorithmed"Euclide pour une calculatrice.

Solution:

- Entreraetb - Tant queb0 (début de la boucle) -E?a b? q -abqr -baLe nouveau dividende estb. -rb(Le nouveau diviseur estr) - Fin Tant que - Affichera(C"est le dernier reste non nul, donc le PGCD cherché) Exercice 3 Déterminer les naturels dont la somme est 600 et dont le PGCD est 50.

Solution:

On chercheaetbtels que :ab600 et pgcd(a;b)50.

Soientaetbles entiers tels que :a50aetb50b; alorsaetbsont premiers entre eux. ab60050a50b60050(ab)600ab12.

On cherche tous les couples d"entiers naturels vérifiant cette relation et on ne garde que les couples

Page 4/

10

TABLE DES MATIÈRES

d"entiers premiers entre eux. (1 ; 11) ; (5 ; 7) ; (7 ; 5) et (11 ; 1). On en déduit les couples solutions: (50 ; 150) ; (250 ; 350) ; (350 ; 250) et (550 ; 50).

Théorème deBézout :

Deux entiersaetbsont premiers entre eux si, et seulement si, il existe deux entiers relatifsuetvtels que

aubv1.

Démonstration ::

On supposeaetbpremiers entre eux, donc pgcd(a;b)1. L"un des deux nombres est non nul, par exemple a. On considère l"ensemble des nombres entiers de la formeaubv, avecuetventiers. Cet ensemble n"est pas vide, puisqu"il contient par exemplea, (avecu1 etv0).

Si E contienta, il contientaet l"un de ces deux entiers est positifs, donc E contient un entier positif.

Soitβle plus petit de ces entiers positifs de E. ; il existeu0etv0tels que :βau0bv0. La division euclidienne deaparβs"écrit :aβqr, avec 0rβd"où raβqa(au0bv0)qa(1u0q)b(v0q). Ainsi,rappartient à E puisqu"il est de la formeaubv avecuetventiers. Par définition deβqui est le plus petit entier positif de E, on a :r0.

On en déduit :aβq, doncβdivisea.

On montre de même queβdiviseb, doncβ1 puisque le PGCD deaet debest 1. Par conséquent, il existe

bien deux entiersu0etv0tels queau0bv01.

Réciproque :

S"il existe des entiersuetvtels queaubv1, alors, sidest le PGCD deaetb, il diviseaetb, doncaubv donc 1 ; par conséquent,d1 etaetbsont premiers entre eux.

Exemples:

1. 5 et 12 sont premiers entre eux car 7(5)3121.

2. (n1)n1 doncnetn1 sont toujours premiers entre eux.

Corollaire

Sidest le PGCD de deux entiersaetb, alors il existe des entiersuetvtels queaubvd.

Démonstration::

adaetbdboùaetbsont premiers entre eux. On applique alors lethéorème de Bézout.

Propriété :

Un nombre premier est premier avec tous les nombres qu"il ne divise pas. Démonstration :: Soitpun nombre premier. Soitaun entier non divisible parp. On notedle PGCD depet a.dvaut 1 oup, puisquepest premier.

Page 5/

10

TABLE DES MATIÈRES

dne peut pas être égal àp, sinonpdiviseraita.

Par conséquent :d1.

Exercice fondamental :

Montrer que les nombres 3920 et 1089sont premiers entre eux et déterminer des entiersuetvtels que

3920u1089v1.

Méthode :on écrit toutes les divisions de l"algorithme d"Euclide ; onreporte alors chaque reste obtenu en

partant de la fin.

On obtient :

392010893653

10896531436

6534361217

43621722

21721081

2121
Par conséquent : le dernier reste non nul est 1, donc les deux nombres sont premiers entre eux.

On a alors :

21721081 (1)

24362172 donc en reportant dans (1) :

217(4362172)1081 d"où 2172174361081 (2)

2176534361. On remplace dans (2) :

(6534361)2174361081 d"où 6532174363251 (3)

4361089653.On remplace dans (3) :

653217(1089653)3251 d"où 65354210893251 (4)

653392010893.On remplace dans (4) :

(392010893)54210893251 soit : 3920542108919511.

Propriété :

Si un entier est premier avec deux entiers, il est entier avecleur produit.

Démonstration :

et des entiersuetvtels queaucv1. On effectue le produit membre à membre. On obtient : (aubv)(aucv)1a2uuacuvabvubcvv1a(auucuvbvu)bc(vv)1. Comme auu cuvbvuetvvsont des entiers, on en déduit queaetbcsont premiers entre eux.

Exemples:

1. 4 est premier avec 9 et avec 35, donc 4 est premier avec 315.

2. Pour toutn,nest premier avecn1 et avecn1, doncnest premier avecn21.

Page 6/

10

TABLE DES MATIÈRES

IV Théorème de Gausset applications:

Théorème

Soienta,betctrois entiers. Siadivise le produitbcet siaest premier avecb, alorsadivisec.

Démonstration ::

Siaest premier avecb, il existeuetvtels que :aubv1. On en déduit :acubcvc.

Or,adiviseacuetbcpar hypothèse, doncadivisec.

Exemple:Soientaetbdeuxentierstelsque5a14b.14 diviseleproduit5a, les entiers14et 5 sontpremiers entre eux, donc 14 divisea.

De même, 5 diviseb.

Corollaires :

1. Si un entier est divisiblepar des entiersaetbpremiersentre eux,alors il est divisiblepar leur produit

ab.

2. Si un entier premier divise un produit de facteursab, alors il divise au moins un des facteursaetb.

Démonstration ::

1. Soitnentier divisible paraetb. Il existe des entiersketktels quenkaetnkbdoncnkakb.

adivise donckb. Commeaetbsont premiers entre eux, on en déduit (d"après le théorèmedeGauss) que

adivisekdonc il existeqtel quekqa. On a alorsnqabetnest divisible parab.

2. Soitpun nombre premier divisantab.

Sipdivisea, alors la conditionest vérifiée.

Supposons quepne divise pasa. Alorsaetpsont premiers entre eux; commepdiviseab, alorspdivise bd"après le théorème de Gauss.

Exercices:

1. Résoudre une équation du typeaxby0 dansZ2.

Exemple :Déterminer les entiersxetytels que 7x5y0.

Cette équation s"écrit 7x 5y. 7 et5 sont premiers entre eux. 7 divise5ydonc 7 diviseyd"après le

théorème de Gauss. Ainsiy7kaveckentier.

En reportant : 7x57kd"oùx5k.

Les solutionssont les couples (5k; 7k) oùkZ.

2. Résoudre une équation du typeaxbycdansZ2, avecaetbpremiers entre eux.

(a) Exemple :Déterminer les entiersxetytels que 5x7y1

Comme 5 et 7 sont premiers entre eux, il existe d"après le théorème de Bezout deux nombresuetv

tels que : 5u7v1. Pour détermineruetv, on peut utiliser l"algorithme d"Euclide ou remarquer que 510771 donc on peut prendreu10 etv 7. Le couple (10 ;7) est une solution particulièrede cette équation.

Alors : 5x7y15x7y510775(x10)7(y7).

5 divise 7(y7); 5 et 7 sont premiers entre eux. D"après le théorème de Gauss, on en déduit que 5

quotesdbs_dbs28.pdfusesText_34

[PDF] conversion notes erasmus

[PDF] correspondance notes lettres

[PDF] conversion notes québec france

[PDF] note sur 20 en gpa

[PDF] tableau de conversion de notes european credit transfer system

[PDF] tableau de conversion des notes

[PDF] b2i adultes ressources

[PDF] b2i adultes greta

[PDF] b2i adultes exercices

[PDF] compétences b2i cm2

[PDF] compétences tice cycle 3 2016

[PDF] compétences tice cycle 2

[PDF] tice programmes 2016

[PDF] b2i nouveaux programmes 2016

[PDF] programmation informatique cycle 3 2016