gcd-lcm

GCD and LCM

If c divides both a and b, then it is their common divisor. The largest such number is their greatest common divisor, gcd(a, b).

Get GCD of 2 ints by mult their common prime factors. For example: 140=2257 and 650=25513, so gcd(140, 6500) = 2*5 = 2

Common multiple of a and b is c such that a|c and b|c. The least common multiple is the smallest positive number for which this is true.

Computable with: lcm(a,b) = a*b / gcd(a,b)

If two ints a and b share no common factor, then gcd(a,b)=1. Such pair is called relatively prime.

• if int k > 0, then k | 0

• gcd(k,0) = gcd(0,k) = k

• gcd(0,0) is not defined since all ints are common divisors of 0 and 0, so there is no greatest one.

Greatest Common Divisor

Greatest common divisor (GCD)

• domain: Integers $\mathbb{Z}$

  A simple calculator to determine the greatest common divisor of any two regular integers.

gcd(a,b)=\deltagcd(a,b)=δ $\mathbb{N}$