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