Algoritme de Euclides

Archiu:Euclidean algorithm 252 105 animation flipped.gif

En matemàtiques, el algoritme de Euclides, o algoritme euclidiano, és un método eficient per a calcular el màxim comú divisor (MCD) de dos número entero, el número més gran que els dividix a abdós sense deixar restant. Du el nom de l'antic matemàtic grec Euclides, qui ho va descriure per primera volta en Elements (ca. 300 a. C.). És un eixemple d'un algoritme, un procediment passe a pas per a realisar un càlcul d'acort en regles ben definides, i és un dels algoritmes més antics que se seguixen utilisant. Es pot usar per a reduir fracciones a la seua forma més simple i és part de molts atres càlculs teòric-numèrics i criptográficos.

L'algoritme euclidiano es basa en el principi de que el màxim comú divisor de dos números no canvia si el número més gran es reemplaça per la seua diferència en el número més menut. Per eixemple, 21 és el MCD de 252 i 105 (ya que 252 = 21 × 12 i 105 = 21 × 5), i el mateix número 21 també és el MCD de 105 i 252 − 105 = 147. Ya que esta tongada reduïx el més gran dels dos números, en repetir este procés s'obtenen parells de números successivament més menuts fins que els dos números es tornen iguals. Quan això ocorre, són el MCD dels dos números originals. Al invertir els passos o usar l'algoritme de Euclides estés, el MCD es pot expressar com una combinació llineal dels dos números originals, és dir, la suma dels dos números, cada u multiplicat per un número entero (per eixemple, 21 = 5 × 105 + (−2) × 252). El fet de que el MCD sempre es puga expressar d'esta manera es coneix com l'identitat de Bézout.

La versió de l'algoritme euclidiano descrita anteriorment (i per Euclides) pot requerir molts passos de resta per a trobar el MCD quan un dels números donats és molt més gran que l'atre. Una versió més eficient de l'algoritme acurta estos passos, en el seu lloc es reemplaça el més gran dels números pel seu restant en dividir-ho pel més chicotet dels dos (en esta versió, l'algoritme es deté en alcançar un restant zero). En esta millora, l'algoritme mai requerix més passos que cinc voltes el número de dígits (base 10) de l'número entero més menut. Açò va ser demostrat per Gabriel Lamé en 1844 (teorema de Lamé),^[1]^[2] i marca el començ de la teoria de la complexitat informàtica. Es varen desenrollar métodos adicionals per a millorar l'eficiència de l'algoritme en el XX.

L'algoritme euclidiano té moltes aplicacions teòriques i pràctiques. S'utilisa per a reduir fracciones a la seua forma més simple i per a realisar divisions en aritmètica modular. Els càlculs que utilisen este algoritme formen part dels protocols criptográficos que s'usen per a protegir les comunicacions d'Internet, i en els métodos per a trencar estos sistemes criptográficos per mig de la factorización de grans número compuesto. L'algoritme euclidiano es pot usar per a resoldre equacions diofánticas, com trobar números que satisfacen múltiples congruència d'acort en el teorema chinenca del restant, per a construir fraccions contínues i per a trobar aproximacions racionals precises a número real. Finalment, es pot utilisar com una ferramenta bàsica per a demostrar teoremes en la teoria de números, com el teorema dels quatre quadrats de Lagrange i l'unicitat de les factorización primeres.

Algoritme original de Euclides

Archiu:Segmentos conmensurables.svg

AB i CD els segments conmensurables.

Archiu:Algoritmo de Euclides geométrico.svg

Eixemple de l'algoritme original de Euclides.

En la concepció grega de la matemàtica, els números s'entenien com a magnituts geomètriques. Un tema recurrent en la geometria grega és el de la conmensurabilidad de dos segments: dos segments (números) AB i CD són conmensurables quan existix un tercer segment PQ que cap exactament un número entero de voltes en els primers dos; és dir, PQ «medix» (mensura: mida) als segments AB i CD.

No qualsevol parell de segments és conmensurable, com varen trobar els pitagórico quan establixen que el costat i la diagonal d'un quadrat no són conmensurables, pero en el cas de dos segments conmensurables es desija trobar la major mida comuna possible.

Euclides descriu en la proposició I.2 en el seu Llibre VII dels seus Elements un método que permet trobar la major mida comuna possible de dos números (segments) que no siguen primers entre sí, encara que d'acort a l'época tal método s'explica en térmens geomètrics, lo que s'ilustra en la següent transcripció.

