The Euclidean Algorithm computes the greatest common divisor of two integers by performing repeated divisions with remainder. The algorithm is based on the following simple observation: If $a=bq+r$, then $\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r)$. Each time a division is performed with remainder, an old argument can be exchanged for a smaller new one (i.e. swap out $a$ for $r$). Since our remainders are getting smaller and smaller, eventually one of them has to be $0$. At this point, we notice that $\mathrm{gcd}(r,0)=r$ and so the last nonzero remainder is the $\mathrm{gcd}(a,b)$.
Expressing the greatest common divisor of $a$ and $b$ as an integral linear combination of $a$ and $b$ is quite useful in a host of applications. Such a linear combination can be found by reversing the steps of the Euclidean Algorithm. Running the Euclidean Algorithm and then reversing the steps to find an integral linear combination is called the "extended Euclidean Algorithm".
The computation above is powered by SageMath. The Sage code is embedded in this webpage's html file. To view the code instruct your browser to show you this page's source. For example, in Chrome, right-click and choose "View page source".
Wikipedia entry for the Euclidean Algorithm and the Extended Euclidean Algorithm.