Euklides algorithm is one of the most ancient algorithms in mathematics used to calculate GCD (Greatest Common Divisor), or FPB (Large Fellowship Factor), of two integers. GCD is the largest number that divides both numbers without leaving any residue. This algorithm is named after ancient Greek mathematicians, Euclid, who introduced him in his book. Elements Around the 3rd century B.C.

In addition to being known for its simplicity, it's highly efficient and still used in modern applications such as cryptography and computation. This article will discuss the definition of GCD, step-step explanation of the Euklides algorithm, and its applications in modern context.

GCD understanding

GCD of two integers aaa and bbb are the largest integers that can divide those two numbers without leaving any residue. For example, GCD from 48 and 18 is 6, because 6 is the largest number that divides 48 and 18.

Formal, if aaa and bbb are two positive integers, then GCD (a, b) text {GCD} (a, b) GCD (a, b) is the biggest integer of ddd (a, b) such as that: d dhadd Aqd mid a quad text {and} quad d bd bd dhadb

That is, ddd split aaa and bbb with no leftovers.

Euklides algorithm

Euklides algorithm works by using the basic properties of GCD: if aaa and bbb are two integers, then GCD (a, b) = GCD (b, r) text {GCD} (a, b) = text {GCD} (b) GCD (a, b) = GCD (b, r), where rrr is left by abbb. By using this trait, the algorithm continues to reduce numbers until one of them becomes zero, and the GCD is another number left.

Euklides algorithm steps

1. Start with two numbers: Suppose we had two aaa numbers and a bbb, where a > ba > ba > b.
2. Do the divisionShare aaa with bbb and get the rest, r = amod br = a mod br = amodb.
3. Update numberChange aaa with bbb, and bbb with rrr.
4. Repeat: Repeat steps 2 and 3 to b = 0b = 0b = 0.
5. GCD found: When b = 0b = 0b = 0, the value aaa at the last step is GCD of two original numbers.

Euklides Algorithm Example

Let's calculate GCD of 48 and 18 using Euklides algorithm:

1. Step 1Start with 48 and 18.
2. Step 2For 48 is 18, and the rest is 48mod 18 = 1248 mod 18 = 1248mod18 = 12. So, updating a = 18a = 18a = 18 and b = 12b = 12b = 12.
3. Step 3: Divide 18 by 12, and the rest is 18mod 12 = 618 mod 12 = 618mod12 = 6. Update a = 12a = 12a = 12 and b = 6b = 6b = 6b = 6.
4. Step 4Divide 12 by 6, and the rest is 12mod 6 = 012 mod 6 = 012mod6 = 0. Update a = 6a = 6a = 6 and b = 0b = 0b = 0b = 0.
5. Results: When b = 0b = 0b = 0, the value aaa is 6, so GCD (48.18) = 6text {GCD} (48, 18) = 6GCD (48.18) = 6.

This algorithm requires only a few simple steps to find GCD, even for relatively large numbers. His high independence is one of the reasons why this algorithm remains in use today.

Euklides algorithm variation

There is also Divided Euklides algorithm (Extended Euclidean Algorithm) which not only finds GCD of two numbers but also produces linear combinations of the two numbers. That means that this algorithm provides a solution for the equation: GCD (a, b) = ax + bytext {GCD} (a, b) = ax + byGCD (a, b) = ax + by

Where xxx and yyy are integer coefficient that meet the equation above. This algorithm works in numbers theory and cryptography, especially in algorithms like RSA that depend on GCD and modular invers.

Euklides Algorithm Modern Applications

Although found over two millennia ago, Euklides algorithm is relevant and used in various modern applications, especially in the field cryptography, Number theory, and computing. Some examples of the application are between us:

1. Asymmetric Cryptography (RSA): This algorithm is used to calculate important modular invers in RSA encryption and decryption algorithms. In RSA, the GCD count helps determine whether two prime relative numbers and can generate public and private keys.
2. Number TheoryIn number theory, Euklides algorithm is used to solve problems like looking for modular invers, solving Diophantine equations, and more.
3. Computer System: Many computer systems are using these algorithms for tasks such as large division numbers, scheduling and hardware optimizations.
4. Data Science and Programming AlgorithmThis algorithm is also used in programming algorithms and data structures, such as binary trees searching and optimization algorithms.

Conclusion

Euklides algorithm is a simple but effective method to calculate GCD or FPB of two integers. Although very old-fashioned, these algorithms continue to be used today in various modern applications, especially in cryptography and number theory. Flexibility and efficiency makes it one of the most important algorithms in math and computing.

source: Hardy, G. H., & Wright, E. M. (2008). An interrogation to the Theory of Numbers. Oxford University Press.