Algorithmus Euclidis

In mathematica algorithmus Euclidis est modus efficax duorum numerorum integrorum divisoris communis maximi (DCM, sive factoris communis maximi) computandi. Ex mathematico Graeco Euclide nominatur, qui eum in libris VII et X Elementorum descripsit.Thomas L. Heath, The Thirteen Books of Euclid's Elements, secunda ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications

In forma simplicissima, algorithmus Euclidis pari integrorum incipit, tunc parem novum fingit ex numere minore et differentia inter numeros maiorem et minorem consistentem. Processus iteratur dum numeri sint aequi. Hic numerus igitur est paris principalis divisor communis maximus.

Unus est ex veterrimis algorithmis numericis adhuc in uso commune. Algorithmus principalis in Elementis (c. 300 a.C.n.) descriptus solos numeros naturales et longitudines geometricas (numeros reales) tractavit, sed saeculo 19 definitio amplificata est ad alia genera numerorum comprehenda, qualia sunt numeri integri Gaussiani et polynomia unius variabilis. Hoc notiones hodiernas algebrae abstractae attulit, e.g. anulos Euclidianos. Nunc algorithmus Euclidis latiore definitur ut et alias structuras mathematicas comprehendat, e.g. nodos et polynomia multiplarum variabilium.

Algorithmus multes applicationes theoreticas et practicas habet. Fere ut omnes rhythmos musicales traditionales gentium variarum generat usurpari potest. Pars est praecipua algorithmi RSA, methodi incryptionis clavi publica in commercio electronico pervagati. Ut aequationes Diaphonteas solvat adhibet, e.g., ut numeros qui multiplas congruentias satisfaciunt (vide theorema Sericum de residuis) vel inversos multiplicativos corporis finiti inveniat. Etiam usurpatur ut fractiones continuas construat, in methoda catenarum Sturm ut radices reales polynomii inveniat, et in pluribus algorithmis recentibus factorizationis numerorum integrorum. Denique instrumentum est elementarium ad theoremata demonstranda in theoria numerorum hodierna, talia quales sunt theorema quatuor quadratorum Lagrange et theorema fundamentale arithmeticae.

Si residuis divisionis Euclidianae et non subtractionibus conficitur, algorithmus Euclidis DCM magnorum numerorum efficaciter computat: nunquam plures gradus divisionis quam quinquies numerum cifrarum (in systema decimale) numeri minoris poscit. Hoc a Gabriele Lamé anno 1844 demonstratum est, initium theoriae complexitatis computationalis signans. Methodi ad efficacitatem algorithmi meliorem faciendam saeculo vicensimo creati sunt.

Divisor communis maximus duorum numerorum est maximus numerus qui ambos ita dividit ut residuum non relinquat. Algorithmus Euclidis in elemento nititur, quod DCM duorum numerorum non mutatur si numerus maior ex minore subtrahitur. Nam si k, m, n sunt integri, et k est factor communis duorum integrorum A et B, ergo A = nk et B = mk significat A − B = (n − m)k, ergo k est etiam factor communis differentiae. Quod k etiam divisorem communem maximum potest representare infra demonstratur. Exempli gratia, 21 est DCM 252 et 105 (252 = 12 × 21; 105 = 5 × 21); quia 252 − 105 = (12 − 5) × 21 = 147, DCM 147 et 105 est etiam 21.

Quandoquidem maior duorum numerorum minuitur, iteratio hunc processi numeros dat ordine minores dum unus zerum sit. Cum hoc fit, DCM est numerus residuus qui non est zerum.

int euclidis_dcm(int m, int n)
{
	if(n == 0)
		return m;
	else
		return euclidis_dcm(n, m % n);
}

 Notae 

 Bibliographia 




 . See also Vorlesungen über Zahlentheorie













 Nexus externi 

 Demonstrationes algorithmi
 Weisstein, Eric W., "Euclidean Algorithm", apud MathWorld
 Euclid's Algorithm at cut-the-knot
 Euclid's Algorithm apud PlanetMath
 The Euclidean Algorithm apud MathPages
 Euclid's Game apud cut-the-knot
 Music and Euclid's algorithm

Categoria:Algorithmi
Categoria:Euclides
Categoria:Theoria numerorum