UNIVERSITE d'ORLEANS SCL1 MA02 Departement de mathematiques

Publié par

Niveau: Supérieur, Licence, Bac+1
UNIVERSITE d'ORLEANS SCL1 MA02 Departement de mathematiques 2008-9 Arithmetique : Corrige feuille 2: revisions de la Toussaint. (Rappels: pas de cours-td la semaine du 3 au 7 novembre 2008). Devoir sur table la semaine suivante. Exercice 1. (1) Utilisez l'algorithme d'Euclide pour trouver un couple (x, y) d'entiers relatifs tels que (E1) : 89x + 41y = 1. On a 89 = 2? 41 + 7; 41 = 5? 7 + 6; 7 = 1? 6 + 1. ainsi pgcd(89, 41) = 1 et 1 = 7? 6 = 7? (41? 5? 7) = 7? 41 + 5? 7 = 6? 7? 41 = 6? (89? 2? 41)? 41 = 6? 89? 13? 41. (On verifiera toujours sur un brouillon cette derniere equation 6?89?13?41 = 1). Ainsi x = 6 et y = ?13 conviennent. (1') Meme question avec (E2) : 59x + 27y = 1. On a 59 = 2? 27 + 5; 27 = 5? 5 + 2; 5 = 2? 2 + 1. D'ou pgcd(59, 27) = 1 et 1 = 5? 2? 2 = 5? 2? (27? 5? 5) = 11? 5? 2? 27 = 11? (59? 2? 27)? 2? 27 =

  • exercice similaire au precedent

  • nk

  • ?4 ?

  • equation avec la methode usuelle

  • divise y0?y

  • entier naturel

  • equation

  • couple


Publié le : mercredi 30 mai 2012
Lecture(s) : 52
Source : univ-orleans.fr
Nombre de pages : 4
Voir plus Voir moins
´ ´ UNIVERSITE d’ORLEANS De´partementdemathe´matiques
SCL1 MA02 2008-9
Arithm´etique:Corrige´feuille2:r´evisionsdelaToussaint. (Rappels: pasde cours-td la semaine du 3 au 7 novembre 2008). Devoir sur table la semaine suivante.
Exercice 1.(1) Utilisezl’algorithme d’Euclide pour trouver un couple (x, y) d’entiers relatifs tels que (E1) : 89x+ 41yOn a= 1. 89 = 2×41 = 541 + 7;×7 + 6;7 = 1×6 + 1. ainsipgcd(89,41) = 1 et 1 = 76 = 7(415×7) = 741 + 5×7 = 6×741 = 6×(892×41)41 = 6×8913×41. (Onve´rieratoujourssurunbrouilloncettedernie`re´equation6×8913×41 = 1). Ainsix= 6 ety=13 conviennent. (1)Mˆemequestionavec(E2) : 59x+ 27y= 1.On a 59 = 2×27 = 527 + 5;×5 + 2;5 = 2×2 + 1.Do`upgcd(59,27) = 1 et 1 = 52×2 = 52×(275×5) = 11×52×27 = 11×(592×27)2×27 = 11×5924×27. ainsix= 11 ety=tnenneivnoc42ouaterierv´On.(nurbuoliojrussrulon cettederni`eree´quation11×5924×27 = 1). (2)Trouvertouslescouplessolutionsdele´quation(E1qeaule´(itnouisd)pE2). Onsuitlam´ethodeducours: Pour (E1) : Onaobtenuunesolutionparticuli`erex0= 6 ety0=nteencre´eirdPa.31er le´quationsatisfaiteparlasolutionge´ne´ralecherch´eeetl´equationsatisfaitepar lasolutionparticuli`ere,onobtient 89(xx0) + 41(yy0) = 11 = 0 ainsi 89(xx0) =41(yy0) = 41(y0y) (α). Dou`89divise41(y0ysait que 89 et 41 sont premiers entre eux (Pgcd). On =1).Parleth´eor`emedeGauss,89divisey0yexistei.e. ilkZtqy0y= 89k i.e.y=y089ktiudor.eintOnr´ydqe´lsna(ontiuaα), 89(xx0) = 41(y0y) = 41×89k. On simplifie par 89 et on obtient,xx0= 41kqui donne. Cex=x0+ 41k. Les solutions si elles existent sont donc parmi les couples (x, y) = (6 + 41k,1389k`u)okZ.esIlactfesopnoie)dev´erierquesli(ete´nceseasrix= 6+ 41k ety=1389kpour n’importe quelkZrslealoation´8e9qu´xx+ 41y= 1 est toujours satisfaite.Ce qui signifie qu’on a exactement toutes les solutions 1
2 del´equationsouslaforme(x, y) = (6 + 41k,1389k`u)okZ. Pour (E2actementlescouplsednno)O:leneesr´taullet:lossoituossnxetn (x, y) = (11 + 27k,2459ku`o)kZL.attiere´ile`cutiarnpioutolasx0= 11 ety0=24. Exercice 2.(1) Calculerpgcd(47,l’algo. d’Euclide:35). Par 47 = 1×35 + 12;35 = 2×12 + 11;12 = 1×11 + 1.Dou`pgcd(47,35) = 1 (Premiers entre eux). (2)Trouvertouteslessolutionsentie`resde47x+ 35y= 1. Unesolutionparticulie`redonn´eeparlalgo.dEuclideest:1=3×474×35 i.e.x0= 3 ety0=La4.lusoontie´ar´gnetelsex+ 35= 3k,y=447k aveckZ. Lessolutionsentie`resde141x+ 105yOn calcule le= 3.pgcd(141,105) = 3. Onpeutdoncdiviser141et105par3.Ondivisedechaquecoˆte´dele´quation par3,lanouvellee´quationest47x+35 = 1.Ainsi les solutions de 141x+105y= 3 sont des solutions de 47xrpice´R.tnemeuqosi+35=1xetysont solutions de 47xa1ol,3n+=5amtuilot´resqeuneatnttepairp3lcixetysatisfont aussi l´equation141x+ 105yLes solutions de 47= 3.x+ 35= 1 et de 141x+ 105y= 3 sont donc identiques.Les solutions de 47x´eoba´et!tenu3+=5´djeo1tn
(3) SoitnNreudso´e47.rno-tuePx+ 35y=noui, donner les solutions.? Si
Pour ce type de question le pgcd de 47 et 35 est utile:il vaut 1.
Le casnt.Onmmenended´ep4c7danonietiartes0=x= 35(y). Puisque 47et35sontpremiersentreeux,dapre`sleth´eore`medeGauss,47divisey i.e. ilexistekZtel quey= 47ka donc pour. Onx, 47x= 35×47ki.e. x= 35ksi (. Ainsix, y) est un couple solution alorsx= 35kety=47kpour unkZeireuqr.´Rcepioruqmene,tilestfaciledev´ex= 35kety=47k sont effectivement des solutions de 47x+35y= 0 pour toutkZsolutions. Les sont donc exactement (x, y) = (35k,47k), kZfaire le lien avec notre. (Pour me´thodeusuelle,onnoteraquex0= 0 ety0licutiarnpioutolnusee0ts=ere` dele´quationavecn= 0.)
Le casnN. Soit (a, b) une solution de 47a+ 35b= 1.Si on multiplie parntecn,iotauqe´et on obtient 47(na) + 35(nb) =n. Ainsix=naety=nbfournit un couple solution de 47x+ 35y=n. Maisest-ce que toutes les solutions sont de cette forme ?Pourn6NON. On choisit= 1:a0etb0leu`itrredcienoapulitnesou 47a+ 35b1=c,nousequieunedonnnoituloslucitrapeeri`x=na0,y=nb0de 47x+ 35y=ni.e. 47x0+ 35y0=noitue´gnre´n(ela.Lasolx, y) de 47x+ 35y=n satisfait alors 47(xx0)+35(yy0) =nnnalutso´enr.O=0oitauqe´ettecsro aveclam´ethodeusuelle!alorslessolutionssontx= 3n+ 35k,y=4n47k aveckZ(x0= 3n,y0=4nnetuesontilusociluaptr)e.`ire
3 Pourquoi les solutionsx=naety=nbne sont pas toutes les solutions?On a vu quea= 3 + 35ketb=447ktoutes lesci-dessus. Si solutions´etaientdelaformex=naety=nb, on obtiendrait que les solutions seraient toutes de la formex= 3n+ 35nkety=4n47nkon. Ainsi obtiendrait uniquement les multiplesnkau lieu de tous les entiersk. (Exemple avecn= 2, on obtiendrait uniquement les entiers pairs 2k). Exercice 3.pgcd= 2.(33 810; 4 146) Exercice 4.SoitnOn poseun entier naturel.a= 3n+4 parb= 2nque+3. Prouvons siddiviseaetbalorsdOn a quedivise 1.ddivise 2a= 6net+ 8ddivise 3b= 6n+ 9 doncdlasevidiener´diec3b2a= 1 ainsid1.Onend´eduitqueis=dest lepgcd de a et b alorsddiviseaetbdoncdAinsi= 1.aetbsont premiers entre eux. Exercice 5.grmunedtatevucan´ec´edenaireauprlimisecicrexE(itSoouuc).rsnun entier naturel.On posea= 2npar+ 1b= 3n+ 2.On a 3a= 6net 2+ 3b= 6nalors+ 4 2b3a= 1.C’est une relation entreaetbenepntdaeed´dninrpe`ustn´hoe`rmeea.D du cours s’il existe deux entiersuetvtels queua+vbuivat´eqceslorsa1=eltnaet bpremiers entre eux.Iciu=3 etv= 2 conviennent alorsaetbsont premiers entre eux. Exercice 6.(1) Lesdiviseurs de 21 sont 1;3; 7et 21 car 21 = 3×7. 2 2 (2) Lescouples (a, b) d’entiers naturels tels queab(tneire´v12=ab)(a+b) = 21 ainsiabeta+bOn a les cas suivants:sont des diviseurs de 21. (i)ab= 1 eta+b2oisn=P.12mmedarsoquates´ea= 22 i.e.a= 11 donc b= 10. (ii)ab= 3 eta+b´sedauqeissrsaupeAm.m7o=ontis2a= 10 i.ea= 5 doncb= 2. (iii)ab= 7 eta+b= 3 donc 2a= 10 i.e.a= 5 etb=2. (iv)ab= 21 eta+b= 1 donc 2a= 22 i.e.a= 11 etb=10. Ceci donne tous les couples (a, bel´equation.os)ituldsno (3)(Meˆmem´ethode).Onde´compose15=3×5 ainsi les diviseurs de 15 sont 1;3; 5 2 2 et 15.Les solutions deab= (ab)(a+b) = 15 sonta= 8 etb= 7,a= 4 etb= 1,a= 4 etb=1,a= 8 etb=7. Exercice 7.Calculer le pgcd et le ppcm dea= 105 etbOn a= 231.pgcd(a, b) = 21. ab Doncppcm(a, b= 5) =×231 = 1155. pgcd(a,b) 2n n Exercice 8.Montrons que 21 est divisible par 2a1. On 2n n2n n 21 = (2)1 = (21)1)(2 +. 3n n Montrons que 21 est divisible par 21. Ona 3n n3n2n n 21 = (2)1 = (21)(2 +2 +1) n3 2 on prendb= 2dansb1 = (b1)(b+b+ 1). Exercice 9.On cherche les couples (x, y) d’entiers naturels tels que : xy0 xy= 1512 etppcm(x, y) = 252.Calculonsd=pgcd(x, y) == 6.Soitx=dx, ppcm(x,y)
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.