(Redirected from GCD)
![Pending changes are displayed on this page Pending changes are displayed on this page](/w/extensions/FlaggedRevs/frontend/modules/img/1.png)
There are no approved revisions of this page, so it may
not have been
reviewed.
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
, 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 = pj α j (mi ), 1 ≤ i ≤ n, |
where
is the
number of primes up to
, and
is the
th prime number, we have
-
gcd (m1, ..., mn ) = pj min (α j (m1), ..., α j (mn )) |
and
-
lcm (m1, ..., mn ) = 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 and
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
corresponds to the bag (multiset) intersection of the two bags of
prime factors (with multiplicity), while
corresponds to the bag (multiset) union (which amounts to bag addition, here performed multiplicatively as
, minus bag intersection, here performed multiplicatively via division by
) 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)
-
mi = max (m1, ..., mn ) + {[ min (mi, mj )] − [ min (mi, mj, mk )] + ⋯ + (−1) n min (m1, ..., mn )}, m1 ≤ ⋯ ≤ mn , |
we then have
-
lcm (m1, ..., mn ) ⋅ {[ gcd (mi, mj )] ⋅ [ gcd (mi, mj, mk )] − 1 ⋅ ⋯ ⋅ [gcd (m1, ..., mn )] ( − 1) n}, mi ≠ 0. |
Series representations
-
gcd (m, n) = m + n − m n + + = |
m + n − m n + 2 = m + n − m n + 2 , |
-
gcd (m, n) = 1 − 2 − [ = ] ⋅ [ = ] + |
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
“near” multiples
of some unknown positive integer
, 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
, without the knowledge of any
and
.
Notes