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.