Algoritmi de Factorizare Pentru Polinoame din F Q
ALGORITMI DE FACTORIZARE PENTRU POLINOAMELE DIN
CUPRINS
Introducere
Capitolul I. Inele euclidiene
Subinel, subcorp
Definiția inelelor euclidiene. Exemple
Relația de divizibilitate în inele euclidiene
Algoritmul lui Euclid. Lema chineză a resturilor
Polinoame de interpolare Lagrange
Capitolul II. Elemente de teoria corpurilor
2.1 Extinderi de corpuri
2.2 Extinderi algebrice
2.3 Corpuri finite
Capitolul III. Inele de polinoame
Capitolul IV. Algoritmi de factorizare pentru polinoame din și
Capitolul V. Algoritmi de factorizare pentru polinoame cu coeficienți într-un corp finit
5.1 Algoritmul DS
5.2 Algoritmul SF
5.3 Algoritmul Berlekamp
5.4 Algoritmul DD
5.5 Algoritmul Cantor-Zassenhauss
Concluzii
Anexă. Descrierea algoritmilor în pseudocod
Bibliografie
INTRODUCERE
Deși polinoamele monice ireductibile peste R, care sunt de forma , cu , și orice polinom monic neconstant din , se pot reprezenta în mod unic, abstracție făcând de ordinea factorilor, ca produs de polinoame monice ireductibile, nu se cunosc totuși proceduri efective pentru asemenea reprezentări ale polinoamelor din .
În inelul , spre deosebire de inelul , există polinoame ireductibile de orice grad. În această lucrare îmi propun să prezint câteva proceduri efective, de natură algebrică, care să stabilească pentru orice polinom neconstant din , dacă este ireductibil, și în caz contrar, să determine descompuneri netriviale ale sale. De asemenea, voi încerca să prezint faptul că factorizarea polinoamelor monice în , se reduce la factorizarea polinoamelor monice din , p număr prim, unde prin am notat corpul claselor de resturi modulo un număr prim , .
Lucrarea de față este structurată în cinci capitole, ultimul capitol prezentând efectiv procedurile mai sus menționate.
Primul capitol, intitulat ”Inele euclidiene”, cuprinde în primul paragraf definiții și enunțuri ale rezultatelor referitoare la inel, subinel, subcorp, domeniu de integritate. În cel de-al doilea paragraf, pe baza axiomei bunei ordonări este demonstrat Principiul inducției matematice: (vezi Propoziția 1.2.3), precum și un rezultat fundamental privind aritmetica mulțimii numerelor naturale N, Teorema împărțirii cu rest (vezi Teorema 1.2.4). Pentru a putea stabili o serie de proprietăți de natură aritmetică pentru inelul Z al numerelor întregi și pentru inelele de polinoame , K corp comutativ, este abordată această problematică pentru clasa inelelor euclidiene, care conține inelele Z și , K corp comutativ. Relația de divizibilitate este prezentată în paragraful al treilea. Aici este dată definiția celui mai mare divizor comun a două elemente dintr-un domeniu de integritate și demonstrată existența celui mai mare divizor comun în inele euclidiene (vezi Propoziția 1.3.3). Sunt prezentate în cel de-al patrulea paragraf două instrumente fundamentale din Aritmetica modulară. Primul, Algoritmul lui Euclid extins, este de fapt Agoritmul lui Euclid întregit cu operațiile de determinare a coeficienților Bézout. Cel de-al doilea, Lema chineză a resturilor pentru inele euclidiene, este o extindere la un inel euclidian arbitrar a unui rezultat cunoscut încă din secolul IV A.D. În ultimul paragraf al acestui capitol, restrângându-ne la polinoamele monice, obținem în un rezultat analog Teoremei fundamentale a Aritmeticii adevărată în mulțimea numerelor naturale N, care arată că orice polinom monic , , admite o reprezentare unică sub forma , cu polinoame monice ireductibile distincte și , , reprezentare numită descompunerea canonică a polinomului f (vezi Teorema 1.5.13).
În capitolul al doilea, intitulat „Elemente de teoria corpurilor”, sunt prezentate și explicate câteva din conceptele, construcțiile și rezultatele de bază din Teoria corpurilor. În primul paragraf sunt discutate extinderile de corpuri, gradul unei extinderi, extinderile de grad finit și noțiunea de polinom minimal. Este prezentată demonstrația unui rezultat fundamental în studiul extinderilor finite și al extinderilor algebrice, și anume Formula gradelor (vezi Teorema 2.1.9). În paragraful al doilea este introdus conceptul de extindere algebrică și definit inelul de resturi modulo un polinom arbitrar nenul având coeficientul dominant inversabil, unde R este inel comutativ arbitrar. Această definiție este dată prin analogie cu inelul de resturi modulo un număr , care angajează Teorema de împărțire cu rest în inelul Z. Construcția lui se bazează pe Teorema cu rest relativ la asemenea polinoame . Este demonstrat deasemenea un rezultat esențial al Teoriei corpurilor: pentru orice polinom neconstant cu coeficienți într-un corp comutativ K există o extindere L a lui K în care se descompune în factori liniari (vezi Teorema 2.2.17), iar o cea mai mică asemenea extindere se numește corp de descompunere al lui (vezi Definiția 2.2.20). În paragraful trei sunt stabilite rezultate de bază ale corpurilor finite, precum Mica Teoremă a lui Fermat pentru corpuri finite (Teorema 2.3.3). Enunțul original al Micii Teoreme a lui Fermat se referă la numere întregi și nu la corpuri finite: pentru orice număr prim și orice care nu este divizibil cu p, are loc congruența . Pentru a face legătura cu Teorema 2.3.3 se transpune echivalent această congruență din inelul Z în egalitatea din corpul finit . Prin urmare enunțul original al Micii Teoreme a lui Fermat pentru numere întregi este echivalent pentru corpul finit cu următorul enunț: . Prin urmare, enunțul Teoremei 2.3.3 este o extindere naturală de la corpul finit la orice corp finit F. Tot aici este prezentat un rezultat fără demonstrație al matematicianului Nathan Jacobson (vezi Teorema 2.3.4). Combinând Teorema de comutativitate a lui Jacobson cu Mica Teoremă a lui Fermat (Teorema 2.3.3) se obține Teorema de comutativitate a lui Wedderburn (Teorema 2.3.5), dată tot fără demonstrație. Sunt prezentate o serie de proprietăți de bază ale corpurilor finite: Teorema de cardinalitate (vezi Teorema 2.3.6), Teorema de structură aditivă (vezi Teorema 2.3.7), Teorema de ciclicitate (vezi Teorema 2.3.8), Teorema de existență (vezi Teorema 2.3.9) și Teorema de unicitate (vezi Teorema 2.3.12).
Capitolul III se numește „Inele de polinoame” și prezintă o construcție a inelului seriilor formale peste un inel comutativ și unitar R, și pornind de aici se definesc noțiunile de polinom, coeficient dominant al unui polinom. Este dată o proprietate importantă, proprietatea de universalitate a inelelor de polinoame de o nedeterminată (vezi Teorema 3.4). Este deasemenea definit, prin inducție matematică, inelul polinoamelor într-un număr finit de nedeterminate, și noțiunea de derivată formală a unui polinom și câteva din proprietățile acesteia.
O metodă modernă de factorizare a polinoamelor cu coeficienți raționali este prezentată în Capitolul al patrulea, intitulat „Algoritmi de factorizare pentru polinoame din și ”. Se arată că factorizarea polinoamelor de grad pozitiv din se reduce la factorizarea polinoamelor monice din , și se prezintă pașii necesari pentru determinarea unui divizor pentru polinomul monic , unde grad , grad și , algoritm numit procedura Kronecker. În cel de-al doilea paragraf al acestui capitol este discutată o problemă majoră de Aritmetică modulară, și anume aceea când cunoscând divizorii monici de grad d din ai lui , în ce condiții se pot găsi eventualii divizori monicide grad d din ai lui f?
În ultimul capitol, „Algoritmi de factorizare pentru polinoame cu coeficienți într-un corp finit ” sunt prezentate câteva metode efective de determinare a descompunerii canonice a unui polinom , în cazul , p număr prim. Algoritmul DS (descompunere standard) este folosit pentru calculul descompunerii standard a unui polinom monic neconstant , grad și sunt prezentați pașii necesari parcurgerii acestui algoritm. Algoritmul SF reduce problema factorizării polinoamelor monice din la problema factorizării polinoamelor libere de pătrate neconstante din , p număr prim. Algoritmul Berlekamp permite, pentru un polinom de grad pozitiv liber de pătrate din , să decidem dacă este ireductibil, iar în caz contrar, să obținem o factorizare netrivială a sa. Pasul următor algoritmului SF, de reducere la cazul polinoamelor libere de pătrate cu toți divizorii ireductibili de același grad, este Algoritmul DD care determină produsul tuturor divizorilor monici ireductibili și de același grad ai unui polinom liber de pătrate. Algoritmul Cantor-Zassenhaus este un algoritm probabilistic care determină factorizarea efectivă a polinoamelor din , p număr prim, despre care se știe că sunt produse de polinoame monice ireductibile distincte și de același grad. Mai exact, dat polinomul produs de polinoame monice ireductibile și distincte de același grad d, Algoritmul Cantor-Zassenhaus determină un divizor propriu al lui f.
În încheierea lucrării este adăugată o Anexă în care este făcută o scurtă descriere a algoritmilor în Pseudocod.
Doresc să exprim caldele mele mulțumiri Domnului Profesor……. pentru ajutorul acordat în vederea întocmirii prezentei lucrări, precum și pentru tot ceea ce m-a învățat de-a lungul anilor de studenție.
Capitolul I
INELE EUCLIDIENE
Subinel, subcorp
Definiția 1.1.1 Se numește inel (vezi [17]) o mulțime nevidă R, înzestrată cu două operații algebrice (adunarea și înmulțirea )
și ,
care satisfac următoarele condiții:
i) este grup abelian;
ii) este monoid;
iii) înmulțirea este distributivă față de adunare:
.
Observația 1.1.2 În continuare, toate inelele considerate vor fi unitare, motiv pentru care le vom numi prescurtat inele.
În cazul unui inel R, grupul abelian R față de adunare se numește grupul aditiv subiacent inelului. Elementul neutru al grupului abelian va fi notat cu 0 și îl vom numi elementul zero al inelului R, iar opusul față de adunare al unui element oarecare se notează, de obicei cu . Elementul neutru la înmulțire al monoidului va fi notat cu 1 și îl vom numi elementul unitate sau unitatea inelului R, iar inelul cu element unitate se va numi inel unitar. Într-un inel R avem oricare ar fi . De asemenea, dacă și numai dacă R are un singur element, și în acest caz R se numește inelul nul și se notează cu 0. Dacă înmulțirea este comutativă inelul R se numește comutativ.
Exemplul 1.1.3 Mulțimile Z, Q, și R cu operațiile obișnuite de adunare și înmulțire formează inele comutative și unitare.
Definiția 1.1.4 [1] O relație pe o mulțime nevidă M se numește relație de echivalență pe M dacă ea este reflexivă, simetrică și tranzitivă.
Observația 1.1.5 O relație de echivalență pe mulțimea M, , se notează cu semnul ~ sau cu semnul și se citește ”x este echivalent cu y” sau ”x este congruent cu y”.
Vom nota cu Eq mulțimea tuturor relațiilor de echivalență pe o mulțime nevidă dată M. Fie ~ o relație de echivalență pe M, i.e. ~ Eq. Pentru orice , considerăm mulțimea
numită clasa de echivalență a lui x modulo relația de echivalență ~. Mulțimea formată din toate clasele de echivalență ale tuturor elementelor lui M se numește mulțimea factor (sau cât) a lui M modulo relația ~.
Fie un număr întreg dat. Relația de congruență modulo n pe Z definită prin
este o relație de echivalență pe Z. Dacă atunci este exact relația de egalitate în Z, iar dacă sau atunci este relația totală pe Z.
Pentru orice , clasa de echivalență a lui x modulo relația se numește clasa de resturi modulo n a lui x și este
.
Exemplul 1.1.6 Mulțimea a claselor de resturi modulo n împreună cu adunarea și înmulțirea claselor, formează un inel comutativ și unitar, numit inelul claselor de resturi modulo n.
Dacă R este un inel cu , vom nota cu mulțimea elementelor lui R inversabile față de înmulțire, numite unități ale inelului R. Evident, , este parte stabilă a lui R în raport cu înmulțirea și formează grup în raport cu operația indusă, numit grupul unităților inelului R.
Vom nota cu mulțimea matricelor pătratice de ordin n cu coeficienți din R. Se știe că are structură de inel față de operațiile uzualehivalență a lui x modulo relația de echivalență ~. Mulțimea formată din toate clasele de echivalență ale tuturor elementelor lui M se numește mulțimea factor (sau cât) a lui M modulo relația ~.
Fie un număr întreg dat. Relația de congruență modulo n pe Z definită prin
este o relație de echivalență pe Z. Dacă atunci este exact relația de egalitate în Z, iar dacă sau atunci este relația totală pe Z.
Pentru orice , clasa de echivalență a lui x modulo relația se numește clasa de resturi modulo n a lui x și este
.
Exemplul 1.1.6 Mulțimea a claselor de resturi modulo n împreună cu adunarea și înmulțirea claselor, formează un inel comutativ și unitar, numit inelul claselor de resturi modulo n.
Dacă R este un inel cu , vom nota cu mulțimea elementelor lui R inversabile față de înmulțire, numite unități ale inelului R. Evident, , este parte stabilă a lui R în raport cu înmulțirea și formează grup în raport cu operația indusă, numit grupul unităților inelului R.
Vom nota cu mulțimea matricelor pătratice de ordin n cu coeficienți din R. Se știe că are structură de inel față de operațiile uzuale de adunare și înmulțire a matricelor. Ținând cont de teoria determinanților (vezi [16]) pentru matrice cu coeficienți numerici, obținem teoria asemănătoare valabilă pentru matrice cu coeficienți într-un inel comutativ. Ne vom folosi des proprietatea:
,
În baza acestei proprietăți și ținând cont de regula de construcție a inversei (vezi [16]) rezultă imediat că pentru un inel comutativ R avem
.
Astfel,
,
.
Vom spune că R este inel fără divizori ai lui zero dacă pentru orice avem . Un inel comutativ R cu și fără divizori ai lui zero se numește domeniu de integritate. Un inel K cu în care orice element este inversabil în raport cu înmulțirea se numește corp strâmb. Astfel, Q, R, C, cu p număr prim sunt corpuri, iar Z, , , sunt domenii de integritate.
Fie acum S un inel. O submulțime R a lui S se numește subinel (unitar) al lui S dacă R este subgrup al lui , R este parte stabilă a lui S în raport cu înmulțirea și , unde 1 este elementul unitate al lui S. Astfel, Z este subinel al lui Q, este subinel al lui , este subinel al lui etc. Dacă și
,
atunci R este subinel al lui S.
Observăm că dacă R este subinel al lui S, atunci R este parte stabilă a lui S în raport cu adunarea și înmulțirea și R are structură de inel în raport cu operațiile induse.
Fie un corp L. O submulțime K a lui L se numește subcorp al lui L dacă K este subinel (unitar) al lui L și pentru orice avem . Astfel, Q este subcorp al lui R, R este subcorp al lui C, este subcorp al lui R. Evident, orice subcorp K al lui L este corp față de operațiile induse de adunarea și înmulțirea din L. Spunem că E este un supracorp al corpului F dacă E este un corp și F este subcorp al lui E.
1.2 Definiția inelelor euclidiene. Exemple
Definiția 1.2.1 [1] O relație pe o mulțime nevidă M se numește relație de ordine dacă ea este reflexivă, antisimetrică și tranzitivă. În acest caz, se numește mulțime ordonată.
Observația 1.2.2 O relație de ordine într-o mulțime M se notează cu semnul , iar dacă , atunci în loc de se scrie și se citește ”x este mai muic sau egal cu y”.
Putem astfel defini pe Z relația de ordine „” prin
astfel încât .
Când și , scriem și spunem că a este strict mai mic ca b.
Cum rezultă că numerele naturale pot fi aranjate într-un șir infinit strict crescător
. (1.1)
Orice mulțime nevidă A de numere naturale conține un cel mai mic număr, cu alte cuvinte, N este o mulțime bine ordonată. Mai exact, se acceptă:
Axioma bunei ordonări: oricare ar fi , există astfel încât
.
Într-o abordare naivă, cel mai mic număr din este primul număr întâlnit în șirul (1.1) atunci când este inspectat de la stânga la dreapta.
Pe baza axiomei bunei ordonări se poate demonstra Principiul inducției matematice:
Propoziția 1.2.3 [1] Fie și pentru fiecare fie afirmația . Presupunem că
i) este adevărată.
ii) Dacă este adevărată pentru orice , atunci și este adevărată.
În aceste condiții, afirmația este adevărată oricare ar fi .
Demonstrație:
Fie A mulțimea numerelor naturale pentru care nu este adevărată. Dacă și n este cel mai mic număr din A, atunci și este adevărată oricare ar fi .
Aplicând ii) rezultă că afirmația este adevărată, ceea ce este o contradicție.
Q.E.D.
Un rezultat fundamental privind aritmetica mulțimii numerelor naturale N este:
Teorema 1.2.4 [1] (Teorema împărțirii cu rest). Oricare ar fi există astfel încât
.
Demonstrație:
Fie . Cum , avem , deci . Fie cel mai mic număr din A. Avem . Rămâne de arătat că . În caz contrar avem , de unde . Rezultă că , deci , de unde , ceea ce este o contradicție.
Q.E.D.
Pentru a putea stabili o serie de proprietăți de natură aritmetică pentru inelul Z al numerelor întregi și pentru inelele de polinoame , K corp comutativ, vom aborda această problematică pentru clasa inelelor euclidiene, care conține inelele Z și , K corp comutativ.
Definiția 1.2.5 [1] Fie R un domeniu de integritate și . Spunem că R este inel euclidian dacă există o funcție cu proprietatea că oricare ar fi cu , există astfel încât
și dacă .
Cu notația consemnăm faptul că R este inel euclidian în raport cu funcția .
Exemplul 1.2.6 Inelul Z este euclidian în raport cu funcția
.
În adevăr, folosind Teorema 1.2.4, există astfel încât cu . Când și avem , deci putem lua . Când și , avem , deci și putem lua . La fel se procedează și în cazul și .
Exemplul 1.2.7 Inelul , K corp comutativ, este euclidian în raport cu funcția
.
Într-adevăr, fie cu . Trebuie să arătăm că există astfel încât
cu când .
Vom proceda prin inducție după n. Dacă luăm și .
Dacă , fie
.
Dacă luăm și . Dacă și , . Presupunând rezultatul adevărat pentru polinoamele cu grad , există astfel încât
cu când .
Rezultă că
și putem lua și .
Exemplul 1.2.8 Inelul al întregilor lui Gauss este euclidian în raport cu funcția
,
unde .
În adevăr, să observăm că
.
Fie acum . Există astfel încât . Alegem astfel încât
.
Dacă notăm și , atunci
.
Luăm și . Avem și cum
,
rezultă că este inel euclidian.
Exemplul 1.2.9 Orice corp comutativ K este inel euclidian în raport cu funcția .
Relația de divizibilitate în inele euclidiene
Fie R un domeniu de integritate și . Vom spune că b divide pe a, și scriem , dacă există astfel încât . Vom spune în acest caz că b este divizor al lui a, a este multiplu al lui b și că q este un cât al împărțirii lui a prin b. Să observăm că dacă , atunci și în acest caz orice este un cât al împărțirii lui a prin b.
Definiția 1.3.1 [1] Fie R un domeniu de integritate și. Un element se numește cel mai mare divizor comun (în cele ce urmează vom folosi notația cmmdc) al lui a și b dacă următoarele două condiții sunt satisfăcute:
i) și;
ii) pentru orice cu și avem .
Q.E.D.
Două elemente a și b ale unui domeniu de integritate R se numesc asociate în divizibilitate și scriem dacă și . Se poate arăta ușor că dacă și numai dacă cu .
Să observăm că dacă satisface de asemenea condițiile i) și ii) de la definiția precedentă, atunci și , i.e. . Reciproc, dacă d este un cmmdc al lui a și b și atunci este de asemenea un cmmdc al lui a și b. Așadar cmmdc a două elemente din R, în cazul în care există, este unic determinat până la o asociere în divizibilitate.
Dacă d este un cmmdc al lui a și b, vom folosi notațiile
cmmdc sau.
Să observăm că semnul de egalitate din cmmdc este ușor abuziv, deoarece cmmdc este unic determinat doar până la o asociere în divizibilitate. De exemplu, în cmmdc dar și cmmdc. Mai riguros, ar trebui să scriem .
Dacă spunem că a este prim cu b sau că a și b sunt elemente relativ prime.
Cum și, unde K este un corp comutativ, rezultă că cmmdc d în caz că există este unic dacă cerem ca când și cerem ca d să fie monic (adică d are coeficientul dominant egal cu 1) când.
Observația 1.3.2 [1] Dacă R este un domeniu de integritate și cu, atunci există și avem. În particular oricare ar fi , iar când , avem.
Dacă și , atunci a și b au aceiași divizori comuni ca b și r. În particular există dacă și numai dacă există și în acest caz .
Q.E.D.
Existența cmmdc în inele euclidiene este demonstrată de rezultatul următor:
Propoziția 1.3.3 [1] Fie un inel euclidian. Următoarele afirmații sunt adevărate pentru oricare :
i) a și b admit un cmmdc;
ii) dacă d este cmmdc al lui a și b, atunci există astfel încât .
Demonstrație:
Din definiție putem deduce direct că dacă , atunci cmmdc al lui a și b este 0. Putem presupune deci că sau . Fie
.
Cum rezultă că mulțimea
este nevidă. Fie astfel încât este cel mai mic număr din . Dacă și , , atunci . Avem căci altfel cu și . Dar pentru că
.
Rezultă că , ceea ce este o contradicție. Rămâne adevărat că și analog se arată că .
Q.E.D.
Dacă R este un inel euclidian și , atunci există , nu neapărat unic determinați, astfel încât
cu dacă .
Un element q definit ca mai sus se numește cât al împărțirii lui a prin b, iar r se numește rest al împărțirii lui a prin b. Vom folosi notațiile
.
Dacă , atunci oricare ar fi există unic determinați astfel încât
.
În acest caz r este numit redusul modulo m al lui a și alături de notația vom folosi încă notația .
De asemenea, dacă , K corp comutativ, atunci există polinoamele unic determinate astfel încât
cu dacă .
Polinomul r se numește redusul modulo g al lui f și alături de notația se mai folosește și notația .
Algoritmul lui Euclid. Lema chineză a resturilor
În inelele euclidiene R există o metodă efectivă de calcul pentru cmmdc precum și o metodă efectivă de calcul pentru elemente astfel încât (elementele s și t sunt numite coeficienții Bézout pentru a și b).
Pentru calculul lui cmmdc într-un inel euclidian ne putem restrânge la cazul și .
Vom folosi faptul că nu există un șir infinit strict descrescător
de numere naturale. Într-adevăr, există astfel încât oricare ar fi pentru că este o mulțime bine ordonată. În particular, contrar ipotezei .
Date elementele cu și vom defini și pentru orice cu proprietatea că , definim .
Așadar
când .
Avem
și deci există astfel încât și , adică
(1.2)
Relațiile (1.2) de împărțiri cu rest poartă numele de algoritmul lui Euclid pentru cmmdc.
Cum , avem . Acum, din egalitatea
rezultă că ș.a.m.d. Se obține:
.
Numărul n se numește lungimea euclidiană a perechii și este o măsură a complexității calculului pentru cmmdc. Am obținut următoarea concluzie:
Concluzia 1.4.1 Dacă este un inel euclidian și a, b sunt elemente nenule din R atunci cmmdc este egal cu ultimul rest diferit de zero din Algoritmul lui Euclid pentru a și b.
Într-un inel euclidian putem calcula și coeficienții Bézout. Pentru cu definim alături de elementele și elementele pentru prin
,
.
Avem
. (1.3)
În adevăr, pentru și afirmația (1.3) se verifică imediat. Dacă , iar afirmația (1.3) este adevărată pentru și i, atunci
deci afirmația (1.3) este adevărată și pentru . În particular avem
cmmdc,
deci sunt coeficienții Bézout pentru a și b, unde n este lungimea euclidiană a perechii a,b.
Algoritmul lui Euclid, întregit cu operațiile de determinare a coeficienților Bézout se numește Algoritmul lui Euclid extins.
Propoziția 1.4.2 [12] Într-un inel euclidian orice două elemente au un cel mai mare divizor comun și un cel mai mic multiplu comun.
Demonstrație:
Pentru demonstrația acestei propoziții vom utiliza raționamentul care se face pentru a arăta că pentru Z este adevărată afirmația: altfel spus, vom aplica succesiv teorema împărțirii întregi, adică algoritmul lui Euclid. Fie a, b două elemente din inelul euclidian R. Dacă unul dintre aceste elemente este nul, atunci se observă că celălalt este un cel mai mare divizor comun al lor. Putem presupune deci că , . Aplicând teorema împărțirii întregi elementelor a și b obținem , unde sau , apoi dacă , aceeași teoremă o aplicăm elementelor b și , , unde sau ; dacă , obținem analog , cu sau și se continuă mereu dacă restul obținut este diferit de zero.. Ținând seama de algoritmul lui Euclid descris la începutul paragrafului, obținem relațiile (1.4):
(1.4)
unde , .
Din relațiile (1.4) se vede că divide pe , apoi că divide pe etc. Deci divide pe a și b. Fie acum c un divizor comun al lui a și b. Atunci din relațiile (1.4) rezultă că c divide pe , apoi că c divide pe etc. Adică c divide pe . A doua afirmație a propoziției rezultă din cea precedentă și din faptul că mulțimea numerelor raționale este numărabilă.
Se poate extinde definiția cmmdc pentru un număr finit de elemente dintr-un domeniu de integritate ca fiind un element care divide pe și orice divizor comun c pentru este și un divizor al lui d. Vom folosi notația
sau
și avem .
Fie acum un inel euclidian și . Să observăm că dacă și numai dacă există astfel încât . Într-adevăr, dacă , atunci din Propoziția 1.3.3 deducem că există cu . Reciproc, dacă , fie cu și . Atunci , i.e.,. Cum evident și deducem că .
Propoziția 1.4.2 [1] Fie R un inel euclidian și . Avem
i) Dacă și , atunci .
ii) Dacă și , atunci .
iii) Dacă , și , atunci .
iv) .
Demonstrație:
i) Fie astfel încât și . Avem
,
de unde .
ii) Fie astfel încât . Avem și cum , rezultă că .
iii) Fie astfel încât . Avem . Cum și , există cu și ,
deci
.
Rezultă că .
iv) Fie și cu . Cum , rezultă că orice divizor comun al lui ac și bc este divizor și al lui cd. Pe de altă parte, cd este divizor comun pentru ac și bc. Rezultă că .
Q.E.D.
Observația 1.4.3 [1] Dacă și =1 pentru orice , atunci se arată ușor prin inducție matematică după n că .
Observația 1.4.4 [1] Dacă pentru și oricare ar fi , atunci, prin inducție matematică după n, deducem că .
Teorema 1.4.5 [1] (Lema chineză a resturilor). Fie R un inel euclidian și astfel încât oricare ar fi . Atunci, oricare ar fi , există astfel încât . În plus, dacă are proprietatea că , atunci .
Demonstrație:
Fie și
.
Conform Observației 1.4.3 rezultă că . Fie astfel încât
.
Fie , numite elemente de interpolare Lagrange. Evident și oricare ar fi .
Fie . Cum
,
rezultă că divide pe .
Pentru orice ca în enunț, avem evident , deci . Rezultă că în baza Observației 4.1.4.
Q.E.D.
Dacă atunci folosim notația
.
Numerele din sunt resturile posibile care se obțin când împărțim numerele prin m.
Fie astfel încât oricare ar fi . Dacă atunci aplicația
este bijectivă. În adevăr, dacă cu , atunci
.
Conform Observației 4.1.4 rezultă că și cum , avem neapărat . Așadar este o aplicație injectivă. Cum este o funcție între două mulțimi cu același număr m de elemente, rezultă că este și surjectivă, deci bijectivă.
Pentru , se numește reprezentarea modulară a lui a în sistemul de module .
Polinoame de interpolare Lagrange
Definiția 1.5.1 [12] Un inel unitar nenul în care orice element nenul este inversabil se numește corp. Dacă operația de înmulțire este comutativă, corpul se numește comutativ. Uneori corpurile necomutative sunt numite inele cu diviziune, iar corpurile comutative câmpuri.
Să considerăm inelul euclidian , unde K este un corp comutativ. Fie astfel încât oricare ar fi . Cum , avem oricare ar fi .
Pentru orice polinom și orice i, există și astfel încât
.
Calculând valoarea egalității de mai sus în obținem
,
deci
.
Deducem că
, ,
adică restul împărțirii lui prin este egal cu , .
Aplicând Teorema 1.4.5 rezultă că pentru orice există un unic polinom , grad astfel încât
, ,
adică , .
În cele ce urmează vom arăta cum poate fi determinat un astfel de polinom :
Fie și , .
Avem , .
Există astfel încât
, .
Cum , deoarece altfel ar rezulta că , absurd, putem scrie
, .
Rezultă că și sunt coeficienții Bézout pentru polinoamele și .
Observația 1.5.2 Pentru orice , , vom nota prin sau inversul al elementului a în corpul K.
Definiția 1.5.3 [1] Se numesc polinoame bazice de interpolare Lagrange, polinoamele , definite prin
Luând
,
avem , și grad .
Polinomul de grad pentru care avem , , este unic determinat. Într-adevăr, dacă este astfel încât grad g și , , atunci polinomul de grad are r rădăcini distincte în K, și anume , deci neapărat , adică .
Definiția 1.5.4 [1] Polinomul se numește polinomul de interpolare Lagrange și este singurul polinom din al cărui grafic „trece” prin cele r puncte date din „planul” .
Observația 1.5.5 Cu notațiile de la polinoamele de interpolare Lagrange să observăm că , , unde notează derivata formală a polinomului . Rezultă că
, .
Fie acum K un corp comutativ, și . Deoarece inelul este euclidian, există și astfel încât
.
Calculând valoarea relației precedente în a, obținem
,
deci
.
Teorema 1.5.6 [1] (Bézout) Fie și . Polinomul divide pe f dacă și numai dacă .
Corolarul 1.5.7 [1] Fie și elemente distincte ale lui K. Polinomul f se divide prin dacă și numai dacă , .
Demonstrație:
„”
Dacă f se divide prin atunci există astfel încât
,
de unde , .
„”
Vom proceda prin inducție după n. Conform Teoremei 1.5.5, afirmația este adevărată când . Vom presupune că . Astfel
cu , deci
, .
Cum , , avem , și conform ipotezei de inducție, g se divide prin , deci f se divide prin .
Q.E.D.
Definiția 1.5.8 [1] Fie K un corp comutativ și cu grad f . Spunem că polinomul f este reductibil peste K sau în dacă există astfel încât
, grad și grad,
numită descompunere netrivială în a lui f. În caz contrar se spune că f este ireductibil peste K sau în .
Observația 1.5.9 [1] Fie , . Evident, polinoamele a și af divid pe f, oricare ar fi . Polinomul f este ireductibil peste K dacă și numai dacă a și af cu sunt singurii divizori din ai lui f. Când f este polinom monic (adică are coeficientul dominant egal cu 1) f este ireductibil peste K dacă singurele polinoame monice din care divid pe f sunt 1 și f.
Q.E.D.
Exemplul 1.5.10 Orice polinom de grad 1 din este ireductibil peste K pentru că nu poate fi reprezentat ca produsul a două polinoame cu gradul mai mic ca 1.
Exemplul 1.5.11 Fie , . Dacă f este ireductibil peste K, atunci oricare ar fi . În adevăr, dacă cu , avem cu , și , absurd.
Reciproc, dacă sau și oricare ar fi , atunci f este ireductibil peste K. În adevăr, dacă f nu este ireductibil, atunci admite un divizor de forma , cu , . Rezultă că , unde , absurd.
Lema 1.5.12 [1] Fie K un corp comutativ și , f ireductibil. Dacă , atunci sau .
Demonstrație:
Presupunem că f este polinom monic. Dacă afirmația din enunț nu este adevărată, atunci și . Cum singurii divizori monici ai lui f sunt 1 și f, rezultă că și , deci , conform Propoziției 1.4.2. Dar , de unde , ceea ce este o contradicție.
Q.E.D.
Restrângându-ne la polinoamele monice, obținem în următorul rezultat analog Teoremei fundamentale a Aritmeticii adevărată în mulțimea numerelor naturale N:
Teorema 1.5.13 [1] Fie K un corp comutativ și , f monic, . Există polinoamele monice ireductibile din , unic determinate mai puțin ordinea, astfel încât
.
Demonstrație:
Dacă f este ireductibil peste K luăm și . În caz contrar există , g și h polinoame monice, astfel încât
, , .
Raționând prin inducție după grad f, rezultă că g și h sunt produse finite de polinoame monice ireductibile și atunci are aceeași proprietate.
Pentru a demonstra unicitatea, fie
două reprezentări ale lui f ca produse finite de polinoame monice ireductibile. Rezultă că divide produsul . Conform Lemei 1.5.12 există j, , astfel încât . Reindexând eventual polinoamele , putem presupune că , adică . Cum și sunt polinoame monice ireductibile , rezultă că .
Cum inelul este domeniu de integritate, putem simplifica cu în egalitatea
și obținem
.
Presupunând că unicitatea descompunerii este adevărată pentru polinoamele care admit cel puțin o reprezentare ca produs de polinoame monice ireductibile, rezultă că , deci și , .
Q.E.D.
Observația 1.5.14 Teorema precedentă arată că orice polinom monic , , admite o reprezentare unică sub forma:
(1.5)
cu polinoame monice ireductibile distincte și , . Reprezentarea (1.5) se numește descompunerea canonică a polinomului f.
Q.E.D.
În Capitolul 5 vom prezenta metode efective de determinare a descompunerii canonice a unui polinom , în cazul și în cazul , p număr prim.
Observația 1.5.15 Cum polinoamele monice ireductibile din sunt de forma , rezultă că oricare ar fi un polinom monic cu există numerele complexe distincte și unic determinate astfel încât
.
De asemenea, dacă , , f monic, atunci f admite o reprezentare unică sub forma
cu , , și , și , .
Capitolul II
ELEMENTE DE TEORIA CORPURILOR
2.1 Extinderi, gradul unei extinderi
În toate considerațiile care urmează în acest capitol toate corpurile sunt presupuse comutative.
Definiția 2.1.1 [1] Fie K un corp. Se numește extindere a corpului K un corp L care conține pe K drept subcorp, adică și operațiile corpului L restrânse la K coincid cu operațiile lui K.
Observația 2.1.2 Vom nota faptul că L este o extindere a lui K cu sau L/K . Se mai spune despre că este o extindere de corpuri.
Exemplul 2.1.3 Corpul R este o extindere a lui Q, corpul C este o extindere a lui R și C este o extindere a lui Q. Așadar , și sunt exemple de extinderi de corpuri.
Fie K un corp comutativ. Dacă V este o mulțime nevidă, o aplicație se numește lege de compoziție externă pe V cu scalari în K. Dacă și , notăm . Elementul , notat și , se numește produsul lui v cu scalarul .
Definiția 2.1.4 [1] Fie K un corp. Se numește spațiu vectorial peste K un grup abelian pe care este dată o lege de compoziție externă cu scalari în K,
, ,
astfel încât sunt satisfăcute condițiile:
1) ,
2) ,
3) ,
4) ,
oricare ar fi și .
Spațiile vectoriale se mai numesc și spații liniare. Dacă V este un spațiu vectorial peste K, elementele lui K se numesc scalari, elementele lui V se numesc vectori, iar operația grupului se numește adunarea vectorilor. Elementul neutru al grupului se numește vectorul zero și va fi notat cu 0 ca și scalarul zero. Se mai folosește și notația pentr a indica faptul că V este spațiu vectorial peste K.
Când este o extindere de corpuri, L are o structură naturală de spațiu vectorial peste K. Vectorii sunt elementele lui L, adunarea vectorilor este operația de adunare a corpului L, scalarii sunt elementele lui K, iar produsul al scalarului cu vectorul este produsul în corpul L al lui a cu x. O bază a spațiului vectorial se mai numește și K-bază a lui L sau bază a extinderii .
Dimensiunea a lui L ca spațiu vectorial peste K se notează cu și se numește gradul extinderii . Când gradul este finit spunem despre că este o extindere finită și scriem . În caz contrar, spunem că gradul extinderii este infinit și consemnăm aceasta cu notația .
Definiția 2.1.5 [1] Fie o extindere de corpuri și . Spunem că u este algebric peste K sau, mai scurt, că u este algebric/K sau că u este element algebric al extinderii , dacă există , astfel încât . În caz contrar spunem că u este element transcendent al extinderii .
Fie o extindere și , u algebric peste K. Un polinom nenul din de grad minim care admite pe u ca rădăcină divide orice polinom astfel încât . Printre polinoamele de grad minim din care admit pe u ca rădăcină există un unic polinom care este monic, numit în continuare polinomul minimal al lui u peste K și notat .
Lema 2.1.6 [1] Fie o extindere de corpuri, un element algebric peste K și polinomul minimal al lui u peste K. Atunci f este ireductibil peste K.
Demonstrație:
Fie . Dacă f nu este ireductibil peste K atunci există astfel încât , și . În corpul L avem , de unde sau , ceea ce contrazice definiția lui f.
Q.E.D.
Observația 2.1.7 Fie o extindere și un polinom monic ireductibil peste K. Dacă și , atunci pentru că divide pe f și f e ireductibil.
Fie o extindere de corpuri și . Este evident că L este o K-algebră de morfism structural incluziunea canonică . Am folosit notația pentru K-subalgebra lui L generată de u. Avem
și coincide cu cel mai mic subinel al lui L care conține pe K și pe u.
Teorema 2.1.8 [1] Fie o extindere de corpuri și .
1) Următoarele afirmații sunt echivalente:
i) u este algebric peste K;
ii) este subcorp al lui L.
2) Dacă u este algebric, și , atunci și este o bază a lui ca spațiu vectorial peste K.
Demonstrație:
1)
Notăm . Fie , și fie astfel încât . Cum rezultă că și deci cmmdc. Există astfel încât , de unde , deci.
Este suficient să analizăm cazul . Atunci , deci există , astfel încât . Avem . Dacă , avem și . Rezultă că u este algebric peste K.
(2) Fie și astfel încât . Există atunci astfel încât
,
unde .
Avem
cu , deci este un sistem de generatori pentru ca spațiu vectorial peste K.
Dacă nu sunt liniar independenți peste K, atunci există în K, nu toți nuli, astfel încât
.
Dacă , avem și , ceea ce este absurd deoarece h are gradul mai mic ca n.
Q.E.D.
Teorema 2.1.9 [1] (Formula gradelor) Dacă extinderile de corpuri și sunt finite, atunci este o extindere finită și
.
Reciproc, dacă extinderea este finită, atunci și extinderile și sunt finite.
Demonstrație:
Fie , , o K-bază a lui F (adică o bază a K-spațiului vectorial ) și o F-bază a lui L.
Dacă , atunci cu , . Pentru orice j, , avem
cu , și deci
.
Rezultă că elementele , , , formează un sistem de generatori pentru L ca spațiu vectorial peste K.
Dacă
,
unde , atunci
.
Rezultă că , , deci pentru și , deoarece sunt liniar independenți peste F, iar sunt liniar independenți peste K, deci
.
Reciproc, dacă , atunci pentru că F este un K-spațiu vectorial al lui L. Avem și pentru că vectorii din L liniar independenți peste F sunt liniar independenți și peste K.
Q.E.D.
2.2 Extinderi algebrice
Definiția 2.2.1 [1] O extindere de corpuri se numește algebrică dacă orice element este algebric peste K.
Lema 2.2.2 [1] Orice extindere finită este algebrică.
Demonstrație:
Fie și . Cum L considerat ca spațiu vectorial peste K are dimensiunea n, elementele , luate ca vectori, nu sunt liniar independente peste K. Există deci , nu toți nuli, astfel încât . Dacă , atunci , și . Rezultă că u este algebric peste K.
Q.E.D.
Observația 2.2.3 Fie lanțul de extinderi de corpuri și . Dacă u este algebric peste K atunci u este algebric și peste F pentru că .
Lema 2.2.4 [1] Fie o extindere și elementele algebrice peste K. Atunci:
i) ;
ii) .
Demonstrație:
1) Conform Teoremei 2.1.8 avem . Presupunem că și că afirmația este adevărată pentru . Vom avea
.
2) Când aplicăm Teorema 2.1.8. Dacă și dacă presupunem afirmația adevărată pentru , avem . Cum este algebric peste datorită Observației 2.2.3, avem conform Teoremei 2.1.8. Aplicând Formula gradelor lanțului (Teorema 2.1.9) de extinderi de corpuri
obținem .
Q.E.D.
Propoziția 2.2.5 [1] Fie lanțul de extinderi de corpuri .
i) Dacă extinderea este algebrică și este algebric peste F, atunci u este algebric peste K;
ii) Extinderea este algebrică dacă și numai dacă ambele extinderi și sunt algebrice.
Demonstrație:
i) Există , , astfel încât . Fie . Evident , deci u este algebric și peste . Rezultă că . Avem și din Lema 2.2.4. Aplicând Teorema 2.1.9 rezultă că . Cum , conform Lemei 2.2.2, rezultă că u este algebric peste K.
ii) Dacă extinderea este algebrică, atunci orice element din L, în particular orice element din F, este algebric peste K, sau altfel spus, extinderea este algebrică. Din Observația 2.2.3 rezultă că și extinderea este algebrică.
Reciproc, dacă ambele extinderi și sunt algebrice, atunci orice element este algebric peste F, deci și peste K conform punctului i). Rezultă că extinderea este algebrică.
Q.E.D.
Definiția 2.2.6 [1] Dacă este o extindere de corpuri, atunci
se numește închiderea algebrică a lui K în L.
Propoziția 2.2.7 [1] Dacă este o extindere de corpuri, atunci
i) este subcorp al lui L și ;
ii) .
Demonstrație:
i) Dacă și , atunci , și . Rezultă . Pentru orice avem conform Lemei 2.2.4 și deci extinderea este algebrică conform Lemei 2.2.2. Cum , , și (când ) sunt din , deducem că este subcorp al lui L.
ii) Fie . Cum extinderea este algebrică și u este algebric peste , rezultă că u este algebric peste K conform Propoziției 2.2.5, adică și deci . Din i) avem , ceea ce arată că .
Q.E.D.
Vom prezenta în cele ce urmează o extindere a Teoremei împărțirii cu rest. Toate inelele care intervin în continuare sunt presupuse comutative și unitare. Fie R un inel. Se numește extindere a lui R un inel S care conține pe R ca subinel (unitar).
Dacă R este un inel, atunci în inelul se poate efectua împărțirea cu rest printr-un polinom , având coeficientul dominant inversabil în R.
Teorema 2.2.8 [1] Fie R un inel și cu . Atunci, oricare ar fi un polinom , există polinoamele unic determinate astfel încât cu dacă .
Demonstrație:
Fie . Existența polinoamelor q și r se stabilește la fel ca în cazul când R este un corp. Dacă luăm și , iar când se face inducție după m, ceea ce este posibil înlocuind pe f cu polinomul ,
.
Pentru stabilirea unicității polinoamelor q și r să observăm că și oricare ar fi , datorită faptului că .
Dacă sunt două reprezentări ale lui f ca în enunț, atunci . Dacă , avem și și atunci
,
ceea ce este ocontradicție. Rămâne adevărat , de unde rezultă și .
Q.E.D.
Definiția 2.2.9 [1] Fie R un inel și cu . Pentru orice , restul împărțirii lui f prin se numește redusul modulo al polinomului f și se notează cu .
Să observăm că dacă , atunci .
Corolarul 2.2.10 [1] (Bézout). Fie R un inel, și . Atunci divide pe f în (i.e. există cu ) dacă și numai dacă .
Demonstrație:
Aplicând Teorema 2.2.8 polinomului dat f și polinomului monic , există astfel încât
, cu dacă .
Rezultă că , deci luând valoarea în a a polinoamelor de mai sus, obținem
.
Dacă atunci, din unicitatea lui r, deducem că , adică și reciproc, dacă atunci , deci , adică .
Q.E.D.
Observația 2.2.11 oricare ar fi pentru că și se invocă unicitatea restului.
În particular și este polinom monic. Așadar, în calculul reduselor modulo ne putem mărgini la cazul când este polinom monic.
Observația 2.2.12 Dacă cu , atunci . Într-adevăr, dacă notăm , atunci se poate scrie cu dacă , deci . Din unicitatea restului se deduce că .
Prin analogie cu inelul de resturi modulo un număr , care angajează teorema de împărțire cu rest în inelul Z, definim în acest subcapitol inelul de resturi modulo un polinom arbitrar nenul din având coeficientul dominant inversabil, unde R este un inel unitar comutativ arbitrar; construcția lui , preluată din [3], se bazează pe Teorema cu rest relativ la asemenea polinoame .
În tot ce va urma R va desemna un inel comutativ (unitar) și
un polinom fixat din de cu .
Polinomul permite definirea unei operații algebrice pe mulțimea :
,
numită înmulțirea modulo a polinoamelor din . Reamintim că pentru orice am notat prin restul, unic determinat conform Teoremei 2.2.8, al împărțirii polinomului h prin .
Lema 2.2.13 [1] Înmulțirea modulo pe are proprietățile următoare:
Dacă și , atunci
oricare ar fi .
ii) , oricare ar fi .
Demonstrație:
i) Fie astfel încât și , unde
.
Rezultă că
și .
Aplicând Observația 2.2.12 obținem
.
ii) Cum se poate aplica i) și avem
și analog
.
Dar , de unde .
Q.E.D.
Dacă și definim recurent prin
Lema 2.2.14 [1] Ridicarea la putere față de operația algebrică are următoarele proprietăți:
i) oricare ar fi și ;
ii) ,
unde cu .
Demonstrație:
i) Presupunem că . Cum , aplicând Lema 2.2.13 i) obținem
.
ii) Evident dacă . Este clar că putem scrie
,
deci restul împărțirii lui prin este .
Așadar,
Q.E.D.
Pentru polinomul dat cu , notăm
.
De exemplu, și . Totuși, dacă inelul R unde polinomul dat are coeficienții este indicat explicit, atunci vom folosi notația simplificată în loc de .
Observăm că și că este o parte stabilă a lui în raport cu adunarea uzuală a polinoamelor și în raport cu operația . În plus, pentru orice și avem
,
,
,
.
Este evident că este un inel comutativ (unitar), extindere a inelului R, numit inelul resturilor modulo . Observăm că dacă și numai dacă .
Unul dintre rezultatele fundamentale din teoria corpurilor este acela care stabilește că pentru orice polinom neconstant , K corp comutativ arbitrar, există un corp L, extindere a lui K și un astfel încât . Majoritatea matematicienilor demonstrează acest rezultat luând drept L un corp izomorf cu inelul factor al inelului modulo idealul maximal generat de un divizor ireductibil al lui f. În acest subcapitol vom prezenta o demonstrație elementară a rezultatului de mai sus după [3], în care se evită conceptele mai sus menționate; demonstrația se bazează numai pe inelul resturilor modulo un polinom discutat anterior.
Teorema 2.2.15 [1] Următoarele afirmații sunt adevărate pentru un polinom de grad cu :
i) polinomul admite în inelul () rădăcina ;
ii) dacă R este un corp K, atunci inelul este corp dacă și numai dacă este ireductibil în inelul .
Demonstrație:
i) Deoarece , avem . Valoarea în a polinomului este
.
ii) Presupunem că este corp. Dacă nu este ireductibil peste K, atunci există astfel încât în . Evident și , dar , ceea ce este o contradicție. Rămâne deci adevărat că este ireductibil peste K.
Reciproc, presupunem că este ireductibil peste K și fie , . Cum rezultă că și deci cmmdc. Există astfel încât . Fie . Avem
.
Așadar, r este inversul lui f în , deci este corp.
Q.E.D.
Corolarul 2.2.16 [1] Fie K un corp și , . Atunci există o extindere de corpuri și astfel încât .
Demonstrație:
Fie , g ireductibil astfel încât . Dacă , atunci cu . Este clar că este o rădăcină în K a lui g, deci și a lui f, iar drept L putem lua în acest caz pe K.
Dacă , atunci este un corp și este rădăcină pentru g conform lui Teoremei 2.2.15. Cum în , rezultă că .
Teorema 2.2.17 [1] Fie K un corp și
cu și . Există atunci o extindere E a lui K și elementele , nu neapărat distincte, astfel încât
.
Demonstrație:
Se procedează prin inducție după n. Dacă luăm și . Presupunem că . Conform Corolarului 2.2.16, există o extindere a lui K și astfel încât . Aplicând Corolarul 2.2.10, rezultă că există astfel încât . Conform ipotezei de inducție, există o extindere E a lui și astfel încât
.
Atunci, în avem
.
Q.E.D.
Observația 2.2.18 Cu notațiile de la Teorema 2.2.17, avem , , adică sunt rădăcini din E ale lui . În corpul E sau chiar într-o extindere L a lui E, polinomul nu mai are alte rădăcini. În adevăr, dacă cu atunci
în corpul L. Există i astfel încât , deci .
Observația 2.2.19 Aplicând Teorema 2.2.15 i) și Corolarul 2.2.10, rezultatul de la Teorema 2.2.17 poate fi generalizat, urmând aceeași idee de demonstrație, astfel: dacă R este un inel comutativ și este un polinom din cu și , atunci există o extindere comutativă S a lui R (aceasta înseamnă că S este un inel comutativ care conține pe R ca subinel unitar) și , nu neapărat distincte, astfel încât .
Definiția 2.2.20 [1] Fie K un corp și
cu și . O extindere L a lui K se numește corp de descompunere a lui (sau pentru) f peste K dacă sunt satisfăcute următoarele două condiții:
f se descompune în factori liniari în , adică există elementele astfel încât
;
(2) .
Observația 2.2.21 Conform Teoremei 2.2.17, există o extindere E a lui K și astfel încât
și luând se obține un corp de descompunere al lui f inclus în E. Cum este algebric peste K, , avem conform Lemei 2.2.4. Cum singurele rădăcini din E ale lui f sunt , rezultă că L este unicul corp de descompunere al lui f inclus în E.
2.3 Corpuri finite
Propoziția 2.3.1 [1] Fie G un grup și un element de ordin finit cu . Atunci
și ,
unde prin am notat subgrupul lui G generat de x.
Demonstrație:
Cum , rezultă incluziunea
.
Fie acum . Atunci cu . Conform Teoremei împărțirii cu rest în Z, avem , unde și , deci
,
de unde rezultă și incluziunea inversă, adică egalitatea celor două mulțimi din enunț.
Dacă cu , atunci . Dar , în contradicție cu definiția ordinului lui x. Așadar, elementele sunt două câte două distincte, deci .
Q.E.D.
Corolarul 2.3.2 [1] Fie G un grup finit de ordin n. Atunci pentru orice .
Demonstrație:
Fie . Considerăm subgrupul al lui G generat de x. Cum G este finit deducem că este un subgrup finit. Rezultă că x este de ordin finit, și , conform Propoziției 2.3.1. În baza teoremei lui Lagrange, avem , deci pentru un anumit . Atunci .
Q.E.D.
Se spune că un corp este finit dacă mulțimea subiacentă a acestuia este finită. Dacă p este un număr prim, atunci este un corp finit cu p elemente. Vom nota cu grupul multiplicativ al elementelor nenule ale unui corp K.
Vom da în continuare ceea ce se mai numește și Mica Teoremă a lui Fermat pentru corpuri finite (Teorema 2.3.3). Enunțul original al Micii Teoreme a lui Fermat se referă la numere întregi și nu la corpuri finite: pentru orice număr prim și orice care nu este divizibil cu p, are loc congruența . Pentru a face legătura cu Teorema 2.3.3 se transpune echivalent această congruență din inelul Z în egalitatea din corpul finit . Din modul în care este definită înmulțirea în , avem , deci enunțul original al Micii Teoreme a lui Fermat pentru numere întregi este echivalent pentru corpul finit cu următorul enunț: . Prin urmare, enunțul Teoremei 2.3.3 este o extindere naturală de la corpul finit la orice corp finit F.
Teorema 2.3.3 [1] (Mica Teoremă a lui Fermat) Dacă F este un corp finit cu q elemente, atunci .
Demonstrație:
Dacă F este un corp finit cu q elemente atunci este un grup de ordin , de element neutru . Conform Corolarului 2.3.2, .
Q.E.D.
În continuare vom prezenta un rezultat fără demonstrație al matematicianului Nathan Jacobson, deoarece nu se cunoaște încă o demonstrație elementară elementară a lui:
Teorema 2.3.4 [1] (Teorema de comutativitate a lui Jacobson) Fie R un inel nu neapărat unitar cu proprietatea că pentru orice există un număr , , astfel încât . Atunci R este comutativ.
Combinând Teorema 2.3.4 (Teorema de comutativitate a lui Jacobson) cu Teorema 2.3.3 (Mica Teoremă a lui Fermat) se obține Teorema 2.3.5 (Teorema de comutativitate a lui Wedderburn), dată tot fără demonstrație:
Teorema 2.3.5 [1] (Teorema de comutativitate a lui Wedderburn) Orice corp finit este comutativ.
Vom enumera mai jos o serie de proprietăți de bază ale corpurilor finite:
Teorema 2.3.6 [1] (Teorema de cardinalitate) Dacă F este un corp finit și , atunci , cu p număr prim și .
Demonstrație:
Fie F un corp finit cu q elemente. Pentru a distinge numărul natural 1 de elementul unitate al corpului F, îl vom nota pe cel din urmă cu e. Dacă , unde prin am notat caracteristica corpului F, și este subcorpul prim al lui F, atunci F este spațiu vectorial de dimensiune finită m peste P. Fie o bază a lui . Pentru orice există unic determinați astfel încât . Cum pentru fiecare scalar avem p posibilități de alegere, rezultă că .
Q.E.D.
Teorema 2.3.7 [1] (Teorema de structură aditivă) Grupul aditiv al unui corp finit F este izomorf cu grupul , unde și este astfel încât .
Demonstrație:
Fie P subcorpul prim al lui F, și o bază a spațiului vectorial . Pentru orice există unic determinați astfel încât , deci putem defini aplicația
, ,
care este izomorfism de P-spații vectoriale.
Se obține astfel un izomorfism de grupuri abeliene . Pe de altă parte, grupul abelian coincide cu grupul ciclic de ordin p generat de elementul unitate e al lui F, deci . Aplicând acum o extindere de la un produs direct de două grupuri la m grupuri, deducem că există un izomorfism de grupuri . Prin compunere cu izomorfismul f de mai sus obținem un izomorfism .
Q.E.D.
Teorema 2.3.8 [1] (Teorema de ciclicitate) Grupul multiplicativ al unui corp finit F este ciclic.
Demonstrație:
Corpul finit F este comutativ în baza Teoremei de comutativitate a lui Wedderburn. Se știe că orice subgrup finit H al grupului multiplicativ al oricărui corp comutativ K este ciclic. În particular, aplicând acest rezultat pentru și , deducem că este un grup ciclic.
Q.E.D.
Dacă F este un corp finit cu q elemente, atunci orice generator al grupului ciclic , adică orice element de ordin al acestuia se numește element primitive al corpului F.
Teorema 2.3.9 [1] (Teorema de existență) Oricare ar fi numărul prim și există un corp finit cu elemente.
Demonstrație:
Fie un număr prim, și . Considerăm polinomul . Prin derivare obținem
,
deoarece și . Rezultă că cmmdc, deci f nu are rădăcini multiple. Folosind Teorema 2.2.17, există o extindere E a lui și elementele distincte din E astfel încât
.
Notăm și avem
.
Cum f nu are rădăcini multiple, avem evident .
Evident, . Dar și prin urmare rezultă că
.
De asemenea și (deoarece q este impar când și când ), oricare ar fi . Rezultă că F este subcorp cu exact q elemente al corpului E, deci F este exact ceea ce căutam.
Q.E.D.
Observația 2.3.10 Corpul F cu q elemente descris în demonstrația de mai sus conține pe . Într-adevăr, și oricare ar fi conform Micii Teoreme a lui Fermat (vezi Teorema 2.3.3), de unde deducem că avem și oricare ar fi , i.e., din modul cum am definit pe F.
Observația 2.3.11 Din demonstrația Teoremei 2.3.9 rezultă că F este chiar corpul de descompunere inclus în E al polinomului . De aici, dacă se invocă unicitatea până la un izomorfism a corpului de descompunere al unui polinom, deducem imediat Teorema de unicitate 2.3.11:
Teorema 2.3.12 [1] (Teorema de unicitate) Orice două corpuri finite cu același număr de elemente sunt izomorfe.
Demonstrație:
Fie F și două corpuri finite cu același număr de elemente . Vom demonstra că există un izomorfism (necanonic) între aceste două corpuri.
Conform Teoremei 2.3.6, există cu p prim astfel încât și . Fie P subcorpul prim al lui F și subcorpul prim al lui , ambele de cardinal p. Atunci
și ,
unde, pentru a distinge numărul natural 1 de elementul unitate al corpului F, am notat și aici ca și în demonstrația Teoremei 2.3.6, pe acesta din urmă cu e, iar cu am notat elementul unitate al corpului .
Arătăm acum că funcția canonică
,
este un izomorfism de corpuri. În primul rând, este clar că și că este o bijecție.
Fie acum . Prin împărțirea lui la p obținem , unde și . Avem
și
deoarece , deci
.
Analog se arată că . Așadar, este un izomorfism de corpuri.
Conform Teoremei 2.3.8, există astfel încât . Rezultă că
,
de unde . Fie și . Deoarece este o P-bază a lui (vezi Teorema 2.1.8 ii)) și , rezultă că . Avem
,
deci .
Este clar că aplicația
,
definită prin
este bijectivă. Se verifică imediat că
și
oricare ar fi , cu alte cuvinte este izomorfism de inele. Pentru prescurtare vom folosi notația oricare ar fi . Cum u este rădăcină a polinomului și , rezultă că f divide în polinomul . Există deci astfel încât . Aplicând izomorfismul obținem , deci divide în polinomul .
Cum f este ireductibil peste P, rezultă imediat că este ireductibil peste . Conform Teoremei 2.3.3, polinomul are q rădăcini (distincte) în , deci polinomul care este divizor în al lui are măcar o rădăcină . Polinomul fiind ireductibil, deducem că conform Teoremei 2.3.3. Cum , avem în baza Teoremei 2.1.8 ii), de unde rezultă că .
Aplicând din nou Teorema 2.1.8 ii), orice element se scrie în mod unic sub forma cu . Definim acum aplicația prin
.
Cum și rzultă imediat că aplicația este bijectivă și evident oricare ar fi .
Arătăm acum că
,
ceea ce înseamnă că este izomorfism de corpuri demonstrația va fi încheiată.
Fie deci . Cum , există polinoamele de grad cel mult , unic determinate, astfel încât și .
Împărțind polinomul la , găsim astfel încât
, .
Avem
pentru că deoarece .
Aplicând acum egalității izomorfismul , obținem , deci
deoarece . Cum pentru orice de grad cel mult avem , rezultă că
.
Q.E.D.
Observația 2.3.13 Teorema 2.3.12 se poate reformula astfel: două corpuri finite F și sunt izomorfe dacă și numai dacă .
Observația 2.3.14 Teoremele 2.3.12 și 2.3.9 se pot enunța împreună sub forma următoare: pentru orice număr prim și orice număr natural nenul n, există un corp finit cu elemente, care este unic determinat până la un izomorfism. Acesta este motivul pentru care se poate vorbi de corpul cu elemente.Notația standard folosită pentru un asemenea corp este . Pentru uniformizarea notației, corpul claselor de resturi modulo un număr prim , , va fi notat în continuare cu , corpul finit cu p elemente.
Capitolul III
INELE DE POLINOAME
Fie R un inel comutativ și unitar. În cele ce urmează vom prezenta pentru început o construcție a inelului seriilor formale peste R. Fie mulțimea funcțiilor de la N în R. Dacă scriem o astfel de funcție prin mulțimea ordonată a valorilor sale, atunci este mulțimea șirurilor
,
pentru orice .
Șirurile și sunt egale dacă și numai dacă pentru orice i.
Pe mulțimea se definesc două operații algebrice, adunarea și înmulțirea, în raport cu care devine un inel comutativ.
Dacă ,
,
adunarea se definește astfel
.
Se verifică ușor că împreună cu adunarea formează un grup abelian, adică adunarea este asociativă, comutativă, are element nul și orice element are un opus.
Elementul nul (zero) este
Iar dacă aparține lui , atunci opusul său este
.
Înmulțirea pe se definește astfel:
Dacă și aparțin lui , atunci
,
unde
,
pentru orice .
Înmulțirea pe este asociativă, comutativă și are element unitate
.
Vom demonstra mai jos asociativitatea înmulțirii:
Fie , unde
, ,
și să arătăm că . Dacă , atunci și fie , unde .
Avem
.
Dacă , unde iar , unde , avem
.
Deci pentru orice m, adică .
Comutativitatea înmulțirii rezultă imediat.
Mai mult, înmulțirea este distributivă față de adunare. Într-adevăr, cu notațiile de mai înainte rezultă
, unde , iar
, unde .
Cum operația de înmulțire pe R este distributivă față de adunare, rezultă
.
Analog are loc și relația
.
În concluzie, am demonstrat că împreună cu adunarea și înmulțirea formează un inel comutativ și unitar. Elementele inelului construit mai sus se numesc serii formale cu coeficienți în R.
Fie funcția definită prin
.
Arătăm că u este un morfism injectiv de inele.
Într-adevăr, dacă , atunci
Și
.
Mai mult, dacă , atunci și deci .
Morfismul u dă un izomorfism al lui R pe subinelul al lui , ceea ce permite să se identifice elementul a din R cu imaginea sa prin u, adică cu polinomul din . Astfel R se poate considera ca un subinel al lui .
Pe de altă parte, notăm prin X seria formală care se numește nedeterminata X.
Înmulțirea seriilor formale ne dă și, mai general, pentru orice număr natural i
.
Fie o serie formală din .
Folosind adunarea și înmulțirea definite pe se obține
.
Mai mult, după cele precedente putem scrie
obținând astfel scrierea obișnuită a unei serii formale.
Inelul se numește inelul seriilor formale în nedeterminata X cu coeficienți în inelul R și se notează prin . Inelul se mai numește și inelul seriilor formale într-o nedeterminată.
O serie formală în nedeterminata X se scrie condensat,
,
aceasta fiind pur și simplu o notație, fără sens de adunare.
O serie formală din care are doar un număr finit de coeficienți nenuli se numește polinom cu coeficienți în R. Notăm cu mulțimea polinoamelor peste R.
Dacă f este un polinom cu coeficienți în R, , există un număr natural m astfel încât , pentru orice .
Dacă este un polinom nenul din , atunci se numește gradul polinomului f, și se notează cu grad . Coeficientul , unde , se numește coeficientul dominant al polinomului f.
Pentru polinomul nul, convenim să considerăm gradul său ca fiind , adoptând convențiile uzuale și anume: , pentru orice număr natural n,. Dacă , f nenul, atunci se numesc coeficienții polinomului f, care se va scrie
.
Propoziția 3.1 [17] Mulțimea a polinoamelor împreună cu adunarea și înmulțirea seriilor formale, formează un inel.
Demonstrație:
Este evident că dacă f și g sunt polinoame din , atunci și fg sunt de asemenea polinoame din . Prin urmare este un subinel al inelului seriilor formale și deci la rândul său este un inel.
Acest inel se numește inelul polinoamelor în nedeterminata X, cu coeficienți în inelul R sau inelul polinoamelor într-o nedeterminată.
Propoziția 3.2 [17] Fie R un inel și f,g polinoame din . Atunci
1) ,
2) .
Mai mult, dacă f și g sunt nenule și coeficienții dominanți ai lui f și g nu sunt divizori ai lui zero, atunci avem egalitate.
Demonstrație:
Dacă cel puțin unul dintre polinoamele f și g este nul, atunci 1) și 2) rezultă evident având în vedere convențiile făcute: , oricare ar fi n număr natural și. Dacă f și g sunt nenule, afirmațiile 1) și 2) rezultă imediat din definiția sumei și a produsului a două polinoame.
Fie , , astfel încât și să nu fie divizori ai lui zero.
Atunci, coeficientul dominant al produsului fg este care este nenul. Deci, în acest caz, .
Din punctul 2) al propoziției precedente rezultă
Corolarul 3.3 [17] Dacă R este domeniu de integritate și f, g polinoame din , atunci
.
Dacă R este un inel comutativ și unitar, inelul polinoamelor în nedeterminata X cu coeficienți în R, avem morfismul unitar de inele
,
numit morfismul canonic de la R la .
Vom da acum o proprietate importantă numită proprietatea de universalitate a inelelor de polinoame de o nedeterminată.
Teorema 3.4 [17] Fie R un inel comutativ și unitar, inelul polinoamelor de o nedeterminată cu coeficienți în R, morfismul canonic. Atunci, oricare ar fi inelul comutativ unitar S, morfismul unitar de inele și , există un unic morfism de inele astfel încât și diagrama
să fie comutativă, adică .
Demonstrație:
Vom defini mai întâi morfismul .
Dacă , atunci
.
Arătăm că are proprietățile din enunț. Fie un alt polinom din și să presupunem că .
Completând eventual polinomul f cu termeni ai căror coeficienți sunt zero putem scrie , unde . Atunci
.
Dacă notăm cu , coeficienții produsului fg, avem și cum v este morfism de inele obținem
.
Ținând seamă de acest lucru se verifică imediat că . Deci este morfism de inele. Mai mult, .
Să verificăm acum comutativitatea diagramei. Într-adevăr, dacă și deci .
Să presupunem că este un alt morfism de inele astfel încât și . Atunci, pentru , avem
și deci . Astfel am demonstrat unicitatea lui .
Fie acum S un inel, un subinel al său și incluziunea, adică . Teorema precedentă, aplicată în acest caz, ne dă pentru fiecare un morfism de inele astfel încât
.
Spunem că este valoarea polinomului f în x și o vom nota cu . Spunem că elementul anulează polinomul din sau că x este o rădăcină sau un zero al lui f dacă , adică .
Fiind dat un polinom arbitrar f din putem să definim funcția prin , oricare ar fi . Astfel fiecărui polinom f din și fiecărui inel S care conține pe R ca subinel îi corespunde o funcție definită pe S cu valori în S.
Orice funcție de la S la S care poate fi pusă sub forma pentru un anumit f din se numește funcție polinomială pe S sau funcție pe S asociată polinomului f.
În particular, dacă se obține funcția polinomială de la R la R pe care o vom nota și cu .
Deci, dacă , atunci este funcția definită prin , numită funcția polinomială asociată polinomului f.
Dacă , atunci funcția este constantă, pentru orice . De aceea elementele inelului R, considerate ca polinoame, se vor numi polinoame constante.
Având în vedere cele precedente, pot fi funcții polinomiale care să fie constante, chiar când . Dar numai acele polinoame care sunt în R se numesc constante.
Am construit mai înainte inelul polinoamelor într-o nedeterminată cu coeficienți într-un inel R. În continuare vom defini, prin inducție matematică, inelul polinoamelor într-un număr finit de nedeterminate.
Dacă R este un inel, atunci inelul polinoamelor în nedeterminatele cu coeficienți în inelul R, notat prin , se definește inductiv astfel: este inelul polinoamelor în nedeterminata cu coeficienți în inelul R, inelul polinoamelor în nedeterminata coeficienți în inelul și, în general, este inelul polinoamelor în nedeterminata cu coeficienți în inelul .
Deci l-am construit și atunci
.
Analog, plecând de la , se definește inductiv inelul al seriilor formale în nedeterminatele .
Dacă f este un polinom din inelul , atunci el este un polinom în nedeterminata cu coeficienți în și deci
,
unde , pentru orice . Este clar că, din aproape în aproape, f se scrie ca o sumă finită de forma
,
în care elementele din R se numesc coeficienții polinomului f.
Propoziția 3.5 [17] Orice polinom f din inelul are o scriere unica sub forma
.
Demonstrație:
Am observat mai înainte că polinomul f se scrie sub forma indicată. Să arătăm că o astfel de scriere este unică, ceea ce este echivalent cu faptul că dacă , atunci toți coeficienții polinomului f sunt nuli.
Demonstrația se face prin inducție matematică după numărul n de nedeterminate.
Pentru , afirmația este clară deoarece avem de-a face cu polinoame într-o nedeterminată. Fie acum . Avem , unde pentru orice . Atunci fiecare are o scriere unică
și deci
pentru orice .
Observăm că, orice coeficient apare drept coeficient al unuia dintre polinoamele . Atunci dacă , ținând seama că f este polinom în nedeterminata cu coeficienții , rezultă .
Dar oricare este polinom în nedeterminate și deci conform presupunerii inductive rezultă că toți coeficienții acestora sunt nuli. Deoarece orice coeficient al polinomului f este coeficient al unuia dintre polinoamele , rezultă că toți coeficienții polinomului f sunt nuli, adică unicitatea scrierii lui f sub forma indicată.
Dacă f este un polinom din inelul , gradul lui f relativ la nedeterminata , , este cel mai mare exponent la care figurează în expresia lui f. Când acesta este zero înseamnă că nedeterminata nu apare în expresia lui f. Un polinom de forma , se numește monom, iar prin gradul său înțelegem suma și scriem
.
Fie acum
,
un polinom scris ca sumă de monoame, scrierea fiind unică. Aceste monoame se numesc termenii polinomului. Gradul polinomului f notat prin , se definește astfel:
Observăm că în scrierea lui f pot să apară termeni diferiți care să aibă același grad.
Dacă toți termenii unui polinom f din au același grad, atunci f se numește polinom omogen sau formă. Fiind date două polinoame omogene, atunci fg este sau polinomul nul sau un polinom omogen nenul de grad egal cu .
Polinomul de grad n, se scrie în mod unic sub forma
,
unde fiecare este sau nul sau un polinom omogen de grad i și . Polinoamele se numesc componentele omogene ale polinomului f.
Să considerăm K un corp comutativ și inelul polinoamelor în nedeterminata X cu coeficienți în K. Fie funcția
,
definită astfel:
Dacă , atunci , iar dacă este un polinom al cărui grad este , atunci
.
După definiția funcției D, avem , pentru și deci
.
Această funcție o vom numi derivare iar dacă f este un polinom, se numește derivata formală a lui f și o vom mai nota prin . Prin recurență definim pentru orice număr natural și o vom numi derivata de ordin n a lui f. Pentru , notăm
.
Ținând seamă de cele precedente, rezultă proprietățile următoare:
,
,
,
oricare ar fi și .
CAPITOLUL IV
4.1 Procedura Kronecker de factorizare a polinoamelor din
Dacă , , există și , primitiv astfel încât . În adevăr, fie astfel încât și , conținutul polinomului bf. Avem cu , primitiv și grad f grad . Rezultă că , unde . Evident, f este ireductibil peste Q dacă și numai dacă este ireductibil peste Q. De asemenea, f este reductibil peste Q dacă și numai dacă admite descompuneri netriviale peste Z.
Vom arăta în cele ce urmează că orice descompunere netrivială în a unui polinom primitiv poate fi dedusă dintr-o descompunere netrivială a unui polinom monic din .
Fie , grad , f primitiv, , . Definim polinomul ,
.
Evident, avem . Fie cu , grad, grad. Avem
unde și .
Cum sunt polinoame primitive, rezultă că
,
deci cu , ,
grad g = grad , grad h = grad .
În concluzie rezultă că este o descompunere netrivială a lui f în .
Reciproc, fie cu , grad, grad, o descompunere netrivială a lui f în . Avem,
unde , .
Din , rezultă că , de unde deducem că și cu , , grad , grad.
După cum s-a văzut din considerațiile de mai sus, polinoamele din pot fi factorizate dacă avem metode de factorizare în pentru polinoame monice cu grad . Dacă cu și grad g, , atunci grad și avem sau . În acest caz, divide în Z pe , .
Fie , și , numere distincte. Atunci oricare ar fi notăm cu unicul polinom de interpolare Lagrange din cu grad și , (vezi Capitolul 1).
Dacă și
, ,
atunci conform Observației 1.5.5 avem
.
Fie , , astfel încât , și cu , și grad . Este clar că eventualii divizori g din ai lui f se găsesc printre polinoamele astfel determinate deoarece .
Procedura Kronecker de determinare a unui divizor pentru polinomul monic , unde grad , grad și , presupune parcurgerea următorilor pași:
Se fixează numere distincte și se determină elementele mulțimii .
Pentru fiecare se calculează polinomul astfel încât , și se testează dacă în când .
Se continuă până când se găsește un polinom astfel încât divide în pe f. Dacă un asemenea divizor nu există oricare ar fi d, , se concluzionează că f este ireductibil peste Q.
4.2 Reducerea modulo m a polinoamelor din
Fie , și inelul claselor de resturi modulo m. Pentru orice se notează în cele ce urmează cu clasa de resturi modulo m a lui a. Morfismul canonic de inele , , induce un morfism surjectiv de inele
, ,
unde pentru orice se numește redusul modulo m al polinomului f. Dacă , atunci și deci grad grad f. În particular rezultă că reducerea modulo m păstrează gradul polinoamelor monice.
Fie un polinom monic de grad și un divizor monic al lui f cu grad , . Există , h polinom monic astfel încât . Reducând modulo m, rezultă că cu grad grad g și grad grad h. Prin urmare, orice divizor monic g din al lui f produce un divizor monic al lui în .
În continuare, vom determina o margine în pentru valorile absolute ale coeficienților divizorilor de grad d din ai lui f. Îl alegem pe astfel încât să fie o astfel de margine. Pentru orice divizor monic de grad d al lui putem alege coeficienții săi cu .
Observă că dacă este un divizor monic de grad d al lui f în și , atunci , și cum rezultă că , .
Prin urmare, dacă pentru orice divizor monic de grad d al lui în , alegem și îi asociem polinomul , atunci divizorii monici de grad d din ai lui f sunt printre polinoamele g astfel determinate.
Pentru determinarea modulului m necesar funcționării regulei de mai sus, vom prezenta următoarele rezultate:
Propoziția 4.2.1 [1] Fie și
.
Atunci oricare ar fi cu .
Demonstrație:
Cum , avem
și cum
, ,
rezultă că
.
Notând , inegalitatea de mai sus se poate scrie . Dacă , atunci și deci , ceea ce este o contradicție. Rămâne adevărat că avem , deci .
Q.E.D.
Propoziția 4.2.2 [1] Fie un polinom monic de grad și un divizor monic de grad d al lui f. Dacă oricare ar fi cu , atunci
, , .
În plus, dacă , atunci , , .
Demonstrație:
Dacă sunt rădăcinile din C ale lui g, atunci folosind relațiile lui Viète, avem
, .
Pentru ultima afirmație să observăm că avem pentru orice k, . Într-adevăr, această inegalitate este echivalentă cu , adică cu , iar ecuația are rădăcinile și .
Dacă , aplicând succesiv inegalitatea , avem
.
Q.E.D.
Capitolul V
ALGORITMI DE FACTORIZARE PENTRU POLINOAME CU COEFICIENȚI ÎNTR-UN CORP FINIT
Fie corpul cu q elemente și , grad. Conform Teoremei 1.5.13, polinomul f se reprezintă ca un produs finit de polinoame ireductibile peste corpul . Pentru determinarea efectivă a unei asemenea reprezentări putem să ne mărginim la cazul în care f este monic. În acest caz există polinoamele monice ireductibile și distincte și astfel încât
. (5.1)
Reprezentarea (5.1) se numește descompunere canonică a polinomului f. Polinoamele și numerele sunt unic determinate.
Dat , f monic, grad , exponentul poate fi determinat când este cunoscut factorul ireductibil , anume cu proprietatea că îl divide pe f și f și aceasta se poate stabili folosind algoritmul împărțirii cu rest a polinoamelor din . Problema care se pune este aceea de a găsi algoritmi pentru determinarea divizilor monici ireductibili ai polinomului .
Se spune că polinomul f este liber de pătrate (square-free) în cazul în care . Dacă polinomul monic are descompunerea dată de relația (5.1), atunci polinomul SF,
SF
se numește partea liberă de pătrate a polinomului f. Să observăm că f și SF au aceiași divizori ireductibili, iar SF are avantajul că are gradul mai mic când f nu este liber de pătrate.
În problema determinării descompunerii canonice a unui polinom cu coeficienți într-un corp finit, va fi examinat cazul , când p este număr prim. Algoritmii care vor fi prezentați se extind imediat la cazul unui corp finit arbitrar .
5.1 Algoritmul DS
Următorul rezultat ajută la elaborarea unui algoritm pentru calculul descompunerii standard a unui polinom monic neconstant :
Propoziția 5.1.1 [1] Fie un polinom monic neconstant și descompunerea sa standard. Notăm
și cmmdc(, D),
Dacă D, atunci și . Altfel, există astfel încât D pentru și D; în acest caz avem și quo (câtul împărțirii lui f prin ).
Demonstrație:
Cum DDh, rezultă că avem pentru orice , unde și (, D), deci grad grad . Există deci cu DD și D, .
Avem D, deci există astfel încât . Dacă și este un divizor ireductibil al lui , atunci
,
contradicție. Rezultă că , deci și quo, câtul împărțirii lui f prin .
Algoritmul DS (descompunere standard) este folosit pentru calculul descompunerii standard a unui polinom monic , grad și presupune parcurgerea următorilor pași:
Pasul 1: Se calculează succesiv , cmmdc(, D) până se găsește k astfel încât , și D.
Pasul 2: Se calculează astfel încât și apoi se calculează quo, câtul împărțirii lui f prin .
Pasul 3: Se pune DS.
Observația 5.1.2 Algoritmul DS poate fi prezentat în Pseudocod astfel:
INPUT: , f monic, grad
OUTPUT: DS
INITIALIZATION:
WHILE DF DO cmmdc(F, DF)
Calculează astfel încât
quo F
RETURN: DS
Exemplul 5.1.3 Fie . Ne propunem să găsim DS. Efectuăm următoarele calcule:
1. , D;
2. (, D), D;
3. (, D), D;
4. avem cu și quo ;
5. DF, unde și .
Observăm că polinoamele și sunt ireductibile peste și deci este descompunerea canonică a lui f, ceea ce a simplificat mult calculul cmmdc, de câte ori a fost cazul în calculele precedente.
Exemplul 5.1.4 Fie . Să se scrie descompunerea standard a polinomului folosind algoritmul DS.
1. , D;
2. (, D), D;
3. (, D), D;
4. avem cu și quo ;
5. DF, unde și .
Exemplul 5.1.5 Fie . Să se scrie descompunerea standard a polinomului folosind algoritmul DS.
1. , D;
2. (, D), D;
3. (, D), D;
4. avem cu și quo ;
5. DF, unde și .
5.2 Algoritmul SF
În acest paragraf sunt prezentate mai întâi o serie de proprietăți ale polinoamelor din inelul , număr prim. Multe dintre aceste proprietăți sunt consecințe ale faptului că este un corp finit de caracteristică p.
Observația 5.2.1 În conformitate cu notația generală a oricărui corp finit cu q elemente (vezi Observația 2.3.14), am notat cu corpul al claselor de resturi modulo un număr prim .
Propoziția 5.2.2 [1] Fie un polinom monic de grad . Există polinoamele monice unic determinate astfel încât și h oricare ar fi divizorul ireductibil al lui f.
Demonstrație:
Fie descompunerea canonică a lui f. Prin împărțirea cu rest la p, obținem
, , , .
Dacă luăm
și
atunci și nu îl divide pe h oricare ar fi .
Unicitatea lui g și h rezultă din faptul că numerele și din împărțirea cu rest la p a lui sunt unic determinate oricare ar fi .
Reprezentarea din Propoziția 5.2.2 se numește descompunerea standard a polinomului . În cele ce urmează vom folosi notația DS.
Lema 5.2.3 [1] Fie . Următoarele afirmații sunt echivalente:
i) D, adică derivata formală a lui f este polinomul zero;
ii) există astfel încât .
Demostrație:
i)ii)
Dacă , atunci D.
Cum D avem , . Când avem și atunci din rezultă . Așadar, folosind 6.1.9 (2) și 6.3.1, avem:
.
Rezultă că , unde .
ii) i)
Avem DD pentru că oricare ar fi .
Corolarul 5.2.4 [1] Dacă este un polinom ireductibil, atunci D și cmmdc(f, Df).
Demonstrație:
Dacă D, atunci cu , grad. Rezultă că f nu este ireductibil peste , ceea ce este o contradicție. Cum grad Df < grad f, rezultă că Df, deci cmmdc(f, Df) pentru că f este ireductibil.
Lema 5.2.5 [1] Fie , f monic, grad. Următoarele afirmații sunt echivalente:
i) cmmdc(f, Df);
ii) f este liber de pătrate.
Demonstrație:
i)ii)
Dacă f nu este liber de pătrate, există , ireductibil, astfel încât . Avem
DDDg,
deci divide cmmdc(f, Df), contradicție.
ii) i)
Fie d = cmmdc(f, Df). Dacă grad, există un polinom monic ireductibil astfel încât . Fie polinoame monice ireductibile și distincte astfel încât
.
Cum , există i astfel încât și deci Df.
Dar
DD.
Rezultă că D, absurd, pentru că D în baza Corolarului 5.2.4. Rămâne adevărat că .
Lema 5.2.6 [1] Fie un polinom monic, grad și descompunerea sa canonică. Avem
D, , .
cmmdc (f, Df) .
.
Demonstrație:
Cum
DD,
rezultă că Df dacă , . Reciproc, dacă Df , atunci conform Lemei 5.2.3 , există astfel încât , de unde , .
Avem
D D
unde
D
și evident oricare ar fi k astfel încât . Acum relația 2) este evidentă.
rezultă din 2).
Corolarul 5.2.7 [1] Dacă , f monic, grad și pentru orice divizor monic ireductibil al lui f, atunci:
SF.
Legat de calculul părții libere de pătrate a unui polinom monic neconstant , să observăm că dacă este descompunerea standard a lui f și dacă grad, atunci polinomul are aceeași parte liberă de pătrate ca și polinomul f, însă are avantajul de a avea gradul mai mic decât cel al lui f.
Înlocuind de fiecare dată pe f cu , după un număr finit de pași vom avea DS cu și conform Corolarului 5.1.7 va rezulta că
SFSF.
Procedura de mai sus pentru calculul lui SF(f) poartă numele de Algoritmul SF (square-free).
Observația 5.2.8 În Pseudocod, Algoritmul SF poate fi descris astfel:
INPUT: , f monic, grad
OUTPUT: SF
INITIALIZATION:
CALL Algoritmul DS și calculează DS
WHILE DO
RETURN: SF
Exemplul 5.2.9 Fie . Alegem variabila și efectuăm următorii pași:
1. .
2. Calculăm DS cu , .
3. Cum , facem atribuirea și calculăm DS cu , .
4. cu , .
5. .
6. SF.
Exemplul 5.2.10 Fie . Alegem variabila și efectuăm următorii pași:
1. .
2. Calculăm DS cu , .
3. Cum , facem atribuirea și calculăm DS cu , .
4. .
5. SF.
Exemplul 5.2.11 Fie . Alegem variabila și efectuăm următorii pași:
1. .
2. Calculăm DS cu , .
3. Cum , facem atribuirea și calculăm DS cu ,
4. cu și
5.
6. SF.
5.3 Algoritmul Berlekamp
După cum se știe, orice corp finit are cardinalul de forma . Pentru a demonstra că invers, dat fiind nu număr natural n și un număr prim p, există un corp cu elemente trebuiesc invocate o serie de rezultate de algebră: existența închiderii algebrice și existența corpurilor de descompunere. Mai exact, se arată că se poate construi un corp cu elemente ca și corpul de descompunere al polinomului . Mai mult, de fapt corpul de descompunere al acestui polinom este corpul format cu toate rădăcinile sale. Vom arăta în continuare că orice două corpuri cu același cardinal sunt de fapt izomorfe. Mai mult, dacă este fixată o închidere algebrică a lui , atunci există un unic subcorp cu .
Teorema 5.3.1 (Teorema de structură a grupurilor abeliene finit generate) Pentru orice grup abelian G finit generat există numerele naturale r și astfel încât
. (5.2)
O formă similară Teoremei 1.4.5 (Lema chineză a resturilor) este:
Teorema 5.3.2 Fie . Dacă , atunci
.
Remarca 5.3.3 Teorema 5.3.2 ne arată că descompunerea din relația (5.2) nu este neapărat unică.
Reamintim faptul că un grup abelian G se numește ciclic dacă există un element astfel încât G este subgrupul generat de g (i.e. dacă pentru orice există astfel încât ). Teorema factorilor invarianți ne spune că un grup ciclic este fie izomorf cu Z, fie izomorf cu .
Lema 5.3.4 Fie G un grup abelian finit. Dacă pentru orice , mulțimea
are cel mult n elemente, atunci G este ciclic.
Demonstrație:
Din teorema 5.3.1, se poate presupune că G este de forma . Dacă arătăm că pentru orice doi indici distincți avem , atunci din Teorema 5.3.2 va rezulta că , deci G este ciclic. Modulo o renumerotare, putem presupune că . Fie , . Atunci în grupul
există cel puțin n elemente astfel încât . Mai exact, elementele mulțimii
sunt distincte și au proprietatea cerută. Analog, grupul are cel puțin n elemente anulate de n: . Rezultă că în grupul G există cel puțin elemente anulate de n, mai exact toate elementele de forma
.
Se poate demonstra acum un rezultat foarte util în aplicații, și anume:
Teorema 5.3.5 Fie K un corp, un grup finit. Atunci G este ciclic, adică există astfel încât .
Demonstrație:
Aplicând Lema 5.3.4 grupului G, și observăm că pentru orice ,
are cel mult n elemente, deoarece polinomul are gradul n.
În cele ce urmează este prezentat un algoritm de factorizare a polinoamelor din , p număr prim, inventat de Elwyn Ralph Berlekamp în anul 1967. Acest algoritm, aplicat unui polinom monic , grad, stabilește dacă f este ireductibil peste , iar în caz contrar determină efectiv un divizor netrivial g al lui f. Algoritmul Berlekamp valorifică algoritmi cunoscuți pentru calculu cmmdc al unor polinoame din și algoritmi de calcul a soluțiilor sistemelor de ecuații liniare cu coeficienți în corpul .
Teorema 5.3.6 [1] Următoarele afirmații sunt echivalente pentru un polinom monic cu grad :
f admite cel puțin doi divizori monici ireductibili distincți;
există un polinom monic , grad astfel încât f divide pe .
Demonstrație:
Cum , oricare ar fi (Mica Teoremă a lui Fermat) rezultă că polinomul are rădăcinile , deci
,
de unde, înlocuind nedeterminata X cu orice , obținem
. (5.2)
i)ii)
Fie descompunerea canonică a lui f în , i.e., reprezentarea lui f ca produs de puteri de polinoame monice ireductibile distincte. Fie , nu toți egali. Aplicând Lema Chineză a resturilor (Teorema 1.4.5), determinăm astfel încât grad (dacă grad, înlocuim pe cu mod f) și
, .
Avem grad, căci altfel , . Cum nu sunt toți egali, există k astfel încât . Rezultă că , contradicție.
Din relația (5.2) deducem că , . Cum oricare ar fi , rezultă că polinomul divide pe .
ii)i)
Să observăm că pentru orice cu oricare ar fi , avem
oricare ar fi .
Cum și oricare ar fi în (deoarece , și , deci ) obținem
. (5.3)
Cum grad, , în relația (5.3) avem cel puțin doi factori netriviali, i.e. de grade diferite de 0 și n.
Fie și cu doi factori netriviali din (5.3). Fie un divizor monic ireductibil pentru primul din acești factori și pentru al doilea. Avem căci altfel, ar admite un divizor ireductibil, de unde rezultă i).
Vom prezenta acum o procedură de determinare a unui polinom nenul , astfel încât un polinom monic neconstant de grad n să dividă pe .
Să observăm că
.
Efectuând împărțirea cu rest a polinoamelor , , prin f, avem
, ,
unde , . Rezultă că
cu și deci polinomul f divide pe dacă și numai dacă f divide polinomul h,
.
Dacă , atunci grad. Deci f divide pe h dacă și numai dacă , ceea ce revine la
(5.4)
unde
.
Dacă , atunci , deci sistemul liniar și omogen (5.4) admite întotdeauna soluțiile
cu și admite doar aceste soluții dacă și numai dacă rang. În acest caz, dacă f este liber de pătrate, atunci f este ireductibil în baza Teoremei 5.3.1. Așacum am văzut în subcapitolul 5.1, cu algoritmul SF ne putem reduce la problema factorizării polinoamelor monice , f liber de pătrate.
Factorizarea unor asemenea polinoame f libere de pătrate se poate face cu algoritmul Berlekamp, care presupune parcurgerea următorilor pași:
Pasul 1: Se reprezintă polinoamele , , sub forma:
cu și , , , și se consideră matricea , unde .
Pasul 2: Se calculează rangQ și se conchide că f este ireductibil dacă rang.
Pasul 3: Dacă rang, se alege o soluție a sistemului omogen (5.4) având cel puțin o componentă cu indicele și se consideră polinomul
.
Pasul 4: Se calculează următoarea descompunere a lui f
.
Pasul 5: Factorilor netriviali ai lui f din descompunerea de la Pasul 4 li se aplică același tratament ca cel aplicat lui f la pașii 1) – 4) ș.a.m.d. până se obține descompunerea canonică a lui f.
Observația 5.3.7 Pentru simplificarea scrierii, în exemplele următoare vom nota clasele cu ,având grijă ca adunarea și înmulțirea acestora să se efectueze modulo p.
Exemplul 5.3.8 Să se arate că polinomul este un polinom ireductibil peste .
Cum D și , rezultă că SF. Vom efectua mai întâi împărțirile cu rest ale polinoamelor , , prin polinomul f:
Rezultă că
Cum rang rezultă că f este ireductibil peste .
Exemplul 5.3.9 Folosind algoritmul Berlekamp, să se descompună în factori ireductibili peste corpul , polinomul .
Cum
,
rezultă că f este liber de pătrate. Aplicăm algoritmul Berlekamp polinomului . Împărțim prin f polinoamele , , și obținem
,
Rezultă că
Cum rang , f admite descompuneri netriviale în . Vom determina un polinom astfel încât și grad. Coeficienții lui formează o soluție a sistemului omogen
,
peste , adică
.
Soluția generală a sistemului omogen este cu . Luând și , găsim și avem
Așadar, descompunerea canonică a lui f este
.
Exemplul 5.3.10 Folosind algoritmul Berlekamp, să se descompună în factori ireductibili peste corpul , polinomul .
Cum
,
rezultă că f este liber de pătrate. Aplicăm algoritmul Berlekamp polinomului . Împărțim prin f polinoamele , , și obținem
,
Rezultă că
Cum rang , f admite descompuneri netriviale în . Vom determina un polinom astfel încât și grad. Coeficienții lui formează o soluție a sistemului omogen
,
peste , adică .
Soluția generală a sistemului omogen este cu . Luând și , găsim și avem
Așadar, descompunerea canonică a lui f este
.
5.4 Algoritmul DD
Cu algoritmul SF, problema factorizării polinoamelor monice din s-a redus la problema factorizării polinoamelor libere de pătrate. În continuare, vom încerca să reducem problema factorizării polinoamelor monice din la cazul polinoamelor libere de pătrate cu toți divizorii ireductibili de același grad.
Pentru aceasta, fie un polinom monic liber de pătrate și
reprezentarea sa ca produs de polinoame monice ireductibile distincte. Dacă
{grad}
și , notăm cu produsul tuturor divizorilor monici ireductibili de grad k ai lui f. Dacă f nu are divizori ireductibili de grad k, definim . Evident .
Ansamblul de polinoame se numește descompunerea grade-distincte a polinomului f și avem
.
Fie descompunerea grade-distincte a polinomului monic liber de pătrate
de grad. Definim recurent polinoamele prin
și , ,
i.e. este restul împărțirii prin f a polinomului când . Se observă că
, . (5.5)
În adevăr, dacă , atunci . Presupunând că , adică
pentru ,
prin ridicarea la puterea p obținem
,
cu alte cuvinte
.
Afirmăm că pentru orice , avem
cmmdc . (5.6)
În adevăr, cum mod f rezultă că un divizor ireductibil al lui f divide pe dacă și numai dacă divide pe . Dacă , atunci grad. Pe de altă parte, dacă , atunci grad . Acum rezultă imediat că
cmmdc.
Fie un polinom monic liber de pătrate cu grad . Din analiza de mai sus rezultă că luând valorile inițiale
, , și
și repetând pasul
, mod f,
cmmdc,
până când se obține un prim indice s astfel încât , atunci descompunerea grade-distincte a lui f este .
Această procedură de calcul pentru descompunerea grade-distincte se numește Algoritmul DD (distinct degrees).
Observația 5.4.1 Algoritmul DD poate fi descris în Pseudocod astfel:
INPUT: un polinom monic , f liber de pătrate
OUTPUT: descompunerea grade-distincte a polinomului f
INITIALIZATION: , , și
1. REPEAT: , mod f,
cmmdc,
2. UNTIL
3.
4. RETURN:
Exemplul 5.4.2 Fie . Să se calculeze descompunerea grade distincte a lui f.
Avem
,
,
,
,
,
.
Rezultă că descompunerea grade-distincte a lui f este
.
Exemplul 5.4.3 Fie . Să se calculeze descompunerea grade distincte a lui f.
Avem
,
,
,
,
,
.
Prin urmare descompunerea grade-distincte a lui f este
.
Exemplul 5.4.4 Fie . Să se calculeze descompunerea grade distincte a lui f.
Avem
,
,
,
,
,
,
,
,
Așadar descompunerea grade-distincte a lui f este .
5.5 Algoritmul Cantor-Zassenhaus
Cu algoritmii SF și DD problema factorizării polinoamelor monice din a fost redusă la cazul polinoamelor monice despre care știm că reprezentarea lor canonică este un produs de polinoame monice ireductibile, distincte și de același grad.
În acest caz, ca alternativă la Algoritmul Berlekamp, prezentăm algoritmul probabilistic inventat în 1981 de către David G. Cantor și Hans Julius Zassenhaus. În acest scop vom prezenta următoarea:
Lema 5.5.1 [1] Fie corpul cu q elemente, k un divizor al lui , și . Atunci
S este un subgrup de ordin e al grupului .
.
Demonstrație:
i) Conform lui Teoremei 2.3.8, există astfel încât ord . Fie . Rezultă că
ord
și deci este subgrup de ordin e al grupului . Pentru orice , avem , deci .
Reciproc, dacă , atunci pentru un i cu , deci . Rezultă că , ceea ce arată că S este un subgrup de ordin e al grupului .
ii) Fie . Pentru orice avem
,
deci .
Reciproc, fie . Există atunci i, , astfel încât . Cum , avem , deci . Dar , deci . Așadar, pentru un și atunci , ceea ce arată că avem și .
Corolarul 5.5.2 [1] Fie p un număr prim impar, , și cu . Avem
i) P este un subgrup de ordin al grupului .
ii) .
iii) și valorile 1 și -1 ale lui sunt egal probabile.
Demonstrație:
Afirmațiile i) și ii) rezultă din Lema 5.5.1.
iii) Fie . Avem , deci . Cum este corp, rezultă că sau , deci .
Presupunem că p este un număr prim impar și fie ,
unde și sunt polinoame monice ireductibile distincte toate având același grad d. Să observăm că dacă , , unde , iar h=cmmdc(g, f), atunci h este divizor netrivial al lui f (i.e. ) dacă și numai dacă
divide .
Pentru orice i, , există o extindere a lui și astfel încât (vezi Corolarul 2.2.14). Avem Min și conform Teoremei 2.1.8, este un subcorp al lui , iar este o bază a lui ca spațiu vectorial peste . Rezultă că extinderea are gradul d și deci , .
Definim aplicațiile
, ,
și aplicația
Să observăm că dacă și numai dacă în corpul .
Dat polinomul produs de polinoame monice ireductibile și distincte de același grad d, Algoritmul Cantor-Zassenhaus determină un divizor propriu h al lui f. În acest scop se alege la întâmplare un polinom monic astfel încât
.
Dacă cmmdc, atunci polinomul cmmdc este divizor propriu al lui f.
Dacă cmmdc, atunci cmmdc, , și deci în corpul , . În acest caz, conform Corolarului 5.5.2, avem , , unde , și . De asemenea,
.
Dacă mod f și cmmdc, atunci și (adică h este divizor propriu al lui f), mai puțin cazul , ceea ce poate să apară cu probabilitatea .
Facând m alegeri arbitrare pentru cu , și aplicând de fiecare dată lui g procedura de calcul precedentă, probabilitatea de a obține un divizor propriu al lui f este . Astfel, dacă probabilitatea să avem succes este egală cu , deja suficient de mare.
Observația 5.5.3 În Pseudocod, Algoritmul Cantor-Zassenhaus se descrie astfel:
INPUT: , p prim, iar f un polinom monic produs de polinoame ireductibile monice și distincte, de același grad d
OUTPUT: un divizor monic al lui f, și
INITIALIZATION: un polinom monic ,
1. cmmdc
2. Dacă RETURN h
3. mod f cu
4.cmmdc
5. Dacă și RETURN h, altfel RETURN “failure”
Exemplul 5.5.4 Fie polinomul de la Exemplul 5.4.2. Să se descompună în factori ireductibili folosind algoritmul Cantor-Zassenhaus.
Avem , , , .
Alegem și calculăm
.
RETURN: .
Exemplul 5.5.5 Fie polinomul de la Exemplul 5.4.3. Să se descompună în factori ireductibili folosind algoritmul Cantor-Zassenhaus.
Avem , , , .
Alegem și calculăm
.
Cum , calculăm
RETURN: .
.
Exemplul 5.5.6 Fie polinomul . Să se descompună în factori ireductibili folosind algoritmul Cantor-Zassenhaus.
Avem , , , .
Alegem și calculăm
.
Cum , calculăm
RETURN: .
.
CONCLUZII
Matematica a cunoscut o dezvoltare rapidă în ultimii ani, și putem spune că au fost dezvoltate o serie de ramuri noi ale ei. Una din ele este și Algebra computațională, implicit Aritmetica modulară. Proprietățile analitice ale polinoamelor reprezintă una dintre temele care se află în atenția specialiștilor în algebră, analiză numerică, statistică, ecuații diferențiale și cu derivate parțiale, biomatematică, informatică, fizică, etc. Ele au căpătat un nou impuls odată cu apariția Algebrei Computaționale, datorită posibilității implementării algoritmilor și a utilizării calculatoarelor electronice.
Algebra computațională (calculul algebric, manipularea simbolică) este un domeniu al calculului științific care dezvoltă, analizează, implementează și utilizează algoritmi pentru rezolvarea problemelor matematice.
Importanța calculelor algebrice (simbolice) este evidentă. Uneori calculele și rezultatele numerice nu sunt relevante, cele simbolice fiind mult mai simple și mai clare. Așadar, caracteristicile de bază ale structurilor algebrice ale sistemelor de algebră computațională sunt: reprezentarea exactă a structurilor algebrice, aritmetica exactă a structurilor algebrice, aplicarea altor operații analitice asupra structurilor algebrice.
Un reputat matematician, M. Mignotte, a afirmat că problema cea mai importantă a Algebrei computaționale o reprezintă factorizarea polinoamelor. Găsirea unor algoritmi noi de factorizare este o preocupare permanentă a cercetătorilor.
În cadrul acesteia din urmă, factorizarea polinoamelor în inelul , p număr prim este prezentată cu metode moderne. Autorii acestor algoritmi, matematicianul american E. R. Berlekamp, americanul David G. Cantor, germanul H.J. Zassenhaus, au fost sau încă mai sunt contemporani cu noi. De aici și modernitatea algoritmilor prezentați de ei.
Procedurile prezentate în această lucrare, de natură algebrică, stabilesc pentru orice polinom neconstant din , dacă este ireductibil, și în caz contrar, încearcă să determine descompuneri netriviale ale sale. De asemenea, este prezentat faptul că factorizarea polinoamelor monice în , se reduce la factorizarea polinoamelor monice din , p număr prim, unde prin am notat corpul claselor de resturi modulo un număr prim , .
Consider că acest domeniu este un domeniu deschis cercetării, cu reale posibilități de îmbunătățire a algoritmilor deja existenți și de determinare a altora noi.
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Algoritmi de Factorizare Pentru Polinoame din F Q (ID: 149366)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.