GCD and the Euclidean Algorithm

Introduction

The greatest common divisor is one of the oldest and most fundamental concepts in mathematics. When we reduce a fraction to lowest terms, we divide both numerator and denominator by their greatest common divisor. When we solve Diophantine equations, we need to know whether a solution exists—and the GCD tells us. When we implement the RSA cryptosystem, the Euclidean algorithm computes the modular inverses that make encryption possible.

The Euclidean algorithm, described by Euclid around 300 BCE, is arguably the oldest non-trivial algorithm still in widespread use today. Its elegance lies in reducing a seemingly difficult problem—finding the largest common factor of two numbers—to a sequence of simple divisions. The algorithm is fast, easy to implement, and reveals deep structural properties of the integers.

Understanding the GCD and Euclidean algorithm is essential for number theory, abstract algebra, cryptography, and computer science. These concepts form the foundation upon which modular arithmetic, prime factorization theory, and much of modern cryptography are built.

Definition of the Greatest Common Divisor

Basic Definition

Let a and b be integers, not both zero. A common divisor of a and b is an integer d such that d*(∣_^)(a) and d*(∣_^)(b) (that is, d divides both a and b).

The greatest common divisor of a and b, denoted gcd(a,b) or simply (a,b), is the largest positive integer that divides both a and b.

gcd(a,b)=max(d∈ℤ+:d)

By convention, gcd(a,0)=|a| for any nonzero integer a, since every integer divides 0. The expression gcd(0,0) is typically left undefined or set to 0 by convention.

Examples

The divisors of 12 are {1,2,3,4,6,12}. The divisors of 18 are {1,2,3,6,9,18}. The common divisors are {1,2,3,6}, so gcd(12,18)=6.

For gcd(48,180): The divisors of 48 are {1,2,3,4,6,8,12,16,24,48} and the divisors of 180 are {1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180}. The greatest common divisor is 12.

Coprime Integers

Two integers a and b are called coprime (or relatively prime) if gcd(a,b)=1. This means they share no common factor other than 1.

For example, gcd(15,28)=1 since 15=3⋅5 and 28=2⋅7 share no prime factors. Coprimality is central to modular arithmetic: an integer a has a multiplicative inverse modulo n if and only if gcd(a,n)=1.

Properties of the GCD

The greatest common divisor satisfies several fundamental properties that make it amenable to computation and theoretical analysis.

Basic Properties

For any integers a, b, and c:

Commutativity: gcd(a,b)=gcd(b,a)

Associativity: gcd(a,gcd(b,c))=gcd(gcd(a,b),c)

Absolute values: gcd(a,b)=gcd(|a|,|b|)

Idempotence: gcd(a,a)=|a|

Identity: gcd(a,0)=|a|

The Key Divisibility Property

The property that makes the Euclidean algorithm work is:

gcd(a,b)=gcd(b,a−q*b) for any integer q

In particular, if a=q*b+r (division with remainder), then:

gcd(a,b)=gcd(b,r)

This is because any common divisor of a and b must also divide r=a−q*b and conversely, any common divisor of b and r must divide a=q*b+r Thus the set of common divisors is the same, and so is the greatest one.

GCD and Prime Factorization

If we know the prime factorizations of a and b we can compute the GCD by taking the minimum exponent for each prime:

If a=(p_1)(a_1)*(p_2)(a_2)⋯(p_k)(a_k) and b=(p_1)(b_1)*(p_2)(b_2)⋯(p_k)(b_k) then:

gcd(a,b)=(p_1)min((a_1),(b_1))*(p_2)min((a_2),(b_2))⋯(p_k)min((a_k),(b_k))

For example, 48=2⋅3 and 180=2⋅3⋅5, so
gcd(48,180)=2⋅3⋅5=2⋅3=12.

While this formula is conceptually clear, factoring large integers is computationally hard. The Euclidean algorithm provides a much faster way to compute the GCD without factoring.

