GeezerVisonThe World Wide Web, restored to 800 pixels of glory. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Home|About|Gaming cabinet|Archives|How it works|Starter sites | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
GeezerVison is showing mathworld.wolfram.com — Greatest Common Divisor -- from Wolfram MathWorld 
Greatest Common Divisor
The greatest common divisor, sometimes also called the highest common divisor (Hardy and Wright 1979, p. 20), of two positive integers Various notational conventions are summarized in the following table.
The greatest common divisor of 
The plot above shows 
The above plots show a number of visualizations of
If
with
The Euclidean algorithm can be used to find the greatest common divisor of two integers and to find integers
The notion can also be generalized to more general rings than simply the integers
To compute the GCD, write the prime factorizations of
where the
where min denotes the minimum. For example, consider
so
The GCD is distributive
and associative
If
so
and satisfies the absorption law
A recurrence equation that converges to
with
The probability that two integers picked at random are relatively prime is 
Polezzi (1997) observed that
For relatively prime integers
(Graham et al. 1994, p. 147). The case
Polynomial greatest common divisors are computed in the Wolfram Language using PolynomialGCD. See alsoBézout Numbers, Bézout's Theorem, Dirichlet Function, Euclid's Orchard, Euclidean Algorithm, Extended Greatest Common Divisor, Gauss's Lemma, Greatest Common Divisor Theorem, Half-GCD, Least Common Multiple, Least Prime Factor, Orchard-Planting Problem, Polynomial Greatest Common Divisor, Relatively Prime, Star of David Theorem Explore this topic in the MathWorld classroomRelated Wolfram siteshttps://functions.wolfram.com/IntegerFunctions/GCD/Explore with Wolfram|Alpha
ReferencesAndrews, G. E. Number Theory. New York: Dover, 1994.Bressoud, D. M. and Wagon, S. A Course in Computational Number Theory. London, England: Springer-Verlag, 2000.Bronshtein, I. N.; Semendyayev, K. A.; Musiol, G.; and Muehlig, H. Handbook of Mathematics, 5th ed. Berlin, Germany: Springer-Verlag, 2007.D'Angelo, J. P. and West, D. B. Mathematical Thinking: Problem-Solving and Proofs, 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 2000.Gellert, W.; Gottwald, S.; Hellwich, M.; Kästner, H.; and Künstner, H. (Eds.). VNR Concise Encyclopedia of Mathematics, 2nd ed. New York: Van Nostrand Reinhold, 1989.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science. Reading, MA: Addison-Wesley, 1990.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Nagell, T. "Least Common Multiple and Greatest Common Divisor." §5 in Introduction to Number Theory. New York: Wiley, pp. 16-19, 1951.Polezzi, M. "A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor." Amer. Math. Monthly 104, 445-446, 1997.Råde, L. and Westergren, B. Mathematics Handbook for Science and Engineering. Berlin, Germany: Springer-Verlag, 2004.Séroul, R. "The Greatest Common Divisor." §2.4 in Programming for Mathematicians. Berlin, Germany: Springer-Verlag, pp. 9-11, 2000.Stehlé, D. and Zimmerman, P. "A Binary Recursive GCD Algorithm." In Algorithmic Number Theory. Proceedings of the 6th International Symposium (ANTS-VI) Held at the University of Vermont, Burlington, VT, June 13-18, 2004 (Ed. D. Buell). Berlin, Germany: Springer-Verlag, pp. 411-425, 2004.Trott, M. The Mathematica GuideBook for Programming. New York: Springer-Verlag, pp. 25-26, 2004. https://www.mathematicaguidebooks.org/.Yan, S. Y. Number Theory for Computing, 2nd ed. Berlin, Germany: Springer, 2002.Zwillinger, D. (Ed.). "Greatest Common Divisor." §2.3.5 in CRC Standard Mathematical Tables and Formulae, 30th ed. Boca Raton, FL: CRC Press, p. 91, 1996.Referenced on Wolfram|AlphaGreatest Common DivisorCite this as:Weisstein, Eric W. "Greatest Common Divisor." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GreatestCommonDivisor.html Subject classifications | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |
and 
is the largest 
and 
.
,
,
.
can also be defined for three or more positive
integers as the largest divisor shared by all of them. Two or more positive integers
that have greatest common divisor 1 are said to be 
,
,
with rational 
.
is the greatest rational number 
for which all the 
are integers. It is easy to see that if 
,
,
.
is extended by setting it equal to 0 if 
is irrational, the resulting function is continuous at the
irrationals, discontinuous at the rationals, and has Riemann integral equal to 0
over any finite interval.
in the 
-plane. The figure on the left is simply 
,
(Trott 2004, pp. 25-26), and the figure at right
is the absolute value of the transform of 
.
is the greatest common divisor of 
and 
,
is the largest possible integer satisfying
and 
positive integers.
and 
such that
.
,
and 
,
s
are all 
and 
,
does not occur in one factorization, then the corresponding exponent is taken as
0. Then the greatest common divisor 
is given by
.
and 
,
.
for positive odd 
and 
is given by
and 
,
is the 
in 
(Stehlé and Zimmerman 2004). The plot above shows the
number of iterations required to converge for odd 
.![[zeta(2)]^(-1)=6/pi^2](/api/image?u=https%3A%2F%2Fmathworld.wolfram.com%2Fimages%2Fequations%2FGreatestCommonDivisor%2FInline93.svg){kind=small}
,
is the 
,
is the number of 
(excluding 
itself). This observation is intimately connected with the probability of obtaining
,
,
.
.
where the two strings bend give alternating 
of the 
.
and 
and 
,
,
gives
