Solution Review 1: Euclidean Algorithm
Explore the Euclidean algorithm to compute the greatest common divisor (GCD) of two numbers using recursive and iterative methods. Understand how the extended Euclidean algorithm calculates integer coefficients for inputs and its relevance to modular inverses, essential in encryption techniques like RSA.
How does the Euclidean algorithm work?
The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger value of the two is replaced by the difference between both numbers.
Let’s look at an example:
The GCD of and is ( = x and = x ). Now, is also the GCD of ...
Source: Euclidean Algorithm - Wikipedia under lisense CC-BY-SA 3.0