En llenguage modern, l'algoritme es descriu com seguix:

Donats dos segments AB i CD (en AB>CD), restem CD de AB tantes voltes com siga possible. Si no hi ha residu, llavors CD és la màxima mida comuna.
Si s'obté un residu EA, est és menor que CD i podem repetir el procés: restem EA tantes voltes com siga possible de CD. Si al final no queda un residu, EA és la mida comuna. En cas contrari obtenim un nou residu FC menor a EA.
El procés es repetix fins que en algun moment no s'obté residu. Llavors l'últim residu obtingut és la major mida comuna.

El fet de que els segments són conmesurables és clau per a assegurar que el procés termina tart o primerenc.

Algoritme de Euclides tradicional

Al dividir $a$ entre $b$ (número entero), s'obté un cocient $q$ i un restant $r$ . És possible demostrar que el màxim comú divisor de $a$ i $b$ és el mateix que el de $b$ i $r$ . Siga c el màxim comú divisor de $a$ i $b$ , com $a = b q + r$ i $c$ dividix a $a$ i a $b$ , dividix també a $r$ . Si existira un atre número major que $c$ que dividix a $b$ i a $r$ , també dividiria a $a$ , per lo que $c$ no seria el mcd de $a$ i $b$ , lo que contradiu l'hipòtesis). Est és el fonament principal de l'algoritme. També és important tindre en conte que el màxim comú divisor de qualsevol número $a$ i $0$ és precisament $a$ . Per a fins pràctics, la notació $m c d (a, b)$ significa màxim comú divisor de $a$ i $b$ .

Segons lo abans mencionat, per a calcular el màxim comú divisor de 2366 i 273 es pot proseguir de la següent manera:

Pas	Operació	Significat
1	2366 dividit entre 273 és 8 i sobren 182	$m c d (2366, 273) = m c d (273, 182)$
2	273 dividit entre 182 és 1 i sobren 91	$m c d (273, 182) = m c d (182, 91)$
3	182 dividit entre 91 és 2 i sobra 0	$m c d (182, 91) = m c d (91, 0)$

La seqüència d'igualtats $m c d (2366, 273) = m c d (273, 182) = m c d (182, 91) = m c d (91, 0)$ impliquen que $m c d (2366, 273) = m c d (91, 0)$ . Ya que $m c d (91, 0) = 91$ , llavors es conclou que $m c d (2366, 273) = 91$ . Este mateix procediment es pot aplicar a qualssevol dos número natural. En general, si es desija trobar el màxim comú divisor de dos número natural $a$ i $b$ , se seguixen les següents regles:

Si $b = 0$ llavors $m c d (a, b) = a$ i l'algoritme termina
En un atre cas, $m c d (a, b) = m c d (b, r)$ a on $r$ és el restant de dividir $a$ entre $b$ . Per a calcular $m c d (b, r)$ s'utilisen estes mateixes regles

Assumixca que cridem $a = r_{0}$ i $b = r_{1}$ . Aplicant estes regles s'obté la següent seqüència d'operacions:

Pas	Operació	Significat
1	$r_{0}$ dividit entre $r_{1}$ és $q_{1}$ i sobren $r_{2}$	$m c d (r_{0}, r_{1}) = m c d (r_{1}, r_{2})$
2	$r_{1}$ dividit entre $r_{2}$ és $q_{2}$ i sobren $r_{3}$	$m c d (r_{1}, r_{2}) = m c d (r_{2}, r_{3})$
3	$r_{2}$ dividit entre $r_{3}$ és $q_{3}$ i sobren $r_{4}$	$m c d (r_{2}, r_{3}) = m c d (r_{3}, r_{4})$
$⋮$	$⋮$	$⋮$
$n$	$r_{n - 1}$ dividit entre $r_{n}$ és $q_{n}$ i sobren $r_{n + 1}$	$m c d (r_{n - 1}, r_{n}) = m c d (r_{n}, r_{n + 1})$
$n + 1$	$r_{n}$ dividit entre $r_{n + 1}$ és $q_{n + 1}$ i sobra $0$	$m c d (r_{n}, r_{n + 1}) = m c d (r_{n + 1}, 0)$

Com la successió de residus va disminuint, al final un residu té que ser zero i és en eixe moment quan l'algoritme termina. El màxim comú divisor és precisament $r_{n + 1}$ (l'últim residu que no és zero).

