Home | About Mathguru | Advertisements | Teacher Zone | FAQs | Contact Us | Login

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 Euclid`s Division Lemma

Post to:

Bookmark and Share


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.




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,





Then either



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




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.