The Euclidean Algorithm is an efficient method for finding the Greatest Common Divisor (GCD) of two integers. It uses the principle that the GCD of two numbers does not change if the larger number is replaced by its remainder when divided by the smaller number.

Video Explanation​

Watch

Steps to Implement​

1. Divide the larger number by the smaller number and find the remainder.
2. Replace the larger number with the smaller number and the smaller number with the remainder.
3. Repeat until the remainder is 0. The non-zero remainder is the GCD.

Code Examples​

C++ Implementation​

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

int main() {
    int a, b;
    cout << "Enter two integers: ";
    cin >> a >> b;
    cout << "GCD of " << a << " and " << b << " is: " << gcd(a, b) << endl;
    return 0;
}

Python Implementation​

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

if __name__ == "__main__":
    a = int(input("Enter the first integer: "))
    b = int(input("Enter the second integer: "))
    print(f"GCD of {a} and {b} is: {gcd(a, b)}")

Example Walkthrough​

Example 1: GCD of 56 and 98​

1. $98 \mod 56 = 42$
2. $56 \mod 42 = 14$
3. $42 \mod 14 = 0$

$\text{GCD} = 14$

Example 2: GCD of 101 and 103​

1. $103 \mod 101 = 2$
2. $101 \mod 2 = 1$
3. $2 \mod 1 = 0$

$\text{GCD} = 1$

Applications and Use Cases​

• Simplifying Fractions: Reducing fractions to their simplest form.
• Cryptography: Used in algorithms like RSA for key generation.
• Divisibility Problems: Essential in modular arithmetic and number theory.

Math Representation​

$a = b \times q + r$

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

Diagrams​

Time Complexity​

• Best Case: O(1) (When b divides a evenly right away)
• Average Case: O(log(min(a, b)))
• Worst Case: O(log(min(a, b)))

Space Complexity​

• O(1) as it only uses a few variables to hold the integers and their remainders.

Explanation​

The Euclidean Algorithm reduces the numbers a and b extremely fast. In the worst case (when the numbers are consecutive Fibonacci numbers), the number of steps is proportional to the number of digits in the smaller number, leading to a logarithmic time complexity of O(log(min(a, b))). Space complexity is O(1) for the iterative approach, though a recursive implementation would use O(log(min(a, b))) auxiliary space for the call stack.

Conclusion​

The Euclidean Algorithm is a fundamental technique in number theory for efficiently finding the Greatest Common Divisor (GCD) of two integers. By repeatedly applying the division and remainder operation, it significantly reduces the problem size, making it an optimal solution for GCD calculations.

This algorithm not only forms the basis for many mathematical and computational applications, such as simplifying fractions and cryptographic algorithms, but it also introduces important concepts in algorithm design like iteration and efficiency. Understanding and implementing the Euclidean Algorithm helps build a solid foundation in number theory and algorithmic thinking.