If you like what you see in Mathguru
Subscribe Today
 For 12 Months US Dollars 12 / Indian Rupees 600 Available in 20 more currencies if you pay with PayPal. Buy Now No questions asked full moneyback guarantee within 7 days of purchase, in case of Visa and Mastercard payment

Example:Finding Highest Common Factor(HCF) using Euclids Division Lemma

 Post to:

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 (ab) or, more simply, as (ab), 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`