Choose jour language!

---

|

The Euclidean Algorithm

Determination of the greatest common divisor (GCD) and Least common multiple (LCM) determine in an efficient way using the EUCLID's algorithm calculator

​Euclid's algorithm, named after the Greek mathematician Euclid, is one of the oldest known mathematical algorithms. It was first described in Euclid's "Elements" more than 2000 years ago, and its basic structure has remained unchanged to this day. This algorithm is used to efficiently find the greatest common divisor (GCD) of two or more integers. Its simplicity, precision and wide application make it one of the most important tools in mathematical and algorithmic disciplines.

Euclid's algorithm is primarily used to find the greatest common divisor (GCD) of two numbers. This is a useful procedure in many mathematical and engineering problems, as it enables the simplification of fractions, the analysis of cyclic processes, and the solving of divisibility problems. Apart from finding the GCD, the algorithm is also used to calculate the least common component (LCM) of two numbers, which further increases its practical value.

Why is it important?

Euclid's algorithm is widely used in various fields:

• Mathematics: The algorithm is used in number theory to solve divisibility problems, as well as to generate extended versions of the algorithm that allow solving Diophantine equations.
• Programming: As one of the basic algorithms, it is often used in software engineering and algorithmic challenges. Its efficiency and simplicity make it a perfect example of algorithmic optimization.
• Cryptography: In modern applications, the Euclidean algorithm is a key element in cryptographic key generation and analysis algorithms, such as the RSA and Diffie-Hellman protocols.

Determining the greatest common divisor(GCD) ​

​Treating GCD of two numbers A and B is based on the fact that:

• Both A and B are divisible by GCD
• The remainder of the division of A and B is also divisible by GCD

This means that if A and B are integers whose GCD is sought, and if we denote that d = GCD, p is the result of the division and q is the remainder of the division, then it can be written:
A = p * B + q, p and q are integers
Hence, A, B, and q are divisible by d
Let's look at this in the next example for numbers A = 48 and B = 28
Let's fix the first GCD:

Figure 1: Determination the greatest common divisor (GCD) using the EUCLID's algorithm

The picture below shows the classic way of determining the GCD, and this is in this case 4.
In Fig. B, it can be seen that GCD is included in numbers 48 and 28, but also in the remainder of the division of these two numbers. So, we can say that:
​
48 = 1 * 28 + 20
which corresponds to expression 1:

A = p * B + q, p and q are integers

See fig. B) that B and q will be divisible by GCD.
If we now take the GCD for B and q, i.e. for 28 and 20 we would see the GCD the same.
By repeating the process of dividing the previous sender with the remainder of the division, while in one iteration the remainder of the division is zero, we will reach the number representing the GCD. The last result of a division is actually the number we are looking for. In our example, this is number 4. See figure c).
The previous procedure is known as the Euclidean algorithm.
​

Examples and Context

In addition to the example with A=48 and B=28, incorporating more diverse examples with larger numbers can illustrate the robustness of the Euclidean algorithm. For instance:

1. Example with Larger Numbers
   Let's calculate the GCD for A=987654 and B=123456. This highlights the efficiency of the algorithm, even with significant numerical inputs, emphasizing its applicability in computational contexts.
2. Real-World Application: Cryptography
   In cryptographic algorithms such as RSA, the Euclidean algorithm plays a crucial role in computing modular inverses. Demonstrating this use case can show how the algorithm underpins modern security systems, making the theoretical aspect relatable to real-world scenarios.
3. LCM Calculation Using GCD
   An example of calculating the least common multiple (LCM) of two numbers using their GCD can extend the context:
   LCM(A,B)=∣A*B∣/GCD(A,B)​.
   Showing how the Euclidean algorithm indirectly aids in finding the LCM would underscore its versatility.

Determination GCD ​ algoritm:

The program loads two integers a and b and determines the GCD for these two numbers. It is marked higher than the two, and b is smaller.

Figure 2: Determination algorithm GCD iteratively

​the code that solves this problem in an iterative manner would be:

Figure 4: Determination of GCD using the Euclidean algorithm-iterative

​First, two integers x and y are loaded, the larger and smaller the ones are checked and they are placed in the variable
a - greater between x and y
b - smaller between x and y
By the Iterative process, the process of searching for the remainder of the division of the sender and the remainder into the division of the previous iteration is repeated. The procedure is repeated while the rest of the division is different from zero. The last divider in the loop is actually a GCM.

Determination of GCD by recursion - algorithm:

Instead of iteratively through the loop, this problem can be solved recursively:

Figure 5: Determination of GCD using the Euclidean algorithm using a recursive method

The GCDRek function receives two parameters a and b, so that the first is greater than the other. If the remainder of the division r is equal to zero, the second number is returned, that is, the divisor. If not, the procedure is repeated so that the function invokes itself and changes the parameters, so that the first, dividend is in fact the previous divisor, ie, another parameter in the previous call. In the second place is the rest of the partition from the previous recursive call.

The Connection Between Iterative and Recursive Approaches

The iterative and recursive implementations of the Euclidean algorithm are complementary methods, each with unique advantages, depending on the context:

1. Iterative Approach
   
   • The iterative method uses loops to repeatedly calculate the remainder until it reaches zero.
   • Practical Use: It is often preferred in environments where stack memory is limited, as it avoids the overhead of recursive calls. This makes it ideal for embedded systems or performance-critical applications.
2. Recursive Approach
   
   • The recursive method leverages function calls, reducing the problem size with each call until a base case is reached.
   • Practical Use: It is more intuitive for mathematical problem representation and easier to implement in languages with optimized recursion handling, such as functional programming paradigms.
3. How They Complement Each Other
   
   • While the recursive approach provides clarity and elegance in code, the iterative version is more robust in systems where recursion depth is a concern.
   • Both methods solve the same problem with identical results, reinforcing the algorithm's correctness from multiple perspectives.
4. Examples in Practice
   
   • The recursive approach might be demonstrated in scenarios involving symbolic mathematics or theoretical explanations.
   • The iterative method is better suited for practical engineering tasks or when operating on large data sets in constrained environments.

---

Determination of the Least common multiple(LCM)

​the Least common multiple can be determined by first determining the GCD and then from the expression
LCM (a, b) * GCD (a, b) = a * b

determines LCM
LCM = a / (GCD (a, b) * b;
In the example described above for numbers 48 and 28:

Figure 7: Determination Least common multiple(LCM)

The figure under a) shows how the GCD is determined, and in the picture b) LCM for numbers 48 and 28. In Figure c) it was shown that the product GCD and LCM is equal to the product of numbers 28 and 48, i.e. in some general case a and b.
The following code will then calculate LCM based on GCD:

Figure 8: Determination of LCM based on the method for calculating GCD

Extended Euclidean Algorithm

Introduction to the Extended Euclidean Algorithm is a powerful extension of the standard Euclidean Algorithm. While the Euclidean Algorithm determines the greatest common divisor (GCD) of two integers, the extended version also finds integers x and y that satisfy the equation:

ax+by=GCD(a,b)

This additional functionality makes it invaluable in areas such as solving linear Diophantine equations and modular arithmetic.

Mathematics Behind the Algorithm:
Solving Diophantine Equations are equations where solutions are sought in integers. The Extended Euclidean Algorithm provides a constructive way to find such solutions for the equation ax+by=d, where d is the GCD of a and b. By working backwards from the Euclidean steps, it determines the coefficients x and y. This process ensures that the equation is satisfied by these integers.
Practical Applications in Cryptography and Number TheoryThe Extended Euclidean Algorithm is widely used in:

1. Cryptography: Computing modular inverses in algorithms like RSA for efficient encryption and decryption.
2. Number Theory: Solving linear congruences and finding integers that satisfy certain modular properties.
3. Computer Science: Applications in hashing, data compression, and coding theory.

Iterative and Recursive Implementations with ExplanationsThe algorithm can be implemented in both iterative and recursive manners. Here is an explanation of each:

1. Iterative Implementation:
   The iterative approach computes the GCD while simultaneously maintaining the coefficients x and y. The algorithm stores intermediate values and updates them as the division process proceeds. This is efficient for environments where stack depth is a limitation.
2. Recursive Implementation:
   The recursive method follows a more intuitive approach, directly solving for x and y as it unwinds the recursive calls. This is generally simpler to understand and implement but can be limited by recursion depth in some programming environments.

Example: Modular Inverse and Solving Congruences

1. Finding Modular Inverse:
   To compute the modular inverse of a % m(a modul m), use the Extended Euclidean Algorithm to find x such that ax+my=1. The value of x modulo m is the inverse.
2. Example Code:

#include <iostream>
#include <tuple>

// Function for the extended Euclidean algorithm
std::tuple<int, int, int> extended_gcd(int a, int b) {
    if (b == 0) {
        return {a, 1, 0};
    }

    int gcd, x1, y1;
    std::tie(gcd, x1, y1) = extended_gcd(b, a % b);

    int x = y1;
    int y = x1 - (a / b) * y1;

    return {gcd, x, y};
}

// Testing the function
int main() {
    int a = 48, b = 18;
    int gcd, x, y;

    std::tie(gcd, x, y) = extended_gcd(a, b);

    std::cout << "GCD: " << gcd << ", x: " << x << ", y: " << y << std::endl;

    return 0;
}

Explanation:

1. Input Parameters: The function takes two integers a and b as input.
2. Base Case: If b is 0, it returns:
   • GCD as a.
   • Coefficients x = 1 and y = 0, satisfying ax+by=GCD.
3. Recursive Call: The function recursively calls itself with b and a % b.
4. Updating Coefficients:
   • x is updated to the value of y from the recursive call.
   • y is calculated as x1−(a/b)*y1, where x1 and y1 are the coefficients from the recursive step.
5. Tuple Return: It uses std::tuple to return three values: the GCD and the coefficients x and y.

Example:

For a = 48 and b = 18:

• GCD: 6.
• Coefficients: x=−1 and y=3.

​​

This satisfies the equation:

6=48⋅(−1)+18⋅3

Practical Use:
This implementation can be used in cryptographic algorithms like RSA and for solving modular equations involving multiplicative inverses.

---

​Previous
​|< Eratosthenes sieve

Next
​​​​​​Basic data structures >|

---