The Euclidean Algorithm

The Division Algorithm

The Euclidean algorithm relies on the division algorithm, which states: for any integers a and b with b>0 there exist unique integers q (quotient) and r (remainder) such that:

a=q*b+r*where *0≤r<b

We write r=a*mod(b) for the remainder.

Algorithm Description

To compute gcd(a,b) with a≥b>0 repeatedly apply the key property:

([a,=(q_1)*b+(r_1),0≤(r_1)<b],[b,=(q_2)*(r_1)+(r_2),0≤(r_2)<(r_1)],[(r_1),=(q_3)*(r_2)+(r_3),0≤(r_3)<(r_2)],[,⋮,],[(r_n−2),=(q_n)*(r_n−1)+(r_n),0≤(r_n)<(r_n−1)],[(r_n−1),=(q_n+1)*(r_n)+0,])

The sequence of remainders b>(r_1)>(r_2)>⋯≥0 is strictly decreasing and bounded below by zero, so it must eventually reach zero. The last nonzero remainder (r_n) is the GCD.

gcd(a,b)=gcd(b,(r_1))=gcd((r_1),(r_2))=⋯=gcd((r_n−1),(r_n))=gcd((r_n),0)=(r_n)

Bezouts Identity

One of the most important theoretical results about the GCD is Bezouts identity:

For any integers a and b (not both zero), there exist integers x and y such that:

a*x+b*y=gcd(a,b)

The integers x and y are called Bezout coefficients. They are not unique: if ((x_0),(y_0)) is one solution, then ((x_0)+k*b/d,(y_0)−k*a/d) is also a solution for any integer k where d=gcd(a,b)

Bezouts identity has a powerful corollary: gcd(a,b) is the smallest positive integer that can be expressed as a linear combination a*x+b*y with integer coefficients.

The Extended Euclidean Algorithm

The extended Euclidean algorithm computes not only gcd(a,b) but also the Bezout coefficients x and y The idea is to track how each remainder can be expressed as a linear combination of a and b

We maintain the invariant that at each step i we have (r_i)=a⋅(x_i)+b⋅(y_i). Starting with:

(r_0)=a=a⋅1+b⋅0⇒((x_0),(y_0))=(1,0)

(r_1)=b=a⋅0+b⋅1⇒((x_1),(y_1))=(0,1)

At each step, if (r_i−1)=(q_i)*(r_i)+(r_i+1) then (r_i+1)=(r_i−1)−(q_i)*(r_i) so:

(x_i+1)=(x_i−1)−(q_i)*(x_i),(y_i+1)=(y_i−1)−(q_i)*(y_i)

Applications

Reducing Fractions

To reduce a fraction a/b to lowest terms, divide both numerator and denominator by gcd(a,b)

a/b=(a/gcd(a,b))/(b/gcd(a,b))

The resulting fraction is in lowest terms because the new numerator and denominator are coprime.

Modular Multiplicative Inverse

In modular arithmetic, we often need to find a(−1)*(mod(n)) the multiplicative inverse of a modulo n This inverse exists if and only if gcd(a,n)=1

By Bezouts identity, if gcd(a,n)=1 there exist x and y with a*x+n*y=1 Taking this modulo n

a*x≡1*(mod(n))

So x is the modular inverse. The extended Euclidean algorithm computes it efficiently.

Solving Linear Diophantine Equations

A linear Diophantine equation a*x+b*y=c has integer solutions if and only if gcd(a,b)*(∣_^)(c)

If d=gcd(a,b) divides c use the extended Euclidean algorithm to find (x_0),(y_0) with a*(x_0)+b*(y_0)=d then multiply by c/d to get a particular solution. The general solution is:

x=(x_0)(c/d)+(b/d)*t,y=(y_0)*(c/d)−(a/d)*t for any integer t

Cryptography: RSA

