## Euclid’s Division Lemma

Given positive integers a and b there exist unique integers q and r which satisfies the equation a= bq+r, 0 ≤ r < b.

Euclid’s division algorithm is based on this lemma

**Note:**

An algorithm is a procedure which has a series of well defined steps for solving a given problem

Euclid’s division algorithm is a method used to find out the Highest Common Factor (HCF) of two given positive integers.

Recall that the HCF of two given positive integers a and b is the largest integer d which divides both a and b.

Now let us take an example to check how this algorithm works.

**Example:**

Find the HCF of the integers 455 and 42

**Solution:**

we will apply the Euclid’s Division Algorithm to compute the HCF

Initially we need to consider the larger integer, in this problem the larger integer is 455.

Then we use the Euclid’s Lemma to obtain

455= 42*10+35

Now consider the divisor 42 and the remainder 35, and apply the lemma again to obtain

42= 35*1+7

Now consider the divisor 35 and the remainder 7, and apply the lemma again to obtain

35=7*5+0

Here we see that the remainder becomes zero and so we need not proceed further.

We conclude that the HCF of 422 and 45 is 7.

We can verify this by listing out the factors of 455 and 42 and we see that the HCF of the given numbers to be 7.

**Euclid’s Division Algorithm:**

To obtain the HCF of two positive integers say a and b, where a > b, follow the steps given below

**Step 1: **Apply the Euclid’s division lemma to the integers a and b. So we find the whole numbers c and d such that a= bc+d, 0 ≤ d <b.

**Step 2:** If d=0, d is the HCF of the given integers. If d 0, we need apply the division lemma to b and d.

**Step 3: **Continue the same procedure till the remainder becomes zero. The divisor at this stage is the required HCF.

Note: This algorithm works because HCF ( a,b) = HCF (c,d) where the symbol HCF(a,b) denotes the HCF of a and b.

**EXAMPLE:**

Use Euclid’s Algorithm to find the HCF of 867 and 255

**Solution:**

**Step 1**: Here we see that 867> 255, So we apply the division lemma to 865 and 255 to obtain

867= 255*3+102

**Step 2:** Now the remainder 2550, we again apply the division lemma to the integers 255 and 102 to obtain

255= 102*2+51

**Step 3:** Now we consider the new divisor 102 and the remainder 51, and again apply the division lemma

102=51*2+0

We see that the remainder is zero now, so we stop at this stage. Since the divisor at this stage is 51, we conclude by saying that the HCF of 867 and 255 is 51.

Note that 51= HCF ( 102,51)= HCF (255,102) = HCF ( 867,255).

**NOTE:** Euclid’s division algorithm is not only useful for computing the HCF of large numbers but it is one of the oldest algorithm that the computer had been programmed to carry out.

Dear christina kindly show as many examples as possible on Euclid’s Lemma

Dear christina kindly show as many examples as possible on Euclid’s Lemma

Was die Formen betrifft, gibt es sowohl Shirts mit Rundhals als auch Ausführungen mit V-Ausschnitt.