By: Taspia Jannat

      The Euclidean Algorithm is a way to find the greatest common divisor of two positive integers, a and b. The GCD is the largest number that divides two numbers without a remainder. To find the GCD, we can make a list of all factors for the two numbers and find the largest factor that is on both sides. This would be a good way of doing it on small numbers but can get a bit tiring if we had to deal with much bigger numbers like 587. To recap a bit of history, the Euclidean Algorithm is named after the ancient Greek mathematician Euclid who first introduced this procedure in one of his books called the “Elements.” The way the Euclidean Algorithm works is in a recursive fashion by replacing the larger of the 2 numbers with the remainder of dividing those two numbers. This will be continued until the remainder is found to be 0. An example of how to find the GCD using the Euclidean Algorithm is: 

Linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results. You can use the Euclidean Algorithm to write the GCD of two numbers as a linear combination of the two numbers by writing out the expression equalling the GCD. Once you have the GCD, you can work backward to find the coefficients of the linear combination. For the picture below, we can see that the GCD of 270 and 192 is 6 so we write it as an expression equal to 6 as a linear combination. Then, we expand the expression using the second remainder of the equation which is 36, we substitute the expression and then distribute to get rid of the parentheses and then combine the like terms if necessary and then we get a linear combination.