Classical Cryptography Simulator

GCD Calculator

Calculate the Greatest Common Divisor (GCD) of two numbers using the Euclidean algorithm. See step-by-step calculations and understand the mathematical process.

Input Numbers
Enter two positive integers to calculate their GCD
Result
GCD calculation result and information

Enter numbers and click Calculate to see the result

About GCD
Understanding the Greatest Common Divisor

What is GCD?

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder.

Euclidean Algorithm

The Euclidean algorithm is an efficient method for computing the GCD:

  1. Divide the larger number by the smaller number
  2. Find the remainder
  3. Replace the larger number with the smaller number
  4. Replace the smaller number with the remainder
  5. Repeat until the remainder is 0
  6. The last non-zero remainder is the GCD

Applications

  • Simplifying fractions
  • Finding least common multiples (LCM)
  • Cryptography (RSA algorithm)
  • Number theory problems