Algoritmo de Euclides y algoritmo extendido de Euclides

El algoritmo de Euclides [1] es un algoritmo que, dado dos números, calcula el máximo común divisor (gcd) de dichos números. Para determinar si dos o más números son relativamente primos entre si, su máximo común divisor debe ser igual que 1.

El algoritmo extendido de Euclides [2] es una modificación del algoritmo original que nos permite determinar los valores para $x$ y $y$ que nos da la siguiente igualdad:

$gcd(a, b) = (a * x) + (b * y)$ References;
[1] Euclidean algorithm, n,d. http://en.wikipedia.org/wiki/Euclidean_algorithm (accessed September 18, 2014)
[2] Extended Euclidean algorithm, n,d. http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm (accessed September 18, 2014)