18,707 matches
-
Saunderson, care i l-a atribuit lui Roger Cotes ca metodă de calcul eficient a fracțiilor continue. În secolul al XIX-lea, algoritmul lui Euclid a dus la dezvoltarea unor noi sisteme de numere, cum ar fi întregii gaussieni și întregii eisensteinieni. În 1815, Carl Gauss a utilizat algoritmul lui Euclid pentru a demonstra factorizarea unică a întregilor gaussieni, deși lucrarea sa a fost publicată pentru prima oară în 1832. Gauss a menționat algoritmul în "Disquisitiones Arithmeticae" (publicat la 1801), dar
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
În secolul al XIX-lea, algoritmul lui Euclid a dus la dezvoltarea unor noi sisteme de numere, cum ar fi întregii gaussieni și întregii eisensteinieni. În 1815, Carl Gauss a utilizat algoritmul lui Euclid pentru a demonstra factorizarea unică a întregilor gaussieni, deși lucrarea sa a fost publicată pentru prima oară în 1832. Gauss a menționat algoritmul în "Disquisitiones Arithmeticae" (publicat la 1801), dar numai ca metodă pentru fracțiile continue. Peter Dirichlet pare a fi fost primul care a descris algoritmul
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
sunt adevărate pentru toate celelalte sisteme de numere în care se poate aplica algoritmul lui Euclid. Cursurile lui Dirichlet pe tema teoriei numerelor au fost editate și extinse de Richard Dedekind, care a utilizat algoritmul lui Euclid pentru a studia întregii algebrici, un tip general de numere. De exemplu, Dedekind a fost primul care a demonstrat teorema celor două pătrate a lui Fermat folosind factorizarea unică a întregilor gaussieni. Dedekind a definit și conceptul de domeniu euclidian, un sistem numeric în
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
extinse de Richard Dedekind, care a utilizat algoritmul lui Euclid pentru a studia întregii algebrici, un tip general de numere. De exemplu, Dedekind a fost primul care a demonstrat teorema celor două pătrate a lui Fermat folosind factorizarea unică a întregilor gaussieni. Dedekind a definit și conceptul de domeniu euclidian, un sistem numeric în care se poate defini o versiune generalizată a algoritmului lui Euclid. În ultimele decenii ale secolului al XIX-lea, însă, algoritmul lui Euclid a fost treptat eclipsat
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
divizor comun "g" al două numere întregi "a" și "b" se poate reprezenta sub formă de combinație liniară a primelor două numere "a" și "b". Cu alte cuvinte, întotdeauna există două numere întregi "s" și "t" astfel încât "g" = "sa" + "tb". Întregii "s" și "t" pot fi calculați pe baza câturilor "q", "q" etc. inversând ordinea ecuațiilor din algoritmul lui Euclid. Începând cu penultima ecuație, "g" poate fi exprimat în termeni de câtul "q" și de cele două resturi anterioare, "r" and
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
comun mai mic nu poate fi membru al mulțimii, deoarece toate elementele mulțimii trebuie să fie divizibile cu "g". Invers, orice multiplu "m" al lui " g" poate fi obținut alegând "u" = "ms" și "v" = "mt", unde "s" și "t" sunt întregii din identitatea lui Bézout. Aceasta se poate vedea înmulțind identitatea lui Bézout cu "m" Astfel, mulțimea tuturor numerelor "ua" + "vb" este echivalentă cu mulțimea multiplilor "m" ai lui "g". Cu alte cuvinte, mulțimea tuturor sumelor posibile de multipli întregi ai
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
de volum "a" respectiv "b". Adăugând sau scăzând "u" multipli ai primei cești și "v" multipli ai celei de-a doua cești, poate fi măsurat orice volum "ua" + "vb". Aceste volume sunt toate multipli ai lui "g" = CMMDC("a", "b"). Întregii "s" și "t" din identitatea lui Bézout se pot calcula eficient utilizând algoritmul lui Euclid extins. Această extensie adaugă algoritmului lui Euclid două ecuații recursive cu valorile de început Cu ajutorul acestei relații de recurență, întregii lui Bézout "s" și "t
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
lui "g" = CMMDC("a", "b"). Întregii "s" și "t" din identitatea lui Bézout se pot calcula eficient utilizând algoritmul lui Euclid extins. Această extensie adaugă algoritmului lui Euclid două ecuații recursive cu valorile de început Cu ajutorul acestei relații de recurență, întregii lui Bézout "s" și "t" sunt dați de "s" = "s" și "t" = "t", unde "N" este pasul la care algoritmul se termină cu "r" = 0. Validitatea acestei abordări se poate demonstra prin inducție. Se presupune că formula recursivă este corectă
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
1), deoarece este egal cu produsul determinanților matricelor-cât, care sunt egale cu minus unu. Întrucât determinantul lui M nu este niciodată zero, vectorul final de resturi se poate rezolva găsind inversa lui M Deoarece ecuația de sus dă cei doi întregi ai identității lui Bézout sunt "s" = (−1)"m" și "t" = (−1)"m". Metoda matricei este la fel de eficientă ca și cea a formulei de recurență, cu două înmulțiri și două adunări la fiecare pas al algoritmului lui Euclid. Identitatea lui Bézout
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
număr "w" îl divide și el pe "L" dar este prim cu "u", atunci înseamnă că "w" îl divide pe "v", pentru că, dacă cel mai mare divizor comun al lui "u" și "w" este 1, atunci se pot găsi doi întregi "s" și "t" astfel încât conform identității lui Bézout. Înmulțind ambele părți ale ecuației cu "v" rezultă relația Cum "w" divide ambii termeni din partea dreaptă, înseamnă că el divide și termenul din stânga, "v". Acest rezultat este cunoscut sub numele de lema
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
sau ecuația diofantică liniară echivalentă Această ecuație se poate rezolva cu ajutorul algoritmului lui Euclid, după cum s-a arătat mai sus. Găsirea inversului multiplicativ este un pas esențial în algoritmul RSA, folosit pe scară largă în comerțul electronic; anume, ecuația determină întregul utilizat pentru a decripta mesajul. Deși algoritmul RSA utilizează inele și nu corpuri, se poate folosi algoritmul lui Euclid pentru găsirea inversului multiplicativ acolo unde el există. Algoritmul lui Euclid are și alte aplicații în codurile corectoare de erori; de
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
și Reed-Solomon, coduri bazate pe corpuri Galois. Algoritmul lui Euclid se poate folosi pentru a rezolva și mai multe ecuații liniare diofantice. Astfel de ecuații apar în teorema chinezească a resturilor, care descrie o metodă nouă de reprezentare a unui întreg "x". În loc de a reprezenta un număr întreg prin cifrele sale, el se poate reprezenta prin resturile "x" ale împărțirii lui modulo o mulțime de "N" numere prime între ele "m". Scopul este determinarea lui "x" din cele "N" resturi "x
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
462), iar câturile "q" erau 2, 3 și respectiv 7. Deci fracția 1071/462 poate fi scrisă sub forma după cum confirmă și calculele. Calculul celui mai mare divizor comun este un pas esențial în mai mulți algoritmi de factorizare a întregilor, such as Pollard's rho algorithm, algoritmul lui Shor, metoda de factorizare a lui Dixon și factorizarea Lenstra cu curbe eliptice. Algoritmul lui Euclid poate fi utilizat eficient pentru găsirea CMMDC în aceste cazuri. Factorizarea cu fracții continue utilizează fracțiile
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
pași al algoritmului lui Euclid a fost definit în trei moduri diferite. Prima definiție este timpul mediu "T"("a") necesar pentru a calcula CMMDC al unui număr "a" și al unui număr mai mic "b" ales cu probabilitate egală dintre întregii dintre 0 și "a" − 1 ea poate fi aproximată prin formula unde Λ ("d") este funcția Mangoldt. O a treia medie "Y"("n") este definită ca numărul mediu de pași necesar atunci când "a" și "b" sunt ambele alese aleator (cu
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
sus, algoritmul lui Euclid este folosit pentru a găsi cel mai mare divizor comun a două numere naturale (numere întregi pozitive). Acesta poate fi, însă, generalizat la numere reale, și la sisteme de numere mai exotice, cum ar fi polinoamele, întregii cuadratici și cuaternionii Hurwitz. În ultimele două cazuri, algoritmul lui Euclid este folosit pentru a demonstra proprietatea crucială de unicitate a factorizării, anume aceea că astfel de numere pot fi factorizate în mod unic în elemente ireductibile, structuri similare numerelor
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
numere reale, "a" și "b", sunt multipli întregi ai acestuia: "a" = "mg" și "b" = "ng", unde "m" și "n" sunt întregi. Această identificare este echivalentă cu găsirea unei relații întregi între două numere reale "a" și "b"; adică, ea determină întregii "s" și "t" astfel întât "sa" + "tb" = 0. Euclid folosește acest algoritm pentru a trata chestiunea lungimilor incomensurabile. Algoritmul lui Euclid pe numere reale diferă de cel pe întregi prin două aspecte. Primul este că resturile "r" sunt numere reale
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
întregi între două numere reale "a" și "b"; adică, ea determină întregii "s" și "t" astfel întât "sa" + "tb" = 0. Euclid folosește acest algoritm pentru a trata chestiunea lungimilor incomensurabile. Algoritmul lui Euclid pe numere reale diferă de cel pe întregi prin două aspecte. Primul este că resturile "r" sunt numere reale, deși câturile "q" sunt, ca și mai înainte, întregi. Al doilea este că algoritmul nu este garantat că se termină într-un număr finit "N" de pași. Dacă se
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
numerelor întregi. Cel mai mare divizor comun "g"("x") al două polinoame "a"("x") și "b"("x") este definit ca produsul polinoamelor ireductibile comune, care pot fi identificate folosind algoritmul lui Euclid. Procedura de bază este similară cu cea de la întregi. La fie care pas "k", se calculează un polinom cât "q"("x") și un polinom rest "r"("x") care satisfac ecuația recursivă unde "r"("x") = "a"("x") și "r"("x") = "b"("x"). Polinomul cât este ales astfel încât termenul dominant al
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
întregi, reale, și nici măcar complexe. De exemplu, coeficienții pot fi din orice corp, cum ar fi corpurile finite GF("p") descrise mai sus. Concluziile corespunzătoare despre algoritmul lui Euclid și despre aplicațiile acestuia sunt valabile chiar și pentru asemenea polinoame. Întregii gaussieni sunt numere complexe de forma α = "u" + "vi", unde "u" și "v" sunt numere întregi obișnuite și "i" este unitatea imaginară. Definind un algoritm analog celui al lui Euclid, se poate arăta că întregii gaussieni au fiecare o factorizare
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
chiar și pentru asemenea polinoame. Întregii gaussieni sunt numere complexe de forma α = "u" + "vi", unde "u" și "v" sunt numere întregi obișnuite și "i" este unitatea imaginară. Definind un algoritm analog celui al lui Euclid, se poate arăta că întregii gaussieni au fiecare o factorizare unică, conform demonstrației de mai sus. Unicitatea factorizării este utilă în mai multe aplicații, cum ar fi calculul tuturor tripletelor pitagoreice sau demonstrația Primei teoreme a lui Fermat a sumei a două pătrate. În general
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
u" + "v"i) = "u" + "v", care transformă fiecare întreg gaussian "u" + "vi" la un număr întreg. După fiecare pas "k" al algoritmului lui Euclid, norma restului "f"("r") este mai mică decât norma restului precedent, "f"("r"). Norma fiind un întreg nenegativ și scăzând la fiecare pas, algoritmul lui Euclid pentru întregi gaussieni se termină într-un număr finit de pași. Ultimul rest nenul este CMMDC(α,β), întregul gaussian cu norma cea mai mare și care se împarte exact la
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
vi" la un număr întreg. După fiecare pas "k" al algoritmului lui Euclid, norma restului "f"("r") este mai mică decât norma restului precedent, "f"("r"). Norma fiind un întreg nenegativ și scăzând la fiecare pas, algoritmul lui Euclid pentru întregi gaussieni se termină într-un număr finit de pași. Ultimul rest nenul este CMMDC(α,β), întregul gaussian cu norma cea mai mare și care se împarte exact la α și la β; el rămâne aceleași și după înmulțirea numărului
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
cu norma cea mai mare și care se împarte exact la α și la β; el rămâne aceleași și după înmulțirea numărului cu o unitate, ±1 sau ±"i". Multe dintre celelalte aplicații ale algoritmului lui Euclid sunt valabile și pentru întregii gaussieni. De exemplu, el se poate folosi pentru a rezolva ecuații liniare diofantice și probleme chinezești ale resturilor pentru aceste numere; se pot defini și fracții continue de întregi gaussieni. O mulțime de elemente împreună cu doi operatori binari, + și ·, se
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
dintre celelalte aplicații ale algoritmului lui Euclid sunt valabile și pentru întregii gaussieni. De exemplu, el se poate folosi pentru a rezolva ecuații liniare diofantice și probleme chinezești ale resturilor pentru aceste numere; se pot defini și fracții continue de întregi gaussieni. O mulțime de elemente împreună cu doi operatori binari, + și ·, se numește inel euclidian dacă formează un inel comutativ "R" și dacă pe această mulțime se poate executa un algoritm al lui Euclid modificat. Cele două operații ale unui astfel
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
principal, domeniu integral în care fiecare ideal este un ideal principal. Din nou, reciproca nu este adevărată: nu orice astfel de domeniu este inel euclidian. Unicitatea factorizării în inelele euclidiene este utilă în mai multe aplicații. De exemplu, unicitatea factorizării întregilor gaussieni este convenabilă la calculul formulelor pentru toate tripletele pitagoreice și la demonstrarea teoremei lui Fermat privind suma a două pătrate. Unicitatea factorizării este și element cheie într-o tentativă de demonstrare a Ultimei teoreme a lui Fermat publicată în
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]