Generalisació

En realitat, l'algoritme de Euclides funciona no només per als número natural, sino per a qualsevol element en el que existixca una "divisió en residu". A este tipo de divisions se'ls crida divisions euclidianas i als conjunts a on es pot definir dita divisió se'ls crida dominis euclídeos. Per eixemple, el conjunt dels número entero i el dels polinomis en coeficients racionals són dominis euclídeos perque podem definir una divisió en residu (vore Divisió polinomial). D'esta manera, es pot calcular el màxim comú divisor de dos número entero o de dos polinomis.

Per eixemple, per a calcular el màxim comú divisor dels polinomis $P (x) = x^{5} + 2 x^{3} + x$ i $Q (x) = x^{4} - 1$ l'algoritme de Euclides sugerix la següent seqüència d'operacions:

Pas	Operació	Significat
1	$x^{5} + 2 x^{3} + x$ dividit entre $x^{4} - 1$ és $x$ i sobra $2 x^{3} + 2 x$	$m c d (x^{5} + 2 x^{3} + x, x^{4} - 1) = m c d (x^{4} - 1, 2 x^{3} + 2 x)$
2	$x^{4} - 1$ dividit entre $2 x^{3} + 2 x$ és $\frac{1}{2} x$ i sobra $- x^{2} - 1$	$m c d (x^{4} - 1, 2 x^{3} + 2 x) = m c d (2 x^{3} + 2 x, - x^{2} - 1)$
3	$2 x^{3} + 2 x$ dividit entre $- x^{2} - 1$ és $- 2 x$ i sobra 0	$m c d (2 x^{3} + 2 x, - x^{2} - 1) = m c d (- x^{2} - 1, 0)$

D'esta manera es conclou que el seu màxim comú divisor és $- x^{2} - 1$ .

Descripció formal

Es pot expressar este algoritme de manera més formal usant pseudocódigo. En este cas l'expressió " $x mod y$ " significa "el residu de dividir $x$ entre $y$ " (vore Aritmètica modular).

Val la pena notar que este algoritme no és eficient ser implementat directament en una computadora, ya que requeriria memorisar tots els valors de $r_{i}$ .

Algoritme de Euclides estés

L'algoritme de Euclides estés permet, ademés de trobar un màxim comú divisor de dos número entero $a$ i $b$ , expressar-ho com la mínima combinació llineal d'eixos números, és dir, trobar número entero $s$ i $t$ tals que $m c d (a, b) = a s + b t$ . Açò es generalisa també cap a qualsevol domini euclidiano.

Fonaments

Existixen vàries maneres d'explicar l'algoritme de Euclides estés, una de les més comunes consistix en la següent:

Usar l'algoritme tradicional de Euclides. En cada pas, en lloc de " $a$ dividit entre $b$ és $q$ i de restant $r$ " s'escriu l'equació $a = b q + r$ (vore algoritme de la divisió).
Es rebuja el restant de cada equació.
Se substituïx el restant de l'última equació en la penúltima, i la penúltima en la antepenúltima i aixina successivament fins a aplegar a la primera equació, i en tot pas s'expressa cada restant com a combinació llineal.

No obstant, en benefici de la comprensió i memorisació d'este algoritme, és convenient conéixer la següent caracterisació. Per a multiplicar dos matrius de tamany $2 \times 2$ s'usa la següent fòrmula (vore Producte de matrius):

(1) $[\begin{matrix} e & f \\ g & h \end{matrix}] \times [\begin{matrix} a & b \\ c & d \end{matrix}] = [\begin{matrix} e a + f c & e b + f d \\ g a + h c & g b + h d \end{matrix}]$

Suponga's que s'utilisa l'algoritme de Euclides tradicional per a calcular els valors $q_{i}$ i $r_{i}$ que ahí es descriuen. Per cada valor $q_{i}$ calculat es pot formar la matriu $Q_{i} = [\begin{matrix} 0 & 1 \\ 1 & - q_{i} \end{matrix}]$ . Usant l'equació (1) de manera repetida es pot calcular el producte de les primeres $i$ matrius d'este tipo:

