Question

Use Euclid's division algorithm to find
Hcf of 72 and 120

Answer 1

Answer:

24

Step-by-step explanation:

Hcf(72, 120) = 24

solution

set up a division problem where a is larger than b.

a ÷ b = c with remainder r. do the division. then replace a with b, replace b with r and repeat the division. continue the process until r = 0.

120 ÷ 72 = 1 r 48 (120 = 1 × 72 + 48)

72 ÷ 48 = 1 r 24 (72 = 1 × 48 + 24)

48 ÷ 24 = 2 r 0 (48 = 2 × 24 + 0)

when remainder r = 0, the gcf is the divisor, b, in the last equation.

Euclid's Algorithm::

What do you do if you want to find the GCF of more than two very large numbers such as 182664, 154875 and 137688? It's easy if you have a Factoring Calculator or a Prime Factorization Calculator or even the GCF calculator shown above. But if you need to do the factorization by hand it will be a lot of work.

How to Find the GCF Using Euclid's Algorithm

Given two whole numbers, subtract the smaller number from the larger number and note the result.

Repeat the process subtracting the smaller number from the result until the result is smaller than the original small number.

Use the original small number as the new larger number. Subtract the result from Step 2 from the new larger number.

Repeat the process for every new larger number and smaller number until you reach zero.

When you reach zero, go back one calculation: the GCF is the number you found just before the zero result.

$\mathtt \red{QUESTION}\blue\rightarrow$

$\mathtt \blue{Use\: Euclid's \:division \:algorithm\: to\: find\:Hcf \:of \:72\: and \:120}$

$\mathtt \red{ANSWER}\rightarrow\:\green{\underbrace{\underline{240}}}$