Greatest common divisor

This article page is a stub, please help by expanding it.

The greatest common divisor (GCD as abbreviation in the OEIS, but not in mathematical formulae; usually gcd in the literature; sometimes known as the highest common factor, HCF or hcf) of two or more integers is the largest positive integer that is a common divisor of all those numbers, i.e. that divides (gives an integer quotient with 0 as remainder) all those numbers. For example, gcd (144, 2988, 37116) = 36, since 36 evenly divides 144, 2988 and 37116 and there is no greater common divisor for those numbers.

When

gcd (m, n) = 1

, the numbers are said to be coprime or relatively prime, such as for example gcd (128, 11025) = 1. Note that gcd (1, 1) = 1, which means that 1 is coprime with itself, i.e. it shares no prime factors with itself, since 1 is the empty product.

gcd (0, n) = | n | = gcd (n, 0)

. In particular gcd (0, 0) = 0; essentially 0 acts as the top element (⊤ or ∞) in this and other contexts.

GCD and LCM in terms of the prime factorization

From the prime factorization of

mi , 1   ≤   i   ≤   n,

mi  =    π (max (m1, ..., mn )) ∏   j  = 1    pj α j (mi ), 1 ≤ i ≤ n,

where

π (m)

is the number of primes up to

m

, and

pj

is the

j

th prime number, we have

gcd (m1, ..., mn )  =    π (max (m1, ..., mn )) ∏   j  = 1    pj min (α j (m1), ..., α j (mn ))

and

lcm (m1, ..., mn )  =    π (max (m1, ..., mn )) ∏   j  = 1    pj max (α j (m1), ..., α j (mn ))

Formulae

Formulae relating LCM to GCD

Since

m + n  =  max (m, n) + min (m, n), m ≤ n,

then the least common multiple (LCM) of two nonzero integers

m

and

n

is related to their greatest common divisor (GCD) by

| m n |  =  lcm (m, n)  ⋅  gcd (m, n), m n ≠ 0,

where the GCD may be obtained via the Euclidean algorithm.

The above formula results from the fact that

gcd (m n)

corresponds to the bag (multiset) intersection of the two bags of prime factors (with multiplicity), while

lcm (m n)

corresponds to the bag (multiset) union (which amounts to bag addition, here performed multiplicatively as

m n

, minus bag intersection, here performed multiplicatively via division by

gcd (m n)

) of the two bags of prime factors (with multiplicity).

Since (using the inclusion-exclusion principle)

m1 + m2 + m3  =  max (m1, m2, m3 ) + {[min (m1, m2 ) + min (m1, m3 ) + min (m2, m3 )] − min (m1, m2, m3 )}, m1 ≤ m2 ≤ m3,

we then have

| m1 m2 m3 |  =  lcm (m1, m2, m3 )   ⋅  { gcd (m1, m2 ) gcd (m1, m3 ) gcd(m2, m3 ) gcd (m1, m2, m3 ) }, m1 m2 m3 ≠ 0.

Finally, since (using the inclusion-exclusion principle)

n ∑   i  = 1    mi  =  max (m1, ..., mn )  + {[    1  ≤  i  <  j  ≤  n ∑   1  ≤  i  <  j  ≤  n    min (mi, mj )] − [    1  ≤  i  <  j  <  k  ≤  n ∑   1  ≤  i  <  j  <  k  ≤  n    min (mi, mj, mk )] +  ⋯  + (−1) n min (m1, ..., mn )}, m1 ≤ ⋯ ≤ mn ,

we then have

n ∏   i  = 1    mi  =

lcm (m1, ..., mn )  ⋅  {[    1  ≤  i  <  j  ≤  n ∏   1  ≤  i  <  j  ≤  n    gcd (mi, mj )] ⋅  [    1  ≤  i  <  j  <  k  ≤  n ∏   1  ≤  i  <  j  <  k  ≤  n    gcd (mi, mj, mk )]   − 1  ⋅   ⋯  ⋅   [gcd (m1, ..., mn )] ( − 1) n},    n ∏   i  = 1    mi ≠ 0.

Series representations

gcd (m, n)  =  m + n − m n +   m − 1 ∑   k  = 1    k  n m +   n − 1 ∑   k  = 1    k  m n  =

m + n − m n + 2   m − 1 ∑   k  = 1    k  n m  =  m + n − m n + 2   n − 1 ∑   k  = 1    k  m n ,

gcd (m, n)  =  1 − 2 m 2 n 2 − [ m 2 = m 2 ]  ⋅  [ n 2 = n 2 ] +

2   ⌊  m / 2⌋ ∑   k  = 1    k  n m + 2   ⌊  n / 2⌋ ∑   k  = 1    k  m n ,

where [·] is the Iverson bracket and

⌊ ·⌋

is the floor function.

Algorithms

Euclidean algorithm

The GCD of two positive integers is efficiently obtained with the Euclidean algorithm.

Approximate GCD problem

In the approximate GCD problem you are given

n

“near” multiples

{m1, m2, ..., mn}

of some unknown positive integer

p

, i.e.

     

m1  =  p ⋅  q1 + r1, 0 ≤  r1 < p, m2  =  p ⋅  q2 + r2 , 0 ≤  r2 < p, ... , mn  =  p ⋅  qn + rn , 0 ≤  rn < p,

and you need to find out

p

, without the knowledge of any

qi

and

ri

.