La lecture en ligne est gratuite
Télécharger
Polynˆomes.Quelquesd´emonstrationssaut´eesencours
er 1fe´vrier2011
Divisioneuclidienne:existencea`laidedunalgorithme
Encours,nousavonsjusti´elexistencedeladivisioneuclidienneen«posant»uqeohed´mteoi,nadlisiv lonconnaˆıtdepuislecolle`ge. Nousre´e´crivonsicilam´ethodeducolle`gesouslaformedunalgorithmemeˆoynolstenadtno´nseedpsqui´ AK[X] etBK[X] avecB6= 0 construit un couple (Q, Rd)peoˆemlonynadssK[Xe´v]airnt A=Q B+R(1) deg(R)<deg(B) (2) 1 Danslalgorithmedonn´e,deg(Polnpuedr´egedelngise´d)emnyoˆP; dom(P) le coefficient dominant deP,si P6abrivanermfoinleeuqitaLors=0.cnnouqoreueis`da,erirce´a0signiequonaaetce´a`ala valeur 0.
Div(A, B) Entr´ee:A, BK[X] avecB6= 0. 2 Sortie :(Q, R)K[X.)2(te)1ant(eri]v´ 1.RA. 2.Q0. 3. si deg(R)<deg(B),allez en 7. dom(R) deg(R)deg(B) 4.QQ+X . dom(B) dom(R) deg(R)deg(B) 5.RRX B. dom(B) 6. allez en 3. 7.Retourner(Q, R).
Fig.1 – Algorithme de division euclidienne
2 Lorsquuninformaticiena´ecritunalgorithme,ildoitmontrerque: T.sonalgorithmesarreˆtetoujoursquellesquesoientlesentre´es.Onparlealorsdeterminaison; C.sonalgorithmeretournetoujoursunre´sultatcorrect,quellesquesoientlesentr´ees.Onparlealorsde correction. Pour s’assurer de la terminaison et de la correction de son algorithme, l’informaticien peut mettre en ´evidence: T.unequantite´quinesauraitde´croˆıtreind´enimentaucoursdelalgorithme; C.unequantit´einvarianteaucoursdelalgorithme. 1 Lapre´sentationestvolontairementdi´erentedunepre´sentation`alaMaple.Ilsagitdunepre´sentation`alabasicavecdes ´etiquettesetdespointsdebranchement.Cecidit,vouspouvezessayerdelapr´esenterdansunformatMaple. 2 Terminaison et correction sont les mamelles de l’algorithmique.
1
PCSI B
Mathe´matiques
Lyce´eBrizeux-anne´e2010-2011
Examinons ce que dit l’informaticien de l’algorithmeDiv.g.1augeriFriecalt`d´
The´or`eme1moˆnylopseltneioesuelsquesQAK[X]etBK[X],avecB6= 0,l’algorithmeDivliqu´eapp `a(A, B)termine et retourne un couple(Q, R)ire´vseme)1(tnadˆoynolept(2).
D´emonstrationeithmlgoreladruqaobnodsesvrocevesprmaˆtbo,encladaerlanseupr.Aavtnedonsu sarreˆtede`squonesten7.Orpouryparvenir,ilfautquelaconditionen3.soitv´erie´e,cest-`a-diredeg(R)< deg(B).nentertietude`a´uosreiprrureassOontdoinvuqaleuqcpe´titnaladermteaiinnesoaltsnauq´tite deg(R).Pour ce qui est de la correction, c’est une autre affaire. Nous avons le temps de l’examiner d’autant plus si l’algorithme ne termine pas ... Terminaison.eoupaolsoscndunqisngSiqpeuiptahsm.eCneelsaelararlˆgeotre(ioitegndR)<deg(B) nestjamaisve´rie´eetdonclese´tapes3.;4.;5.et6.sontinde´nimentre´pe´te´es. ` Soitileige`al´etape3..O`mepesaastonnolaesrRila valeur deRauie5etap`epemegnesaaslA´.3. qui suit, la variableRecdonetee´onedsspaidomtseRia`Ri+1.reOnt´equeidsnlucqramaseu deg(Ri+1)<deg(Ri). Puisquelalgorithmenesarreˆtepas,ontrouvedoncunesuitestrictementde´croissantedentiersnaturels, `asavoir(deg(Ri))i1.Ce qui est impossible. Ainsidonclalgorithmesarrˆete.Onpeutdonc´etudierlacorrectiondelalgorithme. Correction.daynesetnede´ce´prnsioatotsnlevesnrenOocjoignantQiqui est la valeur de la variable Qauiate´.3epegasla`em`a.sep On remarque qu’au premier passage en 3., on aQ1= 0 etR1=A.On a donc A=Q1B+R1. Nousallonsmontrerquelaquantit´eQ B+Rest invariante au cours de l’algorithme, donc tout le temps e´galea`A.Pour cela, il suffit de montrer queQi+1B+Ri+1=QiB+Ri. dom(Ri) dom(Ri) degRideg(B) degRideg(B) OrQi+1=Qi+XetRi+1=RiX B.D:`uo dom(B) dom(B) dom(Ri) dom(Ri) degRideg(B) degRideg(B) Qi+1B+Ri+1=QiB+X B+RiX B dom(B) dom(B) =QiBi+Ri Puisque l’algorithme termine et puisqueA=B Q+Rtout au long de l’algorithme, le couple (Q, R) retourne´v´eriebien(1)et(2),cequimontrelacorrectiondelalgorithmeDiv. 2
Formule de Leibniz
Lobjectifestdevousdonnerlescle´spoure´tablirlaformuledeLeibniz.Rappelons-la:
SoientnN; (P, Q)K[X].Alors :
n  X n (n) (k) (nk) (P Q) =.P Q k k=0
(0) On rappelle queP=Pnvention.Lad´emoserupraocr´artplincreurecoitartsnbate´snnN.On la donnesousformedequestionsinterm´ediaires.
1. Montrerque la formule est vraie pourn= 0.
Onsupposelaformule´etabliepouruncertainentiern0.
2
PCSI B
Mathe´matiques
Lyc´eeBrizeux-anne´e2010-2011
n n  X X n n (n+1) (k+1) (nk) (k) (n+1k) 2. Montrerque (P Q) =P Q+P Q. k k k=0k=0 n+1 n  X X n n (n+1) (k) (n+1k) (k) (n+1k) 3.Ende´duireque(P Q) =P Q+.P Q k1k k=1k=0 4.Conclure`alavalidit´edelaformuleaurangn+ 1.esrlerseqramlbauusseliserdesidentit´Opnuorruait coefficients binomiaux. 5. Conclure.
Irre´ductiblesdeR[X]
Factorisation dansR[X]
Ilsagitd´etablirlethe´ore`mesuivant:
Th´eor`eme2lbitedse´rricudeesLR[X]er´egedemdsnyoˆpslotneltemeexacsont1grdedeoue´2et de discri-minant<0.
De´monstration`jqaeuelpslonyoˆmesdedegr´e1sontO.ains´etdmoseylˆncude´rrip;selbituieqrcoupoestdes 2 dedegre´2`adiscriminant<0,il suffit de reprendre l’exemple deX+Xpour s’en convaincre.+ 1 Ilnerestedoncplusqua`e´tablirquilnyapasdautrespolynˆomesdeR[Xgueeel´.usdit]crbritsninOid selon que deg(P) = 2 ou deg(P)>2. SiPedtdese2r´eg,on le suppose de discriminant0.oˆnyemLepolPcirasrneel´esleacnodxued (simplesouuneracinedouble)ets´ecritdonccommeunproduitdepolynoˆmesdedegre´1.Ainsi un tel polynoˆmeestr´eductible. SiPe´rgtseeded3,oplisroluaede`ssnesuinmoconeciraexpamelαCnoelsleor`eth´emede D’Alembert-Gauss. Siα(ssteeer´e,lloralXα) diviseP(dansR[Xueeqınaˆtrenuieq]biensˆur)cPansdelbitcude´rtse R[X]. 3 Siαnesslaroll,e´reeptsaαde¯ est aussi une racineP.Puisqueα6= ¯α,polynˆom(eleXα) (X¯α) 2 divisePdansC[X].Or (Xα) (X¯α) =X(α+α¯)X+α α¯R[X].ntueel,lonrceqs´aPmeem 4 2 vu en coursentraˆıne que (Xα) (Xα¯) divisePdansR[X].Ce qui montre quePlbeestr´educti dansR[X]. 2
De´compositionenfacteursirre´ductiblesdansR[X]
5 Nousallons´etablirlapartieexistencedelade´compositionenfacteursirre´ductiblesdansR[X].Rappelons cequestunetelled´ecomposition.
The´or`eme3SoitPR[X]uemnyoˆpnlonon constant. AlorsPns´eitcrmade`eniunreeuqiepa`tumroita pr`esdesfacteurssouslaforme k Y mi P=,λ Q i i=1 ∗ ∗o`uλR;kN;Qiedantiblscude´rriR[X];miNpouriJ1, kK. 3 Lemme1ducoursdu1erfe´vrier2011. 4 cf.coursdu1erfe´vrier2011. 5 Lad´emonstrationesta`retenir:enpratiquecestainsiquonproce´derapourobtenirlad´ecompositiondansR[X]
3