I leaned this when doing a leetcode daily challenge – 3116. Kth Smallest Amount With Single Denomination Combination

GCD

GCD stands for Greatest Common Divisor.
Provided two integers a and b, for each operation,
replace (a, b) with (b, a % b) until b is 0.
At that point, a is the GCD.

Example

1. [60, 36] a= 60, b= 36, a % b = 24
2. [36, 24] a= 36, b= 24, a % b = 12
3. [24, 12] a= 24, b= 12, a % b = 0
4. [12, 0] a= 12, b= 0, return 12

Recursive version:

def gcd(a: int, b: int) -> int:
    if b == 0:
      return a
    return gcd(b, a % b)

Complexity:
Time: O(log(min(a, b)))
Space: O(log(min(a, b)))

Iterative version:

def gcd(a: int, b: int) -> int:
    while b:
      a, b = b, a % b
    return a

Complexity:
Time: O(log(min(a, b)))
Space: O(1)

LCM

LCM stands for Least Common Multiple.
Provided two integer a and b,
LCM is just a * b / GCD(a, b).

Example

From the GCD example above,
we know that
gcd(60, 36)= 12
60= 5 * 12
36= 3 * 12
LCM= 3 * 5 * 12= 3 * 5 * GCD= a * b / GCD

def lcm(a, b): 
    x, y = a, b

    # Calculate greatest common divisor(gcd),
    while y:
        x, y = y, x % y

    # Return least common multiple(lcm),
    # Note that we use a // x * b
    # because (a * b // x)'s (a * b) might overflow
    return a // x * b

We could just use the gcd function above inside lcm function.

def lcm(a, b): 
    # Calculate greatest common divisor(gcd),
    def gcd(x, y) -> int:
        while y:
            x, y = y, x % y
        return x
    return a // gcd(a, b) * b

For the return a // gcd(a, b) * b code in lcm(a, b),
we can identify a relationship:
gcd(a, b) * lcm(a, b) = a * b

Use Case

GCD and LCM can both be used in cryptography.