Greatest common divisor

Take 18 and 30\.

The positive divisors of 18 are

The positive divisors of 30 are

Their common divisors are 1, 2, 3 and 6\. The largest is 6\.

That number is called the \\greatest common divisor\\ of 18 and 30\. It is written

In British school mathematics, you may also meet the term \\highest common factor\\, or HCF. In this setting it expresses the same underlying idea.

The greatest common divisor answers a useful question: how much divisibility structure do these two integers share?

For 8 and 15,

So 8 and 15 are coprime.

For 8 and 12,

so they are not coprime.

This measurement becomes especially useful when studying arithmetic progressions.

Suppose we begin at $a$ and repeatedly add $q$:

If $a$ and $q$ have a common divisor $d>1$, then every term in the progression is divisible by $d$.

For example,

starts at 6 and advances in steps of 9\. Because

every term is divisible by 3\.

So, apart from the possibility of the prime 3 itself appearing as an exceptional term in some such progression, a common factor greater than 1 prevents the progression from producing infinitely many primes.

When instead $\gcd(a,q)=1$, there is no shared factor built into every term.

(This does not guarantee that individual terms are prime. It removes one systematic obstruction. Dirichlet's theorem is the much deeper result that says this condition is enough to ensure infinitely many primes in the progression.)

For small integers, we can find a gcd simply by listing divisors. For larger integers, mathematicians use efficient procedures such as the Euclidean algorithm.

The computational method can change; the meaning does not: the gcd is the largest positive integer that divides both numbers exactly.

See also: coprime, arithmetic progression, modular arithmetic, Euler's totient function, prime factorisation, Fundamental Theorem of Arithmetic.