The greatest common factor (GCF) of several numbers is the largest natural number by which each of these numbers can be divided. The GCF of several numbers is the product of all the common prime factors of these numbers. For example, for the numbers 70 and 105 the greatest common factor is equal to 35. The GCF exists and is uniquely defined, if at least one of the numbers m or n doesn’t equal to zero.
In order to find the GCF of several numbers, you need to do the following:
The main property of the GCF is that the GCF of m and n is divisible by any common divisor of these numbers. For example, for the numbers 12 and 18 the GCF is equal to 6 and it is divided by all these common dividers of these numbers 1, 2, 3, 6.
Corollary 1: the set of common divisors of m and n is the set of divisors GCF (m, n).
Corollary 2: a plurality of common multiples of m and n is the set of the least common multiple LCM (m, n).
If m can be divided by n, then the GCF (m, n) = n. In particular, the GCF (n, n) = n.
If D = (m, n), then after division by D, the numbers are relatively prime, i.e., m/D; n/D = 1. This means, in particular, that in order to bring the fraction to irreducible mean, it is necessary to divide the numerator and denominator by their GCF.
Multiplicativity: if A1and A2 are coprime, then: (A1 x A2, b) = (A1, b) x (A2, b).
The greatest common factor of m and n can be defined as the smallest positive element of the set of all linear combinations of them, and therefore (m, n) can be represented as a linear combination of m and n. This ratio is called Bézout’s identity, and coefficients of u and v are the coefficients of Bézout. Bezout coefficients are effectively calculated with the extended Euclidean algorithm. This statement can be generalized to sets of natural numbers. Its meaning is that the subgroup of Z is cyclic and generated by one element: GCF (a1, a2,..., an).
The concept of divisibility of integers is naturally generalized to arbitrary commutative rings, such as the ring of polynomials, or Gaussian integers. However, it is impossible to determine the GCF (a, b) as the greatest common factor of a, b, as the order relation in these rings, generally speaking, is not defined. Therefore, as the determination of the GCF its basic property is taken: the GCА (a, b) is the common divisor that is divisible by all other common divisors of a and b.
For natural numbers a new definition is equivalent to the old one. For integers, the GCF in the new sense is no longer clear: its opposite number will also be GCF. For the Gaussian numbers, a number of different GCFs increases to 4.
The GCF of two elements of a commutative ring, generally speaking, does not have to exist. In Euclidean rings, the greatest common factor always exists and can be exactly defined up even to a unit, i.e. the number of GCF is equal to the number of divisors of unity in the ring.
The first method is the Euclidean algorithm. The Euclid’s algorithm is a universal method that allows to calculate the greatest common factor of two positive integers. The algorithm is named after the Greek mathematician Euclid, who first described it his book «Elements.» In the simplest case, Euclid’s algorithm is applied to a pair of positive integers, and generates a new pair consisting of a smaller number, and the difference between larger and smaller integer. The process is repeated until the numbers become equal. The obtained number is the greatest common factor of the original pair.
The first description of the algorithm can be found in the «Elements» by Euclid, making it one of the oldest numerical algorithms used in our time. The original algorithm was proposed only for natural numbers and geometric lengths (real numbers). However, in the 19th century it was generalized to other types of numbers, such as Gaussian integers and one variable polynomials. This led to the emergence in the modern general algebra of such notions as a Euclidean ring. Later, Euclid’s algorithm has also been generalized to other mathematical structures such as knots and multivariate polynomials.
There are many theoretical and practical applications for this algorithm. In particular, it is the basis for cryptographic algorithm RSA with the public-key, which is widely distributed in e-commerce. Also, the algorithm is used in solving linear Diophantine equations, in constructing continued fractions, and in the Sturm method. Euclid’s algorithm is the main tool for proving theorems in modern number theory, such as the Lagrange theorem on the sum of four squares and the fundamental theorem of arithmetic.
Ancient Greek mathematicians called this algorithm a «mutual subtraction.» Some scientists say that this algorithm has not been found by Euclid, as it mentions in Aristotle’s works as well. In the Euclid’s books the algorithms is described for finding the greatest common divisor of two integers and for finding the greatest common measure of two homogeneous values. In both cases, the geometrical description of the algorithm for finding the two segments’ «common action» is given.
Historians of mathematics suggested that due to the use of Euclidean algorithm in the Ancient Greek mathematics the existence of incommensurable magnitudes was first discovered (sides and diagonals of the square, or the sides and diagonals of a regular pentagon).
The second method is the Binary Euclidean algorithm. It is a method for finding the greatest common factor of two integers. This algorithm is faster than usual Euclidean algorithm, as instead of slow operations of division and multiplication the changes are used. The algorithm has been known in China in the first century, but was published only in 1967 by the Israeli physicist and programmer Joseph Stein.
This is another method of finding the GCF. The greatest common factor can be found due the expansion of numbers into prime factors. This rule can be formulated as the following: the GCF of two positive integers of A and B is equal to the product of all the common prime factors, which are in the expansions of the numbers of A and B into prime factors.
For example, suppose you know the expansion of numbers 220 and 600 on the prime factors, they are 220 = 2 x 2 x 5 x 11 and 600 = 2 x 2 x 2 x 3 x 5 x 5. The common prime factors involved in the expansion of the numbers 220 and 600 are 2, 2 and 5. Consequently, the GCF (220, 600) = 2 x 2 x 5 = 20.
Thus, if you expand the numbers A and B into prime factors and find the product of their common factors, the greatest common factor of these numbers can be found.
Calculating the greatest common factor of three or more numbers can be reduced to a consistent finding of the GCF of two numbers. There is a rule for that: the GCF of several numbers is equal to the number, which is sequential to computation of GCF (a1, a2) = d2, GCD (d2, a3) = d3, GCD (d3, a4) = d4,..., GCD (dk-1, ak) = dk.
If one or all the numbers, the greatest common factor of which you need to find, are negative numbers, their GCF is equal to the greatest common divisor of modules of these numbers. This is due to the fact that the opposite numbers of A and -A have the same dividers.