本文共 1612 字，大约阅读时间需要 5 分钟。

The Euclidean algorithm calculates the greatest common divisor (GCD) of two  a and b. The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder. Synonyms for the GCD include the greatest common factor (GCF), the highest common factor (HCF), and the greatest common measure (GCM). The greatest common divisor is often written as gcd(a, b) or, more simply, as (a, b), although the latter notation is also used for other mathematical concepts, such as two-dimensional .

If gcd(a, b) = 1, then a and b are said to be  (or relatively prime). This property does not imply that a or b are themselves . For example, neither 6 nor 35 is a prime number, since they both have two prime factors: 6 = 2 × 3 and 35 = 5 × 7. Nevertheless, 6 and 35 are coprime. No natural number other than 1 divides both 6 and 35, since they have no prime factors in common.

Let g = gcd(a, b). Since a and b are both multiples of g, they can be written a = mg and b = ng, and there is no larger number G > g for which this is true. The natural numbers m and n must be coprime, since any common factor could be factored out of m and n to make g greater. Thus, any other number c that divides both a and bmust also divide g. The greatest common divisor g of a and b is the unique (positive) common divisor of a and bthat is divisible by any other common divisor c.

转载地址：http://flhbi.baihongyu.com/