GCD – Euclidean Algorithm

🚀 Introduction

In this post, I'll explain how to implement the Euclidean Algorithm to find the Greatest Common Divisor (GCD) of two numbers. This fundamental algorithm is essential for developers working with number theory, cryptography, or mathematical computations.

🧠 Problem Statement / Objective

Implement the Euclidean Algorithm to find the GCD of two integers in both Java and Python, with proper test cases to verify correctness.

🧩 Tools & Technologies Used

• Languages: Java, Python

• Algorithm: Euclidean Algorithm

• Concepts: Recursion, Modular Arithmetic

💻 Java Code

package maths;

public class Gcd {

    public static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        System.out.println(gcd(60, 36));    // Output: 12
        System.out.println(gcd(10, 5));     // Output: 5
        System.out.println(gcd(8, 12));     // Output: 4
        System.out.println(gcd(100, 25));   // Output: 25
        System.out.println(gcd(81, 27));    // Output: 27
    }
}

💻 Python Code

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

# Test cases
print(gcd(60, 36))    # Output: 12
print(gcd(10, 5))     # Output: 5
print(gcd(8, 12))     # Output: 4
print(gcd(100, 25))   # Output: 25
print(gcd(81, 27))    # Output: 27

📘 Explanation

Euclidean Algorithm Basics:

The GCD of two numbers is the largest number that divides both of them without leaving a remainder. The Euclidean algorithm is based on the principle that the GCD of two numbers also divides their difference.

Key Points:

1. Base Case: When b becomes 0, a is the GCD

2. Recursive Step: The GCD of a and b is the same as the GCD of b and a % b (remainder of a divided by b)

3. Termination: The algorithm guarantees that b will eventually become 0

Time Complexity:

• O(log(min(a,b))): Very efficient even for large numbers

• Each recursive call reduces the problem size significantly

🛠️ Output / Result

12
5
4
25
27

📌 Real-World Use Cases

1. Cryptography: RSA algorithm uses GCD for key generation

2. Fraction Simplification: Reducing fractions to simplest form

3. Computer Graphics: Calculating aspect ratios

4. Scheduling Problems: Finding repeating patterns

5. Number Theory: Fundamental for many advanced algorithms

🧵 Conclusion

The Euclidean algorithm demonstrates:

• The power of recursion in solving mathematical problems

• How modular arithmetic can simplify computations

• The elegance of mathematical algorithms in code

The Java and Python implementations show how the same algorithm translates across languages with minimal syntactic differences.