Question

Use Euclid's Division Algorithm to find HCF of:

$26565,25806,20930$

Answer 1

Step 1: Find HCF of the first two numbers i.e. $26565,25806$using Euclid's division algorithm :

HCF means the highest common factors of two or more numbers.

Euclid's division algorithm: For any given positive integers $a\&b$, there exist unique integers $q\&r$ satisfying $a=bq+r,0\le r<b$

Since $26565>25806$ we apply Euclid's Division Algorithm,

$26565=25806\times 1+759$

Again applying Euclid's division algorithm,

Since Remainder $759$≠ $0$,

$25806=759\times 34+0$

Since, the remainder is zero, the process stops.

The divisor at this stage is $759$.

Therefore, the HCF of $26565and25806is759$

Step 2: Find HCF of $20930\&759$using Euclid's division algorithm :

Since $20930>759$ we apply Euclid's Division Algorithm,

$20930=759\times 27+437$

Again applying Euclid's division algorithm,

Since remainder $437$≠$0$

$759=437\times 1+322$

Since remainder, $322$≠$0$ we again apply Euclid's Division Algorithm

$437=322\times 1+115$

Since remainder, $115$≠$0$ we again apply Euclid's Division Algorithm

$322=115\times 2+92$

Since remainder,$92$≠$0$ we again apply Euclid's Division Algorithm

$115=92\times 1+23$

Since remainder, $23$≠$0$ we again apply Euclid's Division Algorithm

$92=23\times 4+0$

Since the remainder is zero the process stops.

Since the divisor at this stage is $23$

Therefore, the HCF of $20930\&759$ is $23$.

Hence, the HCF of $26565,25806,20930$ is $23$.