Explanation:

The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers 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 vectors.

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

Using Euclid's algorithm

A much more efficient method is the Euclidean algorithm, which uses the division algorithm in combination with the observation that the GCD of two numbers also divides their difference: divide 48 by 18 to get a quotient of 2 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the GCD. Formally, it can be described as:

GCD (a, 0) = a

This also could be written as

GCD (a, 0) = a

GCD (a, b) = GCD (b, a mod b).

Specifically, the division algorithm states that given two integers a and b, with b ≠ 0

There exist unique integers q and r such that a = bq + r and 0 ≤ r < |b|, where |b| denotes the absolute value of b (Our solved example in mathguru.com uses this concept).

The integer

1.  q is called the quotient

2.  r is called the remainder

3.  b is called the divisor

4.  a is called the dividend

Euclid's lemma in plain language says: If a number N is a multiple of a prime number p, and N = a · b, then at least one of a and b must be a multiple of p. Say,

,

,

and

.

Then either

or

.

Obviously, in this case, 7 divides 14 (x = 2).

http://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid.27s_algorithm

The above explanation is copied from Wikipedia, the free encyclopedia and is remixed as allowed under the Creative Commons Attribution- ShareAlike 3.0 Unported License.