Skip to main content

GCD / LCM

GCD​

Greatest Common Divisor (GCD) of two integers A and B is the largest integer that divides both A and B.

Synonyms​

  1. Greatest Common Divisor (GCD)
  2. Greatest Common Factor (GCF)
  3. Highest Common Factor (HCF)
  4. Highest Common Divisor (HCD)
  5. Greatest Common Measure (GCM)

Codes​

# using internal math library
import math
print(math.gcd(3, 6))
# Changed in version 3.9: Added support for an arbitrary number of arguments. Formerly, only two arguments were supported.

gcd = lambda a, b: gcd(b, a % b) if b > 0 else a
print(gcd(10, 7))

Python math.gcd() Method

Euclidean Algorithm​

The Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor of two numbers.

def gcd(x, y):

 while (y):
  x, y = y, x%y

 return x

Applications​

  1. Reducing fractions to their simplest form
  2. Performing division in modular arithmetic
  3. Computations using this algorithm form part of the cryptographic protocols that are used to secure internet communications
  4. Also used for breaking cryptosystems by factoring large composite numbers
  5. Solve Diophantine equations, such as finding numbers that satisfy multiple congruences according to the Chinese remainder theorem
  6. To construct continued fractions
  7. To find accurate rational approximations to real numbers
  8. Proving theorems such as Lagrange's four square theorem and uniqueness of prime factorizations

gcd() in Python - GeeksforGeeks

LCM​

LCM (Least Common Multiple) of two numbers is the smallest number which can be divided by both numbers.

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. However, some authors define lcm(a, 0) as 0 for all a, since 0 is the only common multiple of a and 0.

The least common multiple of the denominators of two fractions is the "lowest common denominator" (lcd), and can be used for adding, subtracting or comparing the fractions.

The least common multiple of more than two integers a, b, c, . . . , usually denoted by lcm(a, b, c, . . .), is defined as the smallest positive integer that is divisible by each of a, b, c, . . .

Least common multiple - Wikipedia

Codes​

# using internal math library
import math
math.lcm(6,9,10)

# using gcd
def lcm(a,b):
 return (a // gcd(a,b))* b

Program to find LCM of two numbers - GeeksforGeeks

Mathematical Algorithms | GCD & LCM - GeeksforGeeks