$[\begin{matrix} s_{i} & t_{i} \\ s_{i + 1} & t_{i + 1} \end{matrix}] = [\begin{matrix} 0 & 1 \\ 1 & - q_{i} \end{matrix}] \times [\begin{matrix} 0 & 1 \\ 1 & - q_{i - 1} \end{matrix}] \times \dots \times [\begin{matrix} 0 & 1 \\ 1 & - q_{1} \end{matrix}]$

Resulta ser que els valors $s_{i}$ i $t_{i}$ tenen la propietat de que $r_{i} = a s_{i} + b t_{i}$ , és dir, expressen a $r_{i}$ com una combinació llineal de $a$ i $b$ . Particularment, com $m c d (a, b) = r_{n + 1}$ llavors es té $m c d (a, b) = a s_{n + 1} + b t_{n + 1}$ , la qual cosa és la solució del problema. Esta propietat no deuria ser sorprenent, puix esta multiplicació de matrius equival al método abans descrit a on es substituye cada equació en l'anterior. És important calcular $Q_{i} \times \dots \times Q_{3} \times Q_{2} \times Q_{1}$ en eixe mateix orde. La matriu $Q_{1}$ apareix en l'extrem dret i la matriu $Q_{i}$ en l'esquerre.

Retornant al primer eixemple, la successió de cocients és $q_{1} = 8$ , $q_{2} = 1$ i $q_{3} = 2$ . Llavors es pot calcular

$[\begin{matrix} - 1 & 9 \\ 3 & - 26 \end{matrix}] = [\begin{matrix} 0 & 1 \\ 1 & - 2 \end{matrix}] \times [\begin{matrix} 0 & 1 \\ 1 & - 1 \end{matrix}] \times [\begin{matrix} 0 & 1 \\ 1 & - 8 \end{matrix}]$

Utilisant el primer rengló d'esta matriu es pot llegir que $91 = 2366 (- 1) + 273 (9)$ , és dir, s'ha trobat la manera d'expressar al màxim comú divisor de 2366 i 273 com una combinació llineal.

Descripció formal

Per a expressar l'algoritme de Euclides estés és convenient notar la manera en que es calculen els valors $s_{i}$ i $t_{i}$ en la multiplicació de matrius:

D'esta manera $s_{i + 1} = s_{i - 1} - q_{i} s_{i}$ i ademés $t_{i + 1} = t_{i - 1} - q_{i} t_{i}$ . Per lo tant l'algoritme en pseudocódigo es pot expressar com seguix:

Aplicacions

Simplificar fraccions

Al moment de fer càlculs en fraccions, és de gran importància saber cóm simplificar-les. Per eixemple, la fracció $\frac{65}{91}$ és equivalent en $\frac{5}{7}$ (vore Número racional). De manera més general, $\frac{a}{b} = \frac{c a}{c b}$ sempre que $c \neq 0$ . Per a reduir una fracció qualsevol $\frac{a}{b}$ , només es necessita dividir $a$ i $b$ entre el seu màxim comú divisor.

Per eixemple, si es desija reduir $\frac{166}{249}$ , primer s'usa l'algoritme de Euclides per a trobar $m c d (166, 249) = 83$ . Es fan les divisions $166 \div 83 = 2$ i $249 \div 83 = 3$ . Després llavors es conclou que $\frac{166}{249} = \frac{2}{3}$ .

Fraccions contínues

La successió de divisions que s'efectuen en seguir l'algoritme de Euclides pot ser utilisada per a expressar una fracció qualsevol $\frac{a}{b}$ com fracció contínua. Açò es deu a que si $a = b q + r$ i $r \neq 0$ , llavors

(3) $\frac{a}{b} = q + \frac{1}{\frac{b}{r}}$

Per eixemple, per a trobar el màxim comú divisor de $93164$ i $5826$ l'algoritme genera la següent seqüència de divisions:

Pas	Operació	Significat
1	93164 dividit entre 5826 és 15 i sobren 5774	$93164 = 5826 \times 15 + 5774$
2	5826 dividit entre 5774 és 1 i sobren 52	$5826 = 5774 \times 1 + 52$
3	5774 dividit entre 52 és 111 i sobren 2	$5774 = 52 \times 111 + 2$
4	52 dividit entre 2 és 26 i sobra 0	$52 = 2 \times 26 + 0$

Totes estes equacions les podem fer paregudes a l'equació ( 3):

