| 释义 |
Greatest Common DivisorThe greatest common divisor of  and  GCD( ), sometimes written  , is the largest Divisor common to and . Symbolically, let
Then the greatest common divisor is given by
 | (3) |
 | (4) |
 | (5) |
 | (6) |
 | (7) |
If  and  , then
 | (8) |
 and  and  are said to be Relatively Prime. The GCD is also Idempotent
 | (9) |
 | (10) |
 | (11) |
The probability that two Integers picked at random are Relatively Prime is  ,where  is the Riemann Zeta Function. Polezzi (1997) observed that  , where  is the number ofLattice Points in the Plane on the straight Line connecting theVectors (0, 0) and  (excluding itself). This observation is intimately connected with theprobability of obtaining Relatively Prime integers, and also with the geometric interpretation of a ReducedFraction  as a string through a Lattice of points with ends at (1,0) and  . The pegs it presses against give alternate Convergents  of the Continued Fraction for , while theother Convergents are obtained from the pegs it presses against with the initial end at (0, 1).
Knuth showed that
 | (12) |
The extended greatest common divisor of two Integers  and  can be defined as the greatest commondivisor of and which also satisfies the constraint  for  and  given Integers. It isused in solving Linear Diophantine Equations. See also Bezout Numbers, Euclidean Algorithm, Least Prime Factor
References
Polezzi, M. ``A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor.'' Amer. Math. Monthly 104, 445-446, 1997. |
