Euclid's Division Algorithm & Lemma and find HCF

As the name implies, Euclid's division algorithm is involved with the divisibility of integers.

Euclid's division algorithm is a technique for calculating the HCF of two numbers using Euclid's division lemma.

[{"selector":"#anim-8a7254e2-386a-4aa9-89f2-8e2201c60ff2","keyframes":{"transform":["translate3d(-125.73529%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"both"}] [{"selector":"#anim-983076be-da1b-4fca-bdd5-33f9b3982317","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"both"}] [{"selector":"#anim-e8ecf891-fe6b-43f9-83a9-6a66f03bbfd1","keyframes":{"transform":["scale(0.15)","scale(1)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"forwards"}] Books

According to Euclid’s Division Lemma ( or Theorem), "Any positive integer 'a' can be divided by another positive integer 'b' in such a way that a remainder 'r' is less than 'b'."

[{"selector":"#anim-b0ac0936-1db1-4a40-b222-39a915cef770","keyframes":[{"transform":"scale(1)","offset":0},{"transform":"scale(1.5)","offset":0.33},{"transform":"scale(0.95)","offset":0.66},{"transform":"scale(1)","offset":1}],"delay":0,"duration":1450,"easing":"ease-in-out","fill":"both","iterations":1}] [{"selector":"#anim-0a44c534-15d5-40d6-b2c5-ab8a1f5ae32a","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-14bce847-38db-40e7-8cc4-13bdc4accabb","keyframes":{"transform":["translate3d(-126.47059%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] Books

In other words, Euclid’s Division Lemma states that, "For any given two positive integers 'a' and 'b', there exist unique integers 'q' and 'r' satisfying the condition: a = bq + r, where 0 ≤ r < b."

[{"selector":"#anim-047aa2f9-5788-4c0c-9f0b-503e87a105d5","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-36b6ad24-406e-41c8-8d4f-46b362809d62","keyframes":{"transform":["translate3d(-119.25675%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] Books

Here, integer 'a' is the dividend, 'b' is the divisor, 'q' is the quotient and 'r' is the remainder, and 'q' or 'r' can also be zero.

[{"selector":"#anim-0a437323-7eb2-4460-8fe3-ece6df5b522a","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-636b519c-dfde-42f0-ae3f-ba3eb7a81634","keyframes":{"transform":["translate3d(-119.25675%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] Books

So, the above condition: a = b q + r ; can be expressed mathematically as: Dividend = Divisor × Quotient + Remainder It is called the Formula of the Euclid Division Algorithm.

Example: Consider the pair of integers: 29, 3. If we divide a=29 by b=3, then we get the quotient as q=9 and the remainder as r=2, as shown follows:

Similarly, we can write the following relations: Dividend = Divisor × Quotient + Remainder; for each such pair: (i) For the pair: 17, 6: 17 = 6 × 2 + 5 (ii) For the pair: 5, 15: 5 = 15 × 0 + 5 (iii) For the pair: 24, 4: 24 = 4 × 6 + 0

Apply the following steps to find the HCF of two positive integers, say a and b, with a > b using Euclid's division algorithm: --->

Apply Euclid’s division lemma to a and b, to find whole numbers, q and r such that a = bq + r, where 0 ≤ r < b

If r = 0, then the HCF of a and b is, b. If r ≠ 0, apply the Euclid’s division lemma to b and r.

Repeat the process until the remainder is zero. At this stage, the divisor will be the required HCF.

This algorithm works because HCF (a, b) = HCF (b, r). The symbol HCF (a, b) denotes the HCF of a and b, etc.

Solution: Apply the steps below to find HCF --->

Step 1: Since 36 > 24, apply the division lemma to 36 and 24, to get 36 = 24 × 1 + 12 Step 2: Since the remainder 12 ≠ 0, again apply the division lemma to divisor 24 and remainder 12, to get 24 = 12 × 2 + 0 The remainder has now become zero, so stop this process. Since the divisor at this stage is 12, the HCF of 36 and 24 is 12.

There are many applications of Euclid’s division lemma/algorithm related to finding properties of numbers. Here are some examples of these applications:

1. Every positive even integer 'm' has the form '2n', where n is an integer. 2. Every positive odd integer 'm' has the form '2n+1', where n is an integer.

Read All Topics of Math & Statistics in Details in Hindi & English

[{"selector":"#anim-a324785e-ed9b-4788-a38e-89e70bb7f33f","keyframes":{"opacity":[0,1]},"delay":0,"duration":1500,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-aecede95-7f5e-4a14-88fb-dee2e066f39f","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":1500,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-d5336321-c408-4a83-b3cb-ce813043f8c0","keyframes":{"opacity":[0,1]},"delay":500,"duration":1500,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-3b0582d4-660c-4b13-ae49-317d0ce6fcd0","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":500,"duration":1500,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-f915221d-a355-4dd8-8b1f-0bfde242c4c0","keyframes":{"opacity":[0,1]},"delay":0,"duration":2500,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"both"}] [{"selector":"#anim-6fd4a835-5416-4a70-9e11-0a44933fb193","keyframes":{"opacity":[0,1]},"delay":500,"duration":2500,"easing":"cubic-bezier(0.4, 0.4, 0.0, 1)","fill":"both"}] Floral Pattern Floral Pattern

As the name implies, Euclid's division algorithm is involved with the divisibility of integers.

Euclid's Division Algorithm

Euclid's division algorithm is a technique for calculating the HCF of two numbers using Euclid's division lemma.

Euclid's Division Algorithm

According to Euclid’s Division Lemma ( or Theorem), "Any positive integer 'a' can be divided by another positive integer 'b' in such a way that a remainder 'r' is less than 'b'."

Euclid’s Division Lemma

In other words, Euclid’s Division Lemma states that, "For any given two positive integers 'a' and 'b', there exist unique integers 'q' and 'r' satisfying the condition: a = bq + r, where 0 ≤ r < b."

Euclid’s Division Lemma

Here, integer 'a' is the dividend, 'b' is the divisor, 'q' is the quotient and 'r' is the remainder, and 'q' or 'r' can also be zero.

Euclid’s Division Lemma

So, the above condition: a = b q + r ; can be expressed mathematically as: Dividend = Divisor × Quotient + Remainder It is called the Formula of the Euclid Division Algorithm.

Formula of the Euclid Division Algorithm

Example: Consider the pair of integers: 29, 3. If we divide a=29 by b=3, then we get the quotient as q=9 and the remainder as r=2, as shown follows:

Similarly, we can write the following relations: Dividend = Divisor × Quotient + Remainder; for each such pair: (i) For the pair: 17, 6: 17 = 6 × 2 + 5 (ii) For the pair: 5, 15: 5 = 15 × 0 + 5 (iii) For the pair: 24, 4: 24 = 4 × 6 + 0

Examples:

Apply the following steps to find the HCF of two positive integers, say a and b, with a > b using Euclid's division algorithm: --->

Find HCF using Euclid's Division Algorithm:

Apply Euclid’s division lemma to a and b, to find whole numbers, q and r such that a = bq + r, where 0 ≤ r < b

Step 1:

If r = 0, then the HCF of a and b is, b. If r ≠ 0, apply the Euclid’s division lemma to b and r.

Step 2:

Repeat the process until the remainder is zero. At this stage, the divisor will be the required HCF.

Step 3:

This algorithm works because HCF (a, b) = HCF (b, r). The symbol HCF (a, b) denotes the HCF of a and b, etc.

Find HCF using Euclid's Division Algorithm:

Solution: Apply the steps below to find HCF --->

Example: Use Euclid’s algorithm to find the HCF of 24 and 36.

There are many applications of Euclid’s division lemma/algorithm related to finding properties of numbers. Here are some examples of these applications:

Applications of Euclid’s division lemma/algorithm

1. Every positive even integer 'm' has the form '2n', where n is an integer. 2. Every positive odd integer 'm' has the form '2n+1', where n is an integer.

Applications of Euclid’s division lemma/algorithm

Read All Topics of Math & Statistics in Details in Hindi & English

MATHPEDIA

STATPEDIA