Chapter 1 · Question 1

State Euclid's division lemma and explain how it is used to find the HCF of two positive integers.

Answer

Euclid's division lemma says that for positive integers

a

and

b

, there exist unique integers

q

and

r

such that

a=bq+r

, where

0\le r<b

. Repeated use of this relation gives Euclid's division algorithm for finding HCF.

Use the larger number as

a

and the smaller as

b

. Divide, replace the pair by divisor and remainder, and repeat until the remainder is zero. The last non-zero divisor is the HCF.

1. Write

a=bq+r

,

0\le r<b

. 2. If

r=0

, then

b

is the HCF. 3. If

r\ne0

, repeat the same process with

b

and

r

. 4. Continue until the remainder becomes zero. The last non-zero remainder/divisor is the HCF. This works because the common divisors of

a

and

b

are the same as the common divisors of

b

and

r

.

Euclid's division lemma says that for positive integers $a$ and $b$ , there exist unique integers $q$ and $r$ such that $a=bq+r$ , where $0\le r<b$ .