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).
Statement of theorem
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.