Euclidean Algorithm

The Euclidean algorithm is one of the earliest algorithms that provide a solution for the greatest common divisor (GCD) of two numbers. The greatest common divisor of two integers is a process of finding the largest integer that will leave those two integers with no remainder upon division. 

It is called the Euclidean algorithm because this description was created by Euclid, the ancient Greek mathematician, in the book “Elements, written” about 300 BCE. The Euclidean algorithm is important and applicable in a wide range of mathematics, such as number theory, cryptography, and computer science.

Here is the explanation, examples, working, etc., of the Euclidean algorithm discussed in an easy way.

What is the Euclidean Algorithm? 

The Euclidean Algorithm builds on one fact: the GCD of two numbers divides their difference. This property is used to reduce the problem of finding the GCD of large numbers to that of smaller numbers. In particular, let 𝑎 and 𝑏 be integers such that 𝑎>𝑏. The algorithm works by successively replacing the larger number with that number modulo, the smaller number, and stopping when one of the numbers is 0. The non-zero number at this point is the GCD of the two original numbers.

How to Find GCD Using Euclidean Algorithm?

To illustrate the Euclidean Algorithm, let us consider two positive integers, a and b, where ( a > b). 

The steps are as follows:

1. Initial Step: Assign the larger number to a and the smaller number to b.

2. Division Step: Divide a by b and find the remainder r.

3. Replacement Step: Replace a with b and b with r 

4. Repeat: Repeat the division and replacement steps until b becomes zero.

5. Result: When (b) is zero, the GCD is the value of (a).

Example: Finding the GCD of Two Numbers Using the Euclidean Algorithm

Let us find the GCD of 252 and 105 using the Euclidean Algorithm:

1. Step 1: ( a = 252 ), ( b = 105 )

2. Step 2: Divide 252 by 105 ( 252 ÷ 105 = 2 ) with a remainder of  42. So, a = 105 ,  b = 42.

3. Step 3: Divide 105 by 42:  105 ÷ 42 = 2 with a remainder of 21. So, a = 42 , b = 21.

4. Step 4: Divide 42 by 21: ( 42 ÷ 21 = 2 ) with no remainder. So, ( a = 21), ( b = 0 ).

When b becomes 0, ( a = 21 ), which is the GCD of 252 and 105.

The Extended Euclidean Algorithm

The Extended Euclidean Algorithm is a modification of the Euclidean Algorithm that not only computes the GCD of two integers a and b but also finds integers x and y such that:

\ax + by = {GCD}(a, b)]

This equation is known as Bézout’s identity. The coefficients x and y are useful in many areas, including solving Diophantine equations and in cryptographic algorithms such as RSA.

How the Extended Euclidean Algorithm Works?

• Initialization: Define the first numbers a and b.
• Apply Euclidean Algorithm: Now, let us find the GCD of two numbers by following the steps in the Euclidean Algorithm Steps.
• Track Coefficients: While performing the divisions, it is important to remember the coefficients that precede the remainders and which form the value on an integral scale (these can be added in various arrays or variables).
• Back Substitution: Now that we have found the GCD, use back substitution to represent it in terms of the original integers.

Example: Extended Euclidean Algorithm

To find the GCD of 252 and 105 along with coefficients x and y

• Step 1: Perform the Euclidean Algorithm as above.
• Step 2: Keep track of the coefficients:

(252 = 2× 105 + 42 ) ⟹ ( 42 = 252 – 2 × 105)

 ( 105 = 2 ×42 + 21) ⟹ ( 21 = 105 – 2 ×42)

 ( 42 = 2 × 21 + 0 )

• Step 3: Back substitute to express 21 (the GCD) as a combination:

( 21 = 105 – 2 ×(252 – 2 × 105))

 ( 21 = 105 – 2 × 252 + 4 × 105)

 ( 21 = 5 × 105 – 2× 252)

Thus, (x = -2) and ( y = 5 ), so ( 252(-2) + 105(5) = 21 ).

Conclusion

The Euclidean Algorithm is developed to demonstrate that, in the end, the programmer can arrive at the most efficient way of calculating the GCD of two numbers. Its modification, the Extended Euclidean Algorithm, is useful in delivering coefficients that give the GCD in terms of the original numbers again in terms of a linear combination. These algorithms are important in the domains of number theory and are applied in several fields, including cryptography and algorithms. Join Turito to learn about these and many other concepts through expert-led classes. 

FAQs