How do you find the gcf using euclidean method?

Answer 1

Suppose you want to find the gcf of 5040 and 1274.

Make a list or a "ladder" starting with 5040 and 1274. Each item after that is the remainder of dividing the two numbers above.

5040

1274

1218 (5040 divided by 1274 leaves a remainder of 1218)

56 (1274 divided by 1218 leaves a remainder of 56)

42 (1218 divided by 56 leaves a remainder of 42)

14 (56 divided by 42 leaves a remainder of 14)

0 (42 divided by 14 leaves a remainder of 0).

When you reach zero, the number before it (in this case 14) is the gcf. The gcf of 5040 and 1274 is 14.

In general:

Let a and b be the two numbers.

repeat while (b >0)

Let c = the remainder of a divided by b

Let a=b

Let b=c

The gcf is a.

Answer 2

A x B/HCF(a,b)