Gcd Lcm

Definition

Greatest Common Divisor (GCD)

Definition: For integers a, b (not both zero), gcd(a,b) is the largest positive integer dividing both a and b without remainder.

Notation: gcd(a,b) or (a,b).

Least Common Multiple (LCM)

Definition: For integers a, b (nonzero), lcm(a,b) is the smallest positive integer divisible by both a and b.

Notation: lcm(a,b).

Existence and Uniqueness

Existence: Guaranteed by well-ordering principle of integers.

Uniqueness: GCD and LCM are unique positive integers for given inputs.

Basic Properties

Properties of GCD

Symmetry: gcd(a,b) = gcd(b,a).

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

Divisibility: gcd(a,b) divides both a and b.

Properties of LCM

Symmetry: lcm(a,b) = lcm(b,a).

Associativity: lcm(a, lcm(b,c)) = lcm(lcm(a,b), c).

Multiples: Both a and b divide lcm(a,b).

Bounds and Inequalities

Lower bound: gcd(a,b) ≤ min(|a|,|b|).

Upper bound: lcm(a,b) ≥ max(|a|,|b|).

Relation: gcd(a,b) × lcm(a,b) ≥ |a×b|.

Euclidean Algorithm

Algorithm Description

Input: integers a, b with b ≠ 0.

Process: repeatedly replace (a,b) with (b, a mod b) until remainder is zero.

Output: last nonzero remainder is gcd(a,b).

Example Computation

Compute gcd(252, 105):

252 = 105 × 2 + 42105 = 42 × 2 + 2142 = 21 × 2 + 0gcd = 21

Complexity

Time complexity: O(log min(a,b)) in worst case.

Efficiency: optimal for large integers.

Prime Factorization Method

Prime Factorization Definition

Expression of integer as product of primes raised to powers.

Uniqueness: Fundamental Theorem of Arithmetic guarantees unique factorization.

GCD via Prime Factors

Take minimum exponent of each prime factor common to both numbers.

LCM via Prime Factors

Take maximum exponent of each prime factor appearing in either number.

Example

36 = 2^2 × 3^248 = 2^4 × 3^1gcd(36,48) = 2^2 × 3^1 = 12lcm(36,48) = 2^4 × 3^2 = 144

Relationship Between GCD and LCM

Fundamental Identity

For integers a,b ≠ 0:

gcd(a,b) × lcm(a,b) = |a × b|

Proof Outline

Use prime factorization: product of min and max exponents equals sum of exponents.

Consequences

Efficient computation of one quantity given the other and the inputs.

Applications in solving Diophantine equations and modular arithmetic.

Applications

Number Theory

Simplification of fractions, solving linear Diophantine equations.

Cryptography

Key generation algorithms require gcd computations for coprimality checks.

Computer Science

Scheduling problems, resource allocation, and hashing algorithms.

Engineering

Signal processing: synchronization periods involve lcm calculations.

Mathematical Puzzles

Common divisor and multiple problems in competitions and recreational math.

Algorithms for Computation

Euclidean Algorithm Variants

Standard, Extended Euclidean Algorithm computes gcd and Bézout coefficients.

Binary GCD Algorithm

Uses bitwise operations; faster on binary computers.

Prime Factorization Method

Impractical for large numbers due to factorization complexity.

Algorithm Complexity

Binary GCD: O(log n) with low constant factors.

Implementation Considerations

Handling negative inputs, zero, and large integers in arbitrary precision libraries.

Generalizations and Extensions

Multiple Integers

GCD and LCM defined for more than two integers via associative properties.

Polynomials

GCD and LCM definitions extend to polynomial rings over fields.

Algebraic Structures

GCD domains and unique factorization domains provide frameworks for gcd-like concepts.

Functions on Integers

Arithmetic functions such as Möbius and Euler’s totient relate to gcd properties.

Matrix GCD and LCM

Extensions to matrices over integers via Smith normal form.

Divisibility Rules

Basic Divisibility Criteria

Rules for divisibility by small integers (2,3,5,7,11).

Relation to GCD

Divisibility rules help determine gcd by checking common divisors.

Modular Arithmetic

Residue classes facilitate gcd computations via congruences.

Applications

Quick factor checks, simplifying large integer problems.

Limitations

Rules become complex for large primes or composite numbers.

GCD and LCM in Rings

Integral Domains

Definition and conditions for gcd existence in integral domains.

Principal Ideal Domains (PIDs)

Every ideal generated by a single element; gcd corresponds to generator of sum of ideals.

Unique Factorization Domains (UFDs)

GCD exists and is unique up to units.

Non-UFD Rings

GCD may not exist or be unique.

LCM in Rings

Defined via intersection of ideals; existence depends on ring properties.

Complexity Analysis

Euclidean Algorithm Complexity

Worst case: Fibonacci numbers input; O(log min(a,b)).

Binary GCD Algorithm

Improved practical efficiency; uses shifts and subtraction.

Prime Factorization

Exponential time; impractical for large integers.

Extended Euclidean Algorithm

Similar complexity to standard Euclidean; computes coefficients.

Space Complexity

Linear in number of digits; depends on implementation.

Examples

Example 1: GCD and LCM of 48 and 180

Prime factorization:

48 = 2^4 × 3^1180 = 2^2 × 3^2 × 5^1gcd = 2^2 × 3^1 = 12lcm = 2^4 × 3^2 × 5^1 = 720

Example 2: Using Euclidean Algorithm

Compute gcd(270,192):

270 = 192 × 1 + 78192 = 78 × 2 + 3678 = 36 × 2 + 636 = 6 × 6 + 0gcd = 6

Example 3: GCD and LCM with Negative Integers

gcd(-24, 36) = gcd(24,36) = 12.

lcm(-24, 36) = lcm(24,36) = 72.

Summary Table

References

• Hardy, G.H., Wright, E.M. - An Introduction to the Theory of Numbers - Oxford University Press, 2008, pp. 15-35.
• Rosen, K.H. - Elementary Number Theory and Its Applications - Pearson, 2011, pp. 45-62.
• Knuth, D.E. - The Art of Computer Programming, Volume 2: Seminumerical Algorithms - Addison-Wesley, 1997, pp. 3-29.
• Bach, E., Shallit, J. - Algorithmic Number Theory, Volume 1: Efficient Algorithms - MIT Press, 1996, pp. 20-55.
• Niven, I., Zuckerman, H.S., Montgomery, H.L. - An Introduction to the Theory of Numbers - Wiley, 1991, pp. 40-67.