$\frac{93164}{5826} = 15 + \frac{1}{\frac{5826}{5774}}$
$\frac{5826}{5774} = 1 + \frac{1}{\frac{5774}{52}}$
$\frac{5774}{52} = 111 + \frac{1}{\frac{52}{2}}$
$\frac{52}{2} = 26$

Si se substituïx la segona equació en la primera, s'obté

$\frac{93164}{5826} = 15 + \frac{1}{1 + \frac{1}{\frac{5774}{52}}}$

Si es repetix este procés de substitució llavors s'obté l'expressió desijada:

$\frac{93164}{5826} = 15 + \frac{1}{1 + \frac{1}{111 + \frac{1}{26}}}$

De manera més general, la fracció contínua trobada en este algoritme sempre és de la forma

$\frac{a}{b} = q_{1} + \frac{1}{q_{2} + \frac{1}{q_{3} + \frac{1}{⋱ q_{n - 1} + \frac{1}{q_{n}}}}}$

Inversos mòdul m

Artícul principal → invers multiplicativo (aritmètica modular).

Es diu que dos número entero són congruents mòdul $m$ (encara que també es pot generalisar per a qualsevol atre domini euclídeo) si en dividir-los entre $m$ obtenim el mateix residu (vore Congruència). Per eixemple, 7 és congruent en 12 mòdul 5 perque en dividir 7 entre 5 i 12 entre 5, en abdós casos obtenim el mateix residu (que és 2). Quan $a$ és congruent en $b$ mòdul $m$ s'escriu $a \equiv b (\mod m)$ , en l'eixemple anterior es té $7 \equiv 12 (\mod 5)$ . Suponga's que es coneixen els valors de $a$ , $b$ i $m$ , pero que es desconeix el valor $x$ en la següent congruència: Plantilla:Ecuacion Basta trobar un valor $a^{- 1}$ que satisfaça: $a^{- 1} a \equiv 1 (\mod m)$ , puix d'esta manera en multiplicar l'equació (2) per $a^{- 1}$ es tindrà la solució desijada: Plantilla:Ecuacion A l'element $a^{- 1}$ se li crida "invers mòdul $m$ " de $a$ . Desafortunadament este valor no sempre existix. Per eixemple, en $a = 4$ i $m = 6$ no existix cap número entero $a^{- 1}$ tal que $a^{- 1} 4 \equiv 1 (\mod 6)$ . De fet este valor existix si i només si $m c d (a, m) = 1$ (l'existència de solucions depén de la condició $m c d (a, m) | b$ , mentres que l'unicitat depén de que el $m c d (a, m) = 1$ ). Més encara, si en usar l'algoritme de Euclides estés (ara en $b = m$ ) s'obté $1 = a s + m t$ , llavors el valor $s$ és l'invers mòdul $m$ de $a$ .

Per eixemple, es desija resoldre l'equació Plantilla:Ecuacion Llavors en l'algoritme de Euclides estés s'obté que $m c d (5, 9) = 1 = 5 (2) + 9 (- 1)$ . Com $m c d (5, 9) = 1$ llavors 5 té un invers mòdul $9$ . Més encara, com $1 = 5 (2) + 9 (- 1)$ , llavors eixe invers és 2. Llavors Plantilla:Ecuacion És dir que el valor de $x$ és $4$ .

Complexitat de l'algoritme

Archiu:Euclidean algorithm running time X Y.png

Gràfica del número de divisions efectuades en l'algoritme de Euclides. El roig indica poques operacions, mentres que els colors més blaus representen major número d'operacions.

La teorema de Lamé afirma que el cas pijor per a este algoritme és quan se li demana calcular el màxim comú divisor de dos números consecutius de la successió de Fibonacci. Per eixemple, si es desija calcular el màxim comú divisor de $f_{10} = 55$ i $f_{11} = 89$ s'obté la següent seqüència d'operacions:

Pas	Operació	Significat
1	89 dividit entre 55 és 1 i sobren 34	$m c d (89, 55) = m c d (55, 34)$
2	55 dividit entre 34 és 1 i sobren 21	$m c d (55, 34) = m c d (34, 21)$
3	34 dividit entre 21 és 1 i sobren 13	$m c d (34, 21) = m c d (21, 13)$
4	21 dividit entre 13 és 1 i sobren 8	$m c d (21, 13) = m c d (13, 8)$
5	13 dividit entre 8 és 1 i sobren 5	$m c d (13, 8) = m c d (8, 5)$
6	8 dividit entre 5 és 1 i sobren 3	$m c d (8, 5) = m c d (5, 3)$
7	5 dividit entre 3 és 1 i sobren 2	$m c d (5, 3) = m c d (3, 2)$
8	3 dividit entre 2 és 1 i sobren 1	$m c d (3, 2) = m c d (2, 1)$
9	2 dividit entre 1 és 2 i sobra 0	$m c d (2, 1) = m c d (1, 0)$

