For questions about the uses of the Euclidean algorithm, Extended Euclidean algorithm, and related algorithms in integers, polynomials, or general Euclidean domains. This is not about Euclidean geometry.
The Euclidean algorithm, sometimes called Euclid's algorithm, is a very efficient algorithm for determining the greatest common divisor of two numbers, $\gcd(a,b)$.
When we divide $b$ by $a$, we have an expression like $b = aq + r$, where we think of $q$ as the "quotient" and $r$ as the "remainder." The major idea of the Euclidean algorithm is that any number dividing $a$ and $b$ must also divide $r$. Similarly, any number dividing $a$ and $r$ must also divide $b$. Thus $\gcd(a,b) = \gcd(a,r)$, and $r$ is smaller than $b$. Iterating this procedure is the Euclidean algorithm.
It is a general fact (Bezout's Theorem) that the greatest common divisor of $a,b$ is the smallest positive integer that can be written as a linear combination $ax + by$ for some $x,y$. One way to get such an $x,y$ is to use the Euclidean algorithm and then back-substitute. This is sometimes called the Extended Euclidean algorithm, and is very useful in studying linear congruences, modular arithmetic, and cryptography.
More generally, the Euclidean algorithm works in any context in which there is a well-defined division algorithm. These are called “Euclidean Domains”. One particularly well-known and important Euclidean domain is the ring $\mathbb{Q}[x]$ of polynomials in one variable over the rationals (or over any other field).
Applications of the general Euclidean algorithm and Extended Euclidean algorithm are wide-ranging and diverse.