In RSA encryption, we choose two large primes p and q compute n=p*q and ϕ(n)=(p−1)*(q−1) select an encryption exponent e with gcd(e,ϕ(n))=1 and compute the decryption exponent d=e(−1)*(mod(ϕ(n))) using the extended Euclidean algorithm.

The security of RSA relies on the difficulty of factoring n but the extended Euclidean algorithm makes key generation efficient.

Algorithm Complexity

The Euclidean algorithm is remarkably efficient. How many steps does it take to compute gcd(a,b)

Lames Theorem

The number of steps in the Euclidean algorithm never exceeds 5 times the number of digits in the smaller input.

More precisely, if the algorithm takes n steps, then b≥(F_n+1) where (F_k) is the kth Fibonacci number. Since (F_n)≈ϕn/√(,5) where ϕ=(1+√(,5))/2 is the golden ratio, the number of steps is O*((log_)(b))

The worst case occurs when a and b are consecutive Fibonacci numbers. For example, gcd((F_n+1),(F_n)) requires exactly n divisions, each with quotient 1

Bit Complexity

If a and b have at most n bits, the Euclidean algorithm runs in O(n) divisions. Each division of nbit numbers takes O(n2) bit operations with schoolbook arithmetic, giving a total of O(n3) bit operations. More sophisticated analysis shows the algorithm actually runs in O(n2) bit operations.

Relationship with Least Common Multiple

The least common multiple lcm(a,b) is the smallest positive integer divisible by both a and b The GCD and LCM are related by a beautiful formula:

gcd(a,b)⋅lcm(a,b)=|a*b|

This can be understood through prime factorizations: if the GCD takes the minimum exponent for each prime, the LCM takes the maximum. For any prime p with exponents α in a and β in b

min(α,β)+max(α,β)=α+β

This allows us to compute the LCM efficiently using the GCD: lcm(a,b)=|a*b|/gcd(a,b)

Generalizations

The GCD extends naturally to more than two integers:

gcd((a_1),(a_2),…,(a_n))=gcd((a_1),gcd((a_2),…,(a_n)))

The concept also generalizes to other algebraic structures. In polynomial rings, we can define the GCD of polynomials and compute it using the polynomial version of the Euclidean algorithm. In abstract algebra, the GCD is generalized to principal ideal domains.

Connection to Other Concepts

The GCD and Euclidean algorithm connect to many areas of mathematics:

In continued fractions, the quotients (q_1),(q_2),… from the Euclidean algorithm give the continued fraction expansion of a/b

Eulers totient function ϕ(n) counts integers from 1 to n that are coprime to n It is fundamental to Eulers theorem and RSA.

The Chinese Remainder Theorem provides a way to solve systems of congruences, and its proof uses the extended Euclidean algorithm to construct solutions.

In abstract algebra, the integers form a Euclidean domain, and the Euclidean algorithm provides the computational foundation for the theory of principal ideal domains.

Summary

The greatest common divisor gcd(a,b) is the largest positive integer dividing both a and b Two integers are coprime when their GCD is 1

The Euclidean algorithm computes the GCD through repeated division: gcd(a,b)=gcd(b,a*mod(b)) It terminates when the remainder is zero, and the last nonzero remainder is the GCD. The algorithm is efficient, running in O((log_)(min(a,b))) steps.

Bezouts identity states that gcd(a,b) can always be expressed as a*x+b*y for some integers x and y The extended Euclidean algorithm computes these coefficients alongside the GCD.

Applications include reducing fractions to lowest terms, computing modular inverses, solving linear Diophantine equations, and implementing cryptographic systems like RSA. The GCD is also related to the LCM by gcd(a,b)⋅lcm(a,b)=|a*b|

The Euclidean algorithm is one of the oldest algorithms in mathematics, yet it remains fundamental to modern number theory, algebra, and computer science. Its elegance lies in reducing a complex problem to a sequence of simple operations, a principle that echoes throughout mathematics.