En este eixemple s'observa que en estos dos números de dos dígits decimals, es necessita fer 9 divisions. En general, el número de divisions efectuades per l'algoritme mai supera 5 voltes el número de dígits que tenen estos números. En térmens de complexitat computacional, açò significa que es requerixen $O (\log n)$ divisions per a calcular el màxim comú divisor de $n$ i $m$ a on $n > m$ .

El número promig de divisions efectuades per l'algoritme es va estar investigant des de 1968, pero solament fins a a penes l'any 2002, Brigitte Vallée va demostrar que si els dos números es poden representar en $n$ bits, llavors el número promig de divisions necessàries és $\frac{π^{2}}{6} n$ .

No obstant, no n'hi ha prou en saber el número de divisions. Cal recordar que l'algoritme de Euclides funciona tant per a polinomis com per a número entero, i en general, qualsevol domini Euclídeo. En cada cas, la complexitat de l'algoritme depén del número de divisions efectuades i del cost de cada divisió. En el cas dels polinomis, el número de divisions és $O (\log n)$ a on $n$ és el grau dels polinomis.

Implementació en pseudocódigo

En general, els algoritmes Plantilla:Algref i Plantilla:Algref no són molt apropiats per a implementar-se directament en un llenguage de programació, especialment perque consumixen molta memòria. Si no es necessiten els valors intermijos, i només es desija calcular el màxim comú divisor de dos número entero, convé usar estes variants:

Sobre la notació amprada:

$x \leftarrow y$ significa "assigne a la variable $x$ el valor actual de $y$ ". En llenguages com C, Java, C#, Python i Visual Basic açò significa simplement x = i. En atres llenguages com Pascal es traduïx en a := b, en Maxima és a : b, en R, S i Ocaml és x <- i, i inclusivament s'utilisa la flecha x ← i com el cas d'APL.
$(x, y, z) \leftarrow (a, b, c)$ significa que primer s'evaluen els valors $a, b, c$ i després s'assigna $x \leftarrow a, y \leftarrow b, z \leftarrow c$ , etc. En llenguages com Python, Ruby o Maxima esta instrucció té una estructura molt similar, com per eixemple en Python: (x,i,z) = (a,b,c). En atres llenguages és necessari l'us de variables auxiliars, com per eixemple en llenguage C: aux1 = b; aux2 = c; x = a; i = aux1; z = aux2;.

$a \div b$ significa "el cocient de dividir $a$ entre $b$ ". A esta operació se li coneix també com la divisió truncada perque trunca la part fraccionaria del número. En molts llenguages de programació açò s'implementa simplement com a/b. Atres maneres són a� (Visual Basic) , a div b (Pascal) o be a//b (Python 3).
$a mod b$ significa "el residu de dividir $a$ entre $b$ ". A esta operació se li coneix simplement com a mòdul. En molts llenguages de programació s'implementa com a % b, mentres que en uns atres és a mod b (Visual Basic o Pascal) o be a rem b (Ada).

Vore també

Identitat de Bézout

Referències

↑ Lamé, Gabriel (1844). “Note sur la llimite du nom dones divisions dans la recherche du plus grand commun diviseur entre deux noms entiers” (fr). Actes de les sessions de l'Acadèmia de Ciències 19: 867-870.
↑ Universitat de l'Estany.Consultat el 2023-07-04.

Bibliografia

Enllaços externs

Explicació dinàmica del màxim comú divisor en este vídeo de YouTube[1]. En gaussianos[2] es poden vore explicacions i eixemples una miqueta més alvançats d'este algoritme.

Referències

Este artícul conté una traducció derivada de «Algoritmo de Euclides» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Lamé, Gabriel (1844). “Note sur la llimite du nom dones divisions dans la recherche du plus grand commun diviseur entre deux noms entiers” (fr). Actes de les sessions de l'Acadèmia de Ciències 19: 867-870.

[2] Universitat de l'Estany.Consultat el 2023-07-04.

[1]

[2]