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, by finding the prime factors of the numbers.

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.

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.

I 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.

Example I(1) :

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.

Example I(2) :

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.

Example I(3) :

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.

II 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.

Example II(1) :

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
-------



Thus, G.C.F. of the numbers 60 and 90 = 30

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

We can see 150 is 5 times 30.

So, 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.

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

Example II(2) :

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.

So, 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
------

Thus, G.C.F. of 70 and 315 = 35.

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

Example II(3) :

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.

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

Example II(4) :

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.

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

For more about G.C.F., go to,

http://www.math-help-ace.com/Greatest-Common-Factor.html