Euclid’s algorithm (Euclidean algorithm)

In mathematics, the Euclidean algorithm[a] (also called Euclid’s algorithm) is an efficient method for computing the greatest common divisor(GCD) of two integers, also known as the greatest common factor (GCF) or highest common factor (HCF). It is named after the Greekmathematician Euclid, who described it in Books VII and X of his Elements.[1]

The earliest surviving description of the Euclidean algorithm is in Euclid’s Elements (c. 300 BC), making it one of the oldest numericalalgorithms still in common use. The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials in one variable. This led to modern abstract algebraic notions such as Euclidean domains. The Euclidean algorithm has been generalized further to other mathematical structures, such as knots and multivariate polynomials.

The algorithm has many theoretical and practical applications. It may be used to generate almost all the most important traditional musical rhythms used in different cultures throughout the world.[2] It is a key element of the RSA algorithm, a public-key encryption method widely used in electronic commerce. It is used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences (Chinese remainder theorem) or multiplicative inverses of a finite field. It can also be used to construct continued fractions, in the Sturm chain method for finding real roots of a polynomial, and in several modern integer factorization algorithms. Finally, it is a basic tool for proving theorems in modernnumber theory, such as Lagrange’s four-square theorem and the fundamental theorem of arithmetic (unique factorization).

If implemented using remainders of long division rather than subtractions, Euclid’s algorithm computes the GCD of large numbers efficiently: it never requires more division steps than five times the number of digits (base 10) of the smaller integer. This was proved by Gabriel Lamé in 1844, and marks the beginning of computational complexity theory. Methods for improving the algorithm’s efficiency were developed in the 20th century.

The GCD of two numbers is the largest number that divides both of them without leaving a remainder. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the smaller number is subtracted from the larger number. For example, 21 is the GCD of 252 and 105 (252 = 21 × 12; 105 = 21 × 5); since 252 − 105 = 147, the GCD of 147 and 105 is also 21.

Since the larger of the two numbers is reduced, repeating this process gives successively smaller numbers until one of them is zero. When that occurs, the GCD is the remaining nonzero number. By reversing the steps in the Euclidean algorithm, the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., 21 = [5 × 105] + [(−2) × 252]. This important property is known as Bézout’s identity.

 

Reference : http://en.wikipedia.org/wiki/Euclidean_algorithm

Advertisements

Find the greatest common factor (GCD)

I assume you mean the greatest common divisor of integers a and b, 
the largest integer that divides both of a and b.  It can be 
calculated using a 2300 year old method called Euclid's algorithm.

I'll explain the algorithm with an example.  Let's find the gcd of 
210 and 990.

Divide 990 by 210:  quotient 4, remainder 150; ignore quotient
Divide divisor from previous step by remainder from previous step
   divide 210 by 150: quotient 1, remainder 60; ignore quotient
Divide divisor from previous step by remainder from previous step
   divide 150 by 60: quotient 2, remainder 30; ignore quotient
Divide divisor from previous step by remainder from previous step
   divide 60 by 30: quotient 2, remainder 0.

When the remainder becomes 0, as it always will, then go to the 
previous step and choose the remainder, in this case 30.  This is the 
gcd!  Neat!

The step of dividing and ignoring the quotient can be done on many 
calculators, using the MOD operation.  For example, on my calculator 
(an HP48G), I enter 990 and 210 and press MOD.  I get 150 on the 
screen.

-Doctor Jerry,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   
Reference : http://mathforum.org/library/drmath/view/58554.html