# Greatest Common Divisor

## Greatest Common Divisor

If m and n are integers, the greatest divisor shared by m and n is the greatest positive integer that divides both m and n.

### Notation

We use the expression GCD(a, b, c) to refer to the greatest common divisor of the numbers a, b and c.

### Properties

• The GCD is always a positive integer.
• The relationship between the GCD and the LCM:
• Consider: PGCD (m, n) = p and PPCM (m, n) = q
• Then: PGCD (m, n) × PPCM (m, n) = m × n
• And we can write: p × q = m × n
• If the GCD (8, 12) = 4 and PPCM (8, 12) = 24, then: 4 × 24 = 8 × 12.
• By extension, we can find the GCD of two or more polynomials. You must factor them first.
• $$x^{2}$$ – 9 = $$(x$$ + 3)($$x$$ – 3)
$$x^{2}$$ – $$x$$ – 12 = ($$x$$ + 3)($$x$$ – 4)
$$x^{2}$$ + 6$$x$$ + 9 = ($$x$$ + 3)($$x$$ + 3)
Therefore, the GCD of these three polynomials is: ($$x$$ + 3).

### Examples

If div(12) = {1, 2, 3, 4, 6, 12} and div(15) = {1, 3, 5, 15}, then: PGCD(12, 15) = 3.
If div(20) = {1, 2, 4, 5, 10, 20} and div(14) = {1, 2, 7, 14}, then: PGCD(20, 14) = 2.