Question

Use Euclid’s Division Algorithm to find the Highest Common Factor (H.C.F) of 340 and 412

Answer 1

To find the H.C.F. of 340 and 412. Using Euclid’s division algorithm.

We get 412 = 340 × 1 + 72

The remainder 72 ≠ 0

Again applying Euclid’s division algorithm

340 = 72 × 4 + 52

The remainder 52 ≠ 0.

Again applying Euclid’s division algorithm

72 = 52 × 1 + 20

The remainder 20 ≠ 0.

Again applying Euclid’s division algorithm,

52 = 20 × 2 + 12

The remainder 12 ≠ 0.

Again applying Euclid’s division algorithm.

20 = 12 × 1 + 8

The remainder 8 ≠ 0.

Again applying Euclid’s division algorithm

12 = 8 × 1 + 4

The remainder 4 ≠ 0.

Again applying Euclid’s division algorithm

8 = 4 × 2 + 0

The remainder is zero.

Therefore H.C.F. of 340 and 412 is 4.