[PDF] [PDF] PGCD et PPCM de deux entiers :

View - Download [PDF] 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

divisey7. Par conséquent :y75k,kZ, doncy75k. On reporte dans l"équation 5(x10)7(y7). On obtient : 5(x10)75kd"oùx107ksoit

Page 7/

10

TABLE DES MATIÈRES

x107k.

Les solutionssont de la forme (107k;75k),kZ.

(b) Déterminer les entiersxetytels que 5x7y3. Comme510771, on a 5307213. Ainsi, (30 ;21) est une solutionparticulièrede cette

équation.

On trouve alors les solutionsen utilisant la même méthode que ci-dessus.

Les couples solutionssont (307k;215k).

3. Montrer la divisibilité par un produit d"entiers.

Exemple : Montrer queAn(n1)(n2) est divisible par 6 pour toutnentier. n(n1) est divisiblepar 2 ;n(n1)(n2)est divisiblepar 3, car il y atoujoursun multiplede 3 parmitrois nombres consécutifs. Aest divisible par 2 et par 3, donc divisible par 6 car 2 et 3 sontpremiers entre eux.

V Petit théorème deFermat

Petit théorème de Fermat

pest un nombre premier,aest un entier tel quea2 et non divisible parp. Alorsapl1 est divisible parp, c"est-à-direap11 (modp).

Démonstration :

pest un nombre premier,doncpest premier avec 1, 2, ...,p1 (sinonpadmettraitun diviseur positifautre que

1) et donc premier avec (p1)!

Sikest un entier tel que 1kp1 , alors le resterkde la division dekaparpest non nul. En effet, sipdiviseka, alorspdiviseacarpest premier aveck; or ceci est impossiblecar par hypothèse,an"est pas divisible parp. Sikest un entier distinct dek(par exemplekk) tel que 1kp1, alors les restesrketrkdes divisions respectives dekaetkaparpsont distincts. En effet, sirkrk, alorspdivisekakac"est-à-dire (kk)aavec 1kkp1, ce qui est impossiblecar an"est pas divisible parp.

Ainsi, lesp1 restesr1,r2,...,rp1des divisions respectives dea, 2a, ..., (pl)aparpsont donc des entiers

naturels non nuls, strictement inférieursàpet tous distincts. Donc l"un de ces restes est égal à 1, l"autre à 2, ..., l"autre àp1.

D"où en utilisantle produit des congruences :

a2a(p1)ar1r2rp1(modp) c"est-à- dire (p1)!ap1(p1)! (modp). Doncpdivise (p1)!ap1(p1)! c"est-à-dire (p1)!?ap11?. Orpest premier avec (pl)!, doncpdiviseap11 d"après le théorème de Gauss. EXEMPLE7 est premier et ne divise pas 12, donc 1261 est divisible par 7.

Conséquence

pest un nombre premier,aest un entier supérieur ou égal à 2. Alorsapaest divisible parpc"est-à-direapa(modp).

DÉMONSTRATION

apaa(ap11).

Page 8/

10

TABLE DES MATIÈRES

Siaest divisible parp, alorsa(ap11) est divisible parp.

Sian" est pas divisible parp, alors, d"après le petit théorème de Fermat,ap11 est divisible parpet donc

a(apl1) est divisible parp.

VI Plus petit commun multiple dedeux entiers

Étant donné un naturela, notonsM(a) l"ensemble des multiplesdeastrictement positifs.

Définition

Le plus petit commun multiple des naturels non nulsaetbest le plus petit élément deM(a)M(b), ensemble des multiplescommuns strictement positifs deaet deb. On l"appelle aussi PPCM deaet deb.

Remarques:

Le PPCM de deux entiers naturelsnon nuls est un entier au moins égal à 1.

PPCM(a;a)a; PPCM(1 ;a)a.

Le seul multiplede 0 est 0, onc PPCM(a; 0)0.

Le PPCM de deux entiers quelconques est celui de leurs valeurs absolues.

Propriété :

Soientaetbdeux entiers au moins égaux à 2. Le PPCM deaetbest égal au produit de tous les facteurs

premiers deaet de tous ceux deb, avec pour chacun d"eux l"exposant le plus grand de ceux qu"il a dans la

décomposition deaet deb.

Démonstration :

Soitmle PPCM de deux naturelsaetbsupérieurs ou égaux à 2. Commemest un multiple dea, sa décomposi-

tionenfacteurspremierscomprendtouslesfacteurspremiersdeaavecunexposantau moinségal àcelui qu(ils

ont dans la décomposition dea; de même, elle comprend tous les facteurs premiers debavec un exposant au

moins égal à celui qu"ils ont dans la décompositiondeb.

Ainsi,mcomprend tous les facteurs premiers deaet tous ceux deb, avec un exposant au mois égal à au plus

grand de ceux qu"il a dansaet dansb.

Propriété

1. L"ensemble des multiplescommuns deaet debest l"ensemble des multiplesde leur PPCM.

2. Soientaetbdeux entiers naturels: PPCM(a;b)PGCD(a;b)ab

Démonstration :

On supposeaetbnon nuls. Soitdle PGCD deaetb: il existe des entiersaetbpremiers entre eutels que adaetbdb. Soitμun multiple commun deaetb: il existe alors des entiersketktels queμkaetμkb. D"où : kda kdb. Commedest non nul, on obtientkakb. Puisqueadivisekbet queaetbsont premiers entre eux,adivisekd"après le théorème de Gauss. IL existe ainsi un entierqtel quekqa.

On en déduit :μqabqdab.

Ainsi, tout multiple comunμàaetbest un multiple desab: le plus petit de ces multiples communsmest

obtenu pourq1., ce qui fournit =mdab.

Page 9/

10

TABLE DES MATIÈRES

D"où :md(da)(db)ab.

Siaet nul etbnon nul, l"égalité est vérifiée cardbetm0.

Exemple :

Le PGCD de 42 et 60 est 6. Si on notemleur PPCM, alors 6m4260 d"oùm420.

Propriété :

Sikest un entier naturel, PPCM (ka;kb)kPPCM (a;b).

Exercices:

1. Déterminer le PPCM de 240 et de 756.

2. Déterminer le PPCM de 44100 et de 36036.

Solution

1. On utilise la décompositionen facteurs premiers.

2. On détermine le PGCD de ces deux entiers avec l"algorithmed"Euclide.

Le PGCD est 252. ON a alors 252m4410036036.

Équationsfaisant intervenir le PPCM :

1. Déterminer deux entiers naturelsaetbconnaissant leur produit 1512 et leur PPCM 252.

2. Soientdetmle PGCD et le PPCM de deux naturelsaetb? Détermineraetbtels quem2d11.

Solutions

1.ab1512. Notonsdleur PGCD. On a 252dabd"oùd6.

Oradaetbdb, avecaetbpremiers entre eux. De plus 35ab1512 d"oùab42. Commeaet b sont premiers entre eux, le couple (a,b) peut être égal à : (1 ; 42),(2 ; 21),(3.14),(6.7),(7 ; 6),(14,3),(21 ; 2),(42 ;1). On multipliepar 6 pour avoir tous les couples solutions.

2.adaetbdb,aetbpremiers entre eux.

Commemdab, on amdd2abd"oùmdab.

La relation donnée s"écrit :dab2d11, soitd(ab2)11.

Ainsi,ddivise 11 etdest positif, doncd11 oud1.

Sid11, alorsab21 doncab3. (a;b)(1 ; 3) ou (3 ; 1) et (a;b)(11 ; 33) ou (33 ; 11). Sid1, alorsab13 d"où (a;b)(1 ; 13) ou (13 ; 1). Alors (a;b)(13 ; 1) ou (1 ; 13). Ainsi, il y a quatre couples solutions.quotesdbs_dbs41.pdfusesText_41

[PDF] ppcm de deux nombres premiers entre eux

[PDF] cours developpement communautaire

[PDF] montrer qu'il existe une infinité de nombres premiers de la forme 4n+1

[PDF] extraction du charbon

[PDF] origine du charbon

[PDF] 3 conditions necessaires a la formation du charbon

[PDF] la formation des combustibles fossiles schéma

[PDF] origine des combustibles fossiles seconde

[PDF] formation du charbon schéma

[PDF] somme de racine carré

[PDF] calcul avec racine carré seconde

[PDF] formation du sac embryonnaire chez les spermaphytes

[PDF] formation du grain de pollen pdf

[PDF] fusion partielle et cristallisation fractionnée

[PDF] magmatisme de dorsale