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
The Euclidean algorithm was named after the Greek mathematician Euclid and is used to effectively determine the greatest common divisor, as well as determine the smallest common content of two or more integers.
Determination 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 rest of division 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:
Both A and B are divisible by GCD
The rest of division 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.
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.
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.
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.
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:
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:
The following code will then calculate LCM based on GCD:
Figure 8: Determination of LCM based on the method for calculating GCD
|
Next
Basic data structures >| |