Euclidean Algorithm
The Euclidean Algorithm is the most ancient and highly efficient method for finding the Greatest Common Divisor (GCD) of two positive integers $a$ and $b$. It is one of the first algorithms ever recorded, appearing in Euclid's Elements around 300 BC.
1. Core Principle
Let $\text{gcd}(a, b)$ be the greatest common divisor of two integers $a$ and $b$. The algorithm is based on the following property:
Principle: If a larger integer $a$ is divided by a smaller integer $b$, yielding a remainder $r$, then the GCD of $a$ and $b$ is always equal to the GCD of $b$ and $r$. $$\text{gcd}(a, b) = \text{gcd}(b, r)$$
This process of replacing the larger number with the smaller number, and the smaller number with the remainder, is repeated until the remainder is $0$. The divisor just before the remainder becomes $0$ is the GCD.
2. Example of the Euclidean Algorithm
Let's find the GCD of two integers $a=1071$ and $b=462$.
| Step | Calculation ($a=bq+r$) | Remainder $r$ |
|---|---|---|
| 1st Step | $1071 = 462 \times 2 + 147$ | $147$ |
| 2nd Step | To find $\text{gcd}(462, 147)$, we divide $462$ by $147$ | |
| 3rd Step | $462 = 147 \times 3 + 21$ | $21$ |
| 4th Step | To find $\text{gcd}(147, 21)$, we divide $147$ by $21$ | |
| 5th Step | $147 = 21 \times 7 + 0$ | $0$ |
Result: The remainder became $0$ in the 5th step, and the divisor at that point was $21$.
$$\text{gcd}(1071, 462) = \mathbf{21}$$
[Image of Euclidean Algorithm flow chart]
3. Significance of the Algorithm
- Efficiency: It is highly efficient because the number of divisions required grows very slowly, making it fast even for very large numbers.
- Extended Euclidean Algorithm: This core principle is extended to find integers $x$ and $y$ that satisfy Bézout's identity, $ax + by = \text{gcd}(a, b)$.
- Cryptography: The Extended Euclidean Algorithm is essential for calculating the private key $d$ in the RSA Encryption scheme, as shown in the previous topic.