Greatest Common Divisor (GCD)

Calculator and example for computing the greatest common divisor

GCD Calculator

Greatest common divisor

Computes the greatest common divisor (GCD) of two natural numbers using the Euclidean algorithm. The GCD is the largest number that divides both without remainder.

gcd(328, 256) = ?
Enter numbers
Natural number greater than 0
Natural number greater than 0
Calculation result
GCD =
Calculation using the Euclidean algorithm

GCD Info

Properties

GCD: Largest number that divides both values without remainder

Euclid Algorithm GCD

Definition: gcd(a,b) is the largest positive integer that divides both a and b without remainder
Computation: Euclidean algorithm

Algorithm steps
1. Divide the larger by the smaller
2. Divide the divisor by the remainder
3. Repeat until remainder = 0
4. Last divisor is the GCD

Euclidean Algorithm

Algorithm definition
\[\gcd(a,b) = \gcd(b, a \bmod b)\]

Recursive definition of the Euclidean algorithm

Base case
\[\gcd(a,0) = a\]

Termination condition of the algorithm

Properties
\[\gcd(a,b) = \gcd(|a|,|b|)\] \[\gcd(a,b) \cdot \text{lcm}(a,b) = a \cdot b\]

Important mathematical properties

Complexity
\[O(\log(\min(a,b)))\]

Logarithmic time complexity

Example: gcd(328, 256)

Step-by-step computation
Step 1: 328 ÷ 256 = 1 remainder 72
Step 2: 256 ÷ 72 = 3 remainder 40
Step 3: 72 ÷ 40 = 1 remainder 32
Step 4: 40 ÷ 32 = 1 remainder 8
Step 5: 32 ÷ 8 = 4 remainder 0 ✓
gcd(328, 256) = 8
Explanation

The algorithm always divides the larger number by the smaller

The remainder becomes the new divisor

Repeat until remainder = 0

Last divisor is the GCD

Verification

328 ÷ 8 = 41 ✓

256 ÷ 8 = 32 ✓

Algorithm steps visualized
a ÷ b
→ remainder r
b ÷ r
→ remainder r'
...
remainder = 0

Repeat until the remainder becomes zero

Applications of the GCD

The greatest common divisor is fundamental in mathematics and has practical applications:

Fractions
  • Reduce fractions to lowest terms
  • Determine common denominators
  • Find equivalent fractions
  • Simplify fraction operations
Cryptography
  • RSA encryption
  • Primality tests
  • Compute modular inverses
  • Chinese remainder theorem
Engineering
  • Optimize gear ratios
  • Analyze periodic signals
  • Synchronize clock frequencies
  • Design modular systems
Algorithms
  • Efficiency analysis
  • Number-theoretic algorithms
  • Computer algebra systems
  • Optimization problems

The GCD: Foundation of number theory

The greatest common divisor is a central concept in elementary number theory. The Euclidean algorithm, one of the oldest known algorithms (c. 300 BC), provides an elegant and efficient method to compute the GCD. Its logarithmic time complexity makes it practical even for large numbers and forms the basis for many modern cryptographic procedures and computer algebra applications.

Properties
  • gcd(a,b) divides both a and b
  • Every common divisor divides the gcd
  • gcd(a,b) = gcd(b, a mod b)
  • gcd(a,0) = |a|
Significance
  • Fundamental number theory
  • Basis for cryptography
  • Algebraic algorithms
  • Practical applications
Algorithm advantages
  • Very efficient (logarithmic)
  • Easy to implement
  • Works for all integers
  • Proven for over 2000 years
Summary

The greatest common divisor connects ancient mathematical wisdom with modern applications. The Euclidean algorithm demonstrates the elegance of mathematical algorithms and their timeless relevance. From fraction arithmetic to RSA encryption, the GCD shows how basic number-theoretic concepts underpin complex technical innovations and unite mathematical beauty with practical utility.