A Guide to the GRE/Greatest Common Factor

From Wikibooks, open books for an open world
Jump to: navigation, search

Greatest Common Factor[edit]

The greatest common factor of two numbers is the product of the prime factors which they have in common in the same quantities.

For example, the greatest common factor of 60 and 48 is 12.

60 48

         /     \                              /    \
       2        30                               2       24
               /    \                                /    \
             2       15                                   2       12
                     /    \                               /      \
                   3       5                            2        6

/ \

                                                                         2      3

60 is equal to 2(2)(3)(5), while 48 is equal to 2(2)(2)(2)(3). Their shared prime factors are 2, 2 and 3, which equal 12.

Practice[edit]

1. What is the greatest common factor of 180 and 216?

2. If the greatest common factor of 84 and y is 6, and the greatest common factor of 125 and y is 5, what is the lowest possible value for y?

3. Which is larger - the greatest common factor of 120 and 192, or the greatest common factor of 128 and 192?


Answers to Practice Questions[edit]

1. 36

180 216

          /      \               /       \
        2        90          2       108
                 /    \                 /      \
               2     45            2        54
                     /    \                    /    \
                   3      15               3     18
                          /    \                    /    \

3 5 3 6 / \ 2 3

The prime factorization of 180 is 2(2)(3)(3)(5), while the prime factorization of 216 is 2(2)(2)(3)(3)(3). The greatest common factor is the product of the prime factors they have in common in the same quantities - 2(2)(3)(3), or 36.

2. 30

If the greatest common factor of 84 and y is 6, then y at a minimum must have prime factors of 2 and 3. If the greatest common factor of 125 and y is 5, then y must have 5 as a factor too. Thus, y must at least equal 2(3)(5), or 30.

3. The greatest common factor of 128 and 192

This question requires determining the prime factorization of each number.

       120                         192                             128
      /       \                           /        \                                      /       \
   2         60                         2          96                        2         64

/ \ / \ / \

               2      30                        2      48                                     2    32

/ \ / \ / \ 2 15 2 24 8 4 / \ / \ / \ / \ 3 5 2 12 4 2 2 2 / \ / \ 2 6 2 2 / \ 2 3

The prime factorization of 192 is 2(2)(2)(2)(2)(2)(3). Its greatest common factor with 120 is thus 2(2)(2)(3), or 24, while its greatest common factor with 128 is 2(2)(2)(2)(2)(2), or 64.