Euclidean and Extended Euclidean Method

Euclidean Algorithm and Extended Euclidean Algorithm

The Euclidean Algorithm and Extended Euclidean Algorithm are two fundamental methods in number theory used to compute the Greatest Common Divisor (GCD) of two integers. The Euclidean Algorithm is a classic, efficient method for finding the GCD, while the Extended Euclidean Algorithm also computes additional information, such as the coefficients of the linear combination of the integers involved.

---

1. Euclidean Algorithm

The Euclidean Algorithm is an efficient method for finding the GCD of two integers $a$ and $b$. It works by repeatedly applying the division algorithm (dividing the larger number by the smaller one and replacing the larger number with the remainder) until the remainder is zero. The last non-zero remainder is the GCD of the two numbers.

Steps to Apply the Euclidean Algorithm:

1. Given two numbers $a$ and $b$, where $a > b$, divide $a$ by $b$ and obtain the quotient and remainder:

   $$a = b \times q + r$$

   where $q$ is the quotient and $r$ is the remainder.

2. Replace $a$ with $b$ and $b$ with $r$, and repeat the process until $r = 0$.

3. When the remainder becomes zero, the GCD is the last non-zero remainder.

Example: Finding $\gcd(48, 18)$

Let’s use the Euclidean algorithm to find $\gcd(48, 18)$:

1. Divide 48 by 18:

   $$48 \div 18 = 2 \quad \text{(quotient)}, \quad 48 - 18 \times 2 = 48 - 36 = 12 \quad \text{(remainder)}$$

   So, $\gcd(48, 18) = \gcd(18, 12)$.

2. Divide 18 by 12:

   $$18 \div 12 = 1 \quad \text{(quotient)}, \quad 18 - 12 \times 1 = 18 - 12 = 6 \quad \text{(remainder)}$$

   So, $\gcd(18, 12) = \gcd(12, 6)$.

3. Divide 12 by 6:

   $$12 \div 6 = 2 \quad \text{(quotient)}, \quad 12 - 6 \times 2 = 12 - 12 = 0 \quad \text{(remainder)}$$

   The remainder is now 0, so the GCD is 6.

Thus, $\gcd(48, 18) = 6$.

---

2. Extended Euclidean Algorithm

The Extended Euclidean Algorithm not only computes the GCD of two integers $a$ and $b$, but also finds the coefficients $x$ and $y$ (called Bezout coefficients) such that:

$$a \times x + b \times y = \gcd(a, b)$$

In other words, the Extended Euclidean Algorithm expresses the GCD of $a$ and $b$ as a linear combination of $a$ and $b$.

This is particularly useful in many areas, such as modular arithmetic, where we need to find the modular inverse of a number.

Steps to Apply the Extended Euclidean Algorithm:

1. Use the Euclidean algorithm to find the GCD of $a$ and $b$.
2. While performing the steps of the Euclidean algorithm, also keep track of the coefficients of $a$ and $b$ in the linear combinations.
3. After completing the Euclidean algorithm, backtrack through the steps to express the GCD as a linear combination of $a$ and $b$.

Example: Extended Euclidean Algorithm for $\gcd(48, 18)$

We will use the Extended Euclidean Algorithm to find the GCD and the Bezout coefficients for $\gcd(48, 18)$.

1. Start by applying the Euclidean algorithm:

   $$48 \div 18 = 2 \quad \text{(quotient)}, \quad 48 - 18 \times 2 = 12 \quad \text{(remainder)}$$

   So, $\gcd(48, 18) = \gcd(18, 12)$.

   $$18 \div 12 = 1 \quad \text{(quotient)}, \quad 18 - 12 \times 1 = 6 \quad \text{(remainder)}$$

   So, $\gcd(18, 12) = \gcd(12, 6)$.

   $$12 \div 6 = 2 \quad \text{(quotient)}, \quad 12 - 6 \times 2 = 0 \quad \text{(remainder)}$$

   The remainder is now 0, so the GCD is 6.

2. Now, backtrack to express 6 as a linear combination of 48 and 18:

   • From $18 - 12 \times 1 = 6$, we have: $$6 = 18 - 12 \times 1$$
   • From $48 - 18 \times 2 = 12$, we substitute $12$ from the previous step: $$12 = 48 - 18 \times 2$$ Substituting this into the equation for 6: $$6 = 18 - (48 - 18 \times 2) \times 1$$ Simplifying: $$6 = 18 - 48 + 18 \times 2$$ $$6 = 3 \times 18 - 48$$

Thus, we have expressed 6 as a linear combination of 48 and 18:

$$6 = 3 \times 18 - 1 \times 48$$

So, the Bezout coefficients are $x = -1$ and $y = 3$.

This means that:

$$48 \times (-1) + 18 \times 3 = 6$$

General Formula:

If you run the Extended Euclidean Algorithm on integers $a$ and $b$, you will get $\gcd(a, b) = ax + by$, where $x$ and $y$ are the coefficients of $a$ and $b$ in the linear combination.

---

3. Applications of the Extended Euclidean Algorithm

• Modular Inverse: One of the most common applications of the Extended Euclidean Algorithm is finding the modular inverse of a number. If $a$ and $m$ are coprime (i.e., $\gcd(a, m) = 1$), then the modular inverse of $a$ modulo $m$ is the $x$-coefficient in the equation $ax + my = 1$. The modular inverse is useful in cryptographic algorithms like RSA.

• Diophantine Equations: The Extended Euclidean Algorithm is used to find integer solutions to linear Diophantine equations of the form $ax + by = c$.

• Cryptography: In RSA and other cryptographic systems, the Extended Euclidean Algorithm is used to compute the private key from the public key.

• Solving Linear Systems: The algorithm can be used to solve systems of linear equations where the coefficients are integers.

---

4. Conclusion

• The Euclidean Algorithm is a fast method for computing the GCD of two integers by repeated division and finding remainders.
• The Extended Euclidean Algorithm not only computes the GCD but also finds the coefficients (Bezout coefficients) that express the GCD as a linear combination of the two integers. This is crucial for solving problems like finding modular inverses and solving Diophantine equations.