Epita 2004 epreuve optionnelle classe prepa mp epreuve optionnelle 2004 classe prepa mp

Publié par

6´ ´EPREUVE OPTIONNELLE de MATHEMATIQUESDans ce probl`eme, on note D(a,b) l’ensemble des diviseurs communs `a deux entiers naturels a, b ou`(a,b)=(0,0), et le plus grand ´el´ement de cet ensemble D(a,b) est donc le PGCD de a et b. Le probl`eme apour but l’´etude de la complexit´e du calcul du PGCD des entiers naturels a et b par ...
Publié le : jeudi 21 juillet 2011
Lecture(s) : 172
Nombre de pages : 2
Voir plus Voir moins
´ ´ EPREUVE OPTIONNELLE de MATHEMATIQUES
Dansceprobl`eme,onnoteD(a, bsemblensdivledesrocsiue`sdammnuientxeeuretunarssl)a,bou` (a, b)6=(0,peulgsar)0e,ltentdecetnd´el´emesneelbmD(a, b) est donc le PGCD deaetbae`lmerpbo.eL pourbutle´tudedelacomplexite´ducalculduPGCDdesentiersnaturelsaetbpar l’algorithme d’Euclide d´ecritci-dessous.One´tudiea`titrepr´eliminairelasuitedeFibonacci,quiestd´enieparF0= 0,F1= 1, et Fn+2=Fn+1+FnpournN.
1˚)anD(ciacnobiFedetiusaledlecalculn´etudieseitnoo,csteetuqFn). ´ a) Ecrireun algorithme de calcul deFnlorsque le nombre entiernno´nsedt.e b)Pre´ciserFnpourn612. 2˚)csnaDseuqetteuiasdeteboFiccna(ition,on´etudielepsorrp´itee´dsleFn). a) Prouverque (Fn) est une suite de nombres entiers naturels, strictement croissante pourn>2. b)De´terminerlessuitesg´eome´triques(unv)relatiolnari´entaun+2=un+1+un. c)De´terminerlexpressiondutermege´ne´ralFnde la suite de Fibonacci en fonction den. d)End´eduirelencadrementsuivantdeFndentelaviuqe´nusiup,Fnlorsquentend vers +:  !! ! ! nn 1 5+ 11 5+ 1 √ −16Fn6+ 1. 5 25 2
e)De´terminerledomaineded´enitionetlasommedelafonctiong´ene´ratrice: +P n F(x) =Fnx. n=0 3˚)i´etropruespuelqlbesnmeleee´dsttceueeqnsDaute´qeidoitsno,nD(a, b). a)Quelssontlese´le´mentsdeD(a,0) et le PGCD deaet de 0 poura>1 ? b) Montrer,sia=bq+r, queD(a, b) =D(b, r) et PGCD(a, b) = PGCD(b, r). c) Enremarquant queFk+2=Fk+1+Fknd,eGeCleiPreduD´deFn+1et deFnpournN. Onconsid`eredeuxnombresentiersnaturelsaetbtels quea > b >enuuqellepparnO0.edelit´´ega la formea=bq+rest la division euclidienne deaparbsiqetronsrelsv´eriantdtueextneisranut 06r < b, et que l’algorithme d’Euclide est la suite des divisions euclidiennes suivantes, poursuivies jusqua`lobtentiondunpremierrestenul,etdanslesquellesa0=aeta1=b: a0=q1a1+a2avec 0< a2< a1 a1=q2a2+a3avec 0< a3< a2 ...................................... an1=qnan+an+1avec 0< an+1< an an=qn+1an+1+an+2aveca2= 0 Onditalors,pluspre´cis´ement,quelalgorithmedEuclidepouraetbs’effectue enndivisions.+ 1 Lensembledecesnotationsestd´esormaisconserve´jusqu`alanduproble`me.
4˚)nacsteetDmedrithide.Euclitnoilaclaogedlemexunieppaedplnoitseuqdute´no, ´ a) Ecrirel’algorithme d’Euclide pourF3etF2, pourF4etF3, pourF5etF4. b)Prouverquel´egalite´Fk+2=Fk+1+Fkest la division euclidienne deFk+2parFk+1pourk>2. Ende´duirequelalgorithmedEuclidepourFn+2etFn+1s’effectue enndivisions euclidiennes.
1
5˚)itoredhmucEdelielpm´tixledeglan´etudieennlacocsteetuqseitnoo,anDameLedemr`eoh´(T.)e´ a) Prouverque le PGCD deaetbest´noteulnnrrsenreiuaedgelaan+1. b)Prouverparre´currencelesin´egalite´sqk>1 pour 16k6n+ 1etak>Fn+2kpour 06k6n+ 2. c)End´eduire,silalgorithmedEuclideseectueenn+ 1divisions, quea>Fn+2,b>Fn+1, et :    ! n+1 1 5+ 1   √ −16b. 5 2
p1p d)Ende´duire,sil´ecritured´ecimaledebcomptepchiffres, autrement dit si 106b <10 ,que le nombrendsnoisivroglaleEedhmitesdeliucpar5tmajor´ededi+1p+ 2. ´ 6˚)ra´efotithriitmeacfilucle´rusrucernulaogcEiresn´euxnDdedePGCantldsnoitresenemorbaetbpar cetteme´thode.
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.