Greatest common divisor (GCD), which can also be referred to as Greatest common factor (GCF) or Highest common factor (HCF), is the biggest/greatest/highest number that can divide two or more numbers, without leaving a remainder.

## Methods of finding GCD of two or more numbers

Word Problem: Mr. Otieno plans to organize the Math club of 16 boys and 20 girls what is the biggest number of members each group can have which would have an equal number of boys and girls? To get the answer, find the Greatest Common Factor of 16 and 20.

### Method 1 : Listing Factors

- List all the factors of 16 and 20.

16 : 1 , 2 , 4 , 8 , 16

20 : 1 , 2 , 4 , 5 , 10 , 20

- Get the Common Factor

16 : 1 , 2 , 4

20 : 1 , 2 , 4

- Select the common factor/divisor

GCD = 4

### Method 2: By Prime Factorization

- Find the prime factors of 16 and 20

- Find the common prime factors.

16: 2 x 2

20: 2 x 2

- Find the Product

16: 2 x 2 = 4

20: 2 x 2 = 4

GCD = 4

### Method 3: By Continuous Division

- Write the number horizontally
- Think of prime numbers that 16 and 20 can divide.
- Divide the given numbers by the given prime numbers.
- Write the quotient below the dividends.
- Continue the process until none of the numbers have a common divisor except 1.
**GCD = 2 x 2 = 4**

The same procedures can be used to get GCD of 3 or more numbers.

### Exercise

- Find the greatest common divisor for each set of numbers by listing factors.
- 45, 60
- 16, 20
- 80, 100
- 60, 90
- 16, 30
- 24, 30
- 36, 54
- 14, 63
- 8, 12, 15
- 10, 25, 40
- 20, 30, 40
- 18, 27, 36

- Find the greatest common divisor for each set of numbers by using continuos division.
- 48, 72
- 70, 170
- 36, 40
- 45, 81
- 216, 234
- 220, 242
- 270, 320
- 275, 286
- 384, 432
- 364, 468
- 261, 290
- 265, 424
- 16, 18, 54
- 15, 24, 40
- 22, 65, 121
- 16, 38, 76

- Find the greatest common divisor for each set of expressions.
- 45x
^{2}y^{5},15x^{3}y^{3} - 30x
^{3}y^{7},15x^{6}y^{4} - 8a
^{7}b^{6},6a^{5}b^{2} - 12a
^{6}b^{5},18a^{4}b^{3} - 16x
^{8}y^{12},20x^{9}y^{7} - 36x
^{6}y^{11},24x^{9}y^{8} - 4x
^{2}y^{3},6x^{3}y^{4},8x^{4}y - 10x
^{5}y^{4},5x^{2}y^{2},15x^{3}y^{7}

- 45x
- Chula is campaigning for dining hall captain and plans to distribute some campaign materials: 20 flyers and 16 buttons. She wants each classroom to receive an identical set of campaign materials, without having any materials left over. What is the greatest number of classrooms Chula can distribute materials to?
- Shannon is making identical balloon arrangements for a party. She has 32 maroon balloons, 24 white balloons, and 16 orange balloons. She wants each arrangement to have the same number of each color. What is the greatest number of arrangements that she can make if every balloon is used?