In Elementary Number Theory, it is significant to find the largest positive integer that divides two or more numbers without remainder.

For example it is useful for reducing vulgar fractions to be in lowest terms.

To see an example, to reduce 203⁄377 to lowest terms, we need to know that 29 is the largest positive integer that divides 203 and 377.

Then, we can write 203⁄377 = (7)(29)⁄(13)(29) = 7⁄13.

How do we find that 29 is the largest integer that commonly divides 203 and 377 ?

One way is by determining the prime factorizations of the two numbers and comparing factors. i.e. we need to know 203 = (7)(29) and 377 = (13)(29).

A much more efficient method is the Euclidean algorithm.

The largest positive integer that divides two or more numbers without remainder is called the GREATEST COMMON FACTOR (G.C.F.) of the two or more numbers.

The first method of finding G.C.F. is discussed in Prime Factorisation. The second method based on the Euclidean algorithm, is more efficient and is discussed here.

Its major significance is that it does not require factoring.

Let us again define G.C.F.

Greatest Common Factor, G.C.F.

Greatest Common Factor, G.C.F. of two or more numbers is the greatest number that divides each one of them exactly. or Greatest Common Factor, G.C.F. is the Greatest of the common factors of two or more numbers.

G.C.F. is also known as Greatest Common Divisor, G.C.D.

some times it is also called Highest Common Factor, H.C.F.

Method based on the Euclidean algorithm for finding G.C.F. of two numbers

STEP 1 :

Divide the bigger number (Dividend) by the smaller number (Divisor) to get some Remainder.

STEP 2 :

Then divide the Divisor (becomes Dividend) by the Remainder (becomes Divisor) to get a new Remainder.

STEP 3 :

Continue the process of dividing the Divisors in succession by the Remainders got, till we get the Remainder zero.

STEP 4 :

The last Divisor is the G.C.F. of the given two numbers.

All these steps are shown at one place as a single unit similar to Long Division. The method will be clear by the following examples.

We can see 150 is 5 times 30. ∴ G.C.F. of 30 and 150 = 30.

If one of the two numbers is a factor of the other,then that factor is the G.C.F. of the two numbers.

∴ G.C.F. of the numbers 60, 90, 150 = 30. Ans.

Get The Best Grades With the Least Amount of Effort

Here is a collection of proven tips, tools and techniques to turn you into a super-achiever - even if you've never thought of yourself as a "gifted" student.

The secrets will help you absorb, digest and remember large chunks of information quickly and easily so you get the best grades with the least amount of effort.

If you apply what you read from the above collection, you can achieve best grades without giving up your fun, such as TV, surfing the net, playing video games or going out with friends!

Solved Example 9 of Greatest Common Factor : Word Problems

Find the greatest possible length of a rope which can be used to measure exactly the lengths 5 m 13 cm, 7 m 83 cm, 10 m 80 cm.

Solution : Let l cm be the greatest possible length of the rope which can be used to measure exactly the lengths 5 m 13 cm = 513 cm, 7 m 83 cm = 783 cm, 10 m 80 cm = 1080 cm.

⇒ l is the Greatest common factor ( G.C.F. ) of 513, 783 and 1080.

We know 4 x 27 = 108 ⇒ 40 x 27 = 1080 ⇒ 27 is a factor of 1080. ⇒ G.C.F. of 27, 1080 = 27.

Thus, G.C.F. of 513, 783 and 1080 = 27.

∴ The required length of the rope = 27 cm. Ans.

Solved Example 10 of Greatest Common Factor : Word Problems

Three different containers contain different quantities of milk whose measurements are 403 kg, 465 kg and 527 kg. What biggest measure must be there to measure all different quantities in exact number of times ?

Solution : Let m kg be the biggest measure to measure 403 kg, 465 kg and 527 kg.

⇒ m is the Greatest common factor ( G.C.F. ) of 403, 465 and 527.

Exercise 2 of Greatest Common Factor : Word Problems

(1) Find the largest number which can divide 290, 460 and 552 leaving the remainders 4, 5 and 6 respectively.

(2) Three pieces of timber 42 m, 49 m and 63 m long have to be divided into planks of the same length. What is the greatest possible length of each plank ?

(3) Find the least number of square tiles required to pave the ceiling of a room 15 m 17 cm long and 9 m 2 cm broad.

Answers to Exercise 2 of Greatest Common Factor : Word Problems

(1) 13 (2) 7 m (3) 814

Progressive Learning of Math : Greatest Common Factor

Recently, I have found a series of math curricula (Both Hard Copy and Digital Copy) developed by a Lady Teacher who taught everyone from Pre-K students to doctoral students and who is a Ph.D. in Mathematics Education.

This series is very different and advantageous over many of the traditional books available. These give students tools that other books do not. Other books just give practice. These teach students “tricks” and new ways to think.

These build a student’s new knowledge of concepts from their existing knowledge. These provide many pages of practice that gradually increases in difficulty and provide constant review.

These also provide teachers and parents with lessons on how to work with the child on the concepts.

The series is low to reasonably priced and include