This site is supported by donations to The OEIS Foundation.

Greatest common divisor

From OeisWiki
(Redirected from Gcd)
Jump to: navigation, search


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.[1]

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), 1in,
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), mn,
then the least common multiple (LCM) of two nonzero integers
m
and
n
is related to their greatest common divisor (GCD) by
| mn |
 =  lcm (m, n)  ⋅  gcd (m, n), mn ≠ 0,

where the GCD may be obtained via the Euclidean algorithm.

The above formula results from the fact that
gcd (mn)
corresponds to the bag (multiset) intersection of the two bags of prime factors (with multiplicity), while
lcm (mn)
corresponds to the bag (multiset) union (which amounts to bag addition, here performed multiplicatively as
mn
, minus bag intersection, here performed multiplicatively via division by
gcd (mn)
) 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 )}, m1m2m3,

we then have

| m1m2m3 |
 =  lcm (m1, m2, m3 )   ⋅  {
gcd (m1, m2 ) gcd (m1, m3 ) gcd(m2, m3 )
gcd (m1, m2, m3 )
}, m1m2m3 ≠ 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 )}, m1mn ,

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 + nmn +
m − 1
k  = 1
  
k  n
m
+
n − 1
k  = 1
  
k  m
n
 = 
m + nmn + 2
m − 1
k  = 1
  
k  n
m
 =  m + nmn + 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
.

Notes

  1. Greatest common divisor, www.mathworks.com