GREATEST COMMON FACTOR - COMPUTING IT MADE EASY, WORD PROBLEMS, EXAMPLES, EXERCISES

Please study  Division  and
Long Division before Greatest Common Factor,
if you have not already done so.

They are prerequisites here.

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.

Can Movies be Learning Tools ?

Do you know Movies provide us
Entertainment, Social interaction,
Laughing Therapy, Learning Tool,
Relaxation, General Well Being ?

To know more, Go to

"Benefits of Movies."

or Go and directly

Download Full Version Movies.

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.

Solved Example 1 of Greatest Common Factor :

Find the G.C.F. of the numbers 16 and 30.

Solution :

                 16 ) 30 ( 1
                      16
                    ------
                      14 ) 16 ( 1
                           14 
                         ------
                    G.C.F.← 2 ) 14 ( 7
                                14
                              -------
                                 0
                              -------

See the Greatest Common Factor finding process
presentation given above.

STEP 1 :

We divide the bigger number (Dividend, 30) by
the smaller number (Divisor, 16)
to get Remainder 14 (quotient being 1).

STEP 2 :

Then, we divide the Divisor (16, becomes Dividend) by the Remainder
(14, becomes Divisor) to get a new Remainder 2 (quotient being 1).

STEP 3 :

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

we divide the Divisor (14, becomes Dividend) by the Remainder
(2, becomes Divisor) to get a new Remainder 0 (quotient being 7).

STEP 4 :

The last Divisor, 2 is the G.C.F.
of the given two numbers 16 and 30.

Thus G.C.F. of 16 and 30 = 2. Ans.

Solved Example 2 of Greatest Common Factor :

Find the G.C.F. of the numbers 45 and 120.

Solution :

                 45 ) 120 ( 2
                       90
                     ------
                       30 ) 45 ( 1
                            30 
                          ------
                    G.C.F.← 15 ) 30 ( 2
                                 30
                               -------
                                  0
                               -------

See the G.C.F. finding process presentation given above.

120 is divided by 45 to get 30 as remainder (quotient being 2).

In the next stage, 30 is divisor and 45 is dividend.
This division gave 15 as remainder (quotient being 1).

In the next stage, 15 is divisor and 30 is dividend.
This division gave 0 as remainder (quotient being 2).

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

Thus G.C.F. of 45 and 120 = 15. Ans.

Solved Example 3 of Greatest Common Factor :

Find the G.C.F. of the numbers 1066 and 46189.

Solution :

                 1066 ) 46189 ( 43
                        45838
                        ------
                          351 ) 1066 ( 3
                                1053 
                               ------
                          G.C.F.← 13 ) 351 ( 27
                                       351
                                      -------
                                         0
                                      -------

See the G.C.F. finding process presentation given above.

46189 is divided by 1066 to get 351 as remainder (quotient being 43).

In the next stage, 351 is divisor and 1066 is dividend.
This division gave 13 as remainder (quotient being 3).

In the next stage, 13 is divisor and 351 is dividend.
This division gave 0 as remainder (quotient being 27).

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

Thus G.C.F. of 1066 and 46189 = 13. Ans.

This division method of finding Greatest Common Factor is
especially useful for finding the G.C.F.of large numbers.

Imagine doing this example 3, by Prime Factorisation.
You will realise the advantage of this division Process
over Prime Factorisation.

2012 phenomenon : Myth or Reality ?

Want to know about "2012 phenomenon."!

There are a variety of popular
"beliefs about the year 2012."

You can get a "Free 2012 Report" also.

Method of finding G.C.F. of more than two numbers

In order to find the G.C.F. of more than two numbers,
first find the G.C.F. of any two of them.

Then, find the G.C.F. of the third number and
the G.C.F.of the first two numbers, so obtained.

Continue this method, in order, till all the numbers are over.

Let us see some Examples.

Solved Example 4 of Greatest Common Factor :

Find the G.C.F. of the numbers 60, 90, 150.

Solution :
First, let us find the G.C.F. of the numbers 60 and 90.

                 60 ) 90 ( 1
                      60
                    ------
             G.C.F. ← 30 ) 60 ( 2
                           60 
                         ------
                            0
                         -------
                    

Now let us find the G.C.F. of 30 and 150.

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.

Solved Example 5 of Greatest Common Factor :

Find the G.C.F. of the numbers 70, 210, 315.

Solution :
First, let us find the G.C.F. of the numbers 70 and 210.

We can see 210 is 3 times 70.
∴ G.C.F. of 70 and 210 = 70.

Now let us find the G.C.F. of 70 and 315.

                 70 ) 315 ( 4
                      280
                    ------
              G.C.F. ← 35 ) 70 ( 2
                            70 
                          ------
                             0
                          ------
                    

∴ G.C.F. of the numbers 70, 210, 315 = 35. Ans.

Solved Example 6 of Greatest Common Factor :

Find the G.C.F. of the numbers 1197, 5320, 4389.

Solution :
First, let us find the G.C.F. of the numbers 1197, 5320.

                 1197 ) 5320 ( 4
                        4788
                        ------
                         532 ) 1197 ( 2
                               1064 
                               ------
                        G.C.F.← 133 ) 532 ( 4
                                      532
                                     -------
                                        0
                                     -------

Thus, G.C.F. of the numbers 1197 and 5320 = 133

Now let us find the G.C.F. of 133 and 4389.

          G.C.F.← 133 ) 4389 ( 33
                        4389
                       ------
                          0
                       ------ 

Thus, the G.C.F. of 133 and 4389 = 133.

∴ The G.C.F. of the numbers 1197, 5320, 4389 = 133. Ans.

Solved Example 7 of Greatest Common Factor :

Find the G.C.F. of the numbers 1701, 2106, 2754.

Solution :
First, let us find the G.C.F. of the numbers 1701, 2106.

                 1701 ) 2106 ( 1
                        1701
                        ------
                         405 ) 1701 ( 4
                               1620 
                              ------
                         G.C.F.← 81 ) 405 ( 5
                                      405
                                     -------
                                        0
                                     -------

Thus, G.C.F. of the numbers 1701, 2106 = 81

Now let us find the G.C.F. of 81 and 2754.

          G.C.F.← 81 ) 2754 ( 34
                       2754
                      ------
                         0
                      ------ 

Thus, the G.C.F. of 81 and 2754 = 81.

∴ The G.C.F. of the numbers 1701, 2106, 2754 = 81. Ans.

Word Problems on Greatest Common Factor

Solved Example 8 of Greatest Common Factor : Word Problems

Find the largest number which can divide 1354, 1866 and 2762 leaving the same remainder 10 in each case

Solution :
Let the reuired number to be found be n.

By data n is the largest number dividing
each of 1354, 1866 and 2762 with remainder 10.

⇒ n is the largest number dividing
each of (1354 - 10), (1866 - 10) and (2762 - 10) exactly.

⇒ n is the G.C.F. of the numbers 1344, 1856, 2752.

Let us first find the G.C.F. of 1344 and 1856.

                 1344 ) 1856 ( 1
                        1344
                        ------
                         512 ) 1344 ( 2
                               1024 
                              ------
                                320 ) 512 ( 1
                                      320
                                     -------
                                      192 ) 320 ( 1
                                            192
                                          -------
                                            128 ) 192 ( 1
                                                  128
                                                -------
                                           G.C.F.← 64 ) 128 ( 2
                                                        128
                                                      -------
                                                         0
                                                      -------  

Thus G.C.F. of 1344 and 1856 = 64.

Now let us find the G.C.F. of 64 and 2752.

          G.C.F.←64 ) 2752 ( 43
                           2752
                           ------
                             0
                          ------     

Thus G.C.F. of 64 and 2752 = 64

∴ G.C.F. of the numbers 1344, 1856, 2752 = 64.

∴ The required number = n = 64. Ans.

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.

First let us find the G.C.F. of 513, 783.

                 513 ) 783 ( 1
                       513
                     ------
                       270 ) 513 ( 1
                             270 
                           ------
                             243 ) 270 ( 1
                                   243
                                 -------
                            G.C.F.← 27 ) 243 ( 9
                                         243
                                        -------
                                           0
                                        -------

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

Now let us find the G.C.F. of 27, 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.

First let us find the G.C.F. of 403, 465.

                 403 ) 465 ( 1
                       403
                      ------
                        62 ) 403 ( 6
                             372 
                           ------
                      G.C.F.← 31 ) 62 ( 2
                                   62
                                -------
                                   0
                                -------

Thus, G.C.F. of 403, 465. = 31.

Now let us find the G.C.F. of 31, 527.

We know 17 x 31 = 527
⇒ 31 is a factor of 527. ⇒ G.C.F. of 31, 527 = 31.

Thus, G.C.F. of 403, 465 and 527 = 31.

∴ The required measure = 31 kg. Ans.

Exercise 1 of Greatest Common Factor

Find the G.C.F. by Division method, of the numbers

(1) 441, 546 (2) 1632, 1088 (3) 1728, 1632 (4) 6239, 7684

(5) 1794, 2346, 4761 (6) 5474, 9775, 11730 (7) 3465, 5460, 6006

For Answers, see at the bottom of the page.

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.

For Answers, see at the bottom of the page.

Answers to Exercise 1 of Greatest Common Factor :

(1) 21 (2) 544 (3) 17 (4) 17 (5) 69 (6) 391 (7) 21

Answers to Exercise 2 of Greatest Common Factor : Word Problems

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