Greatest common divisor

There are two ways to define the great­est com­mon di­vi­sor (also known as great­est com­mon fac­tor, or high­est com­mon fac­tor), both equiv­a­lent.

The first defi­ni­tion is as the name sug­gests: the GCD of \(a\) and \(b\) is the largest num­ber which di­vides both \(a\) and \(b\).

The sec­ond defi­ni­tion is the more “math­e­mat­i­cal”, be­cause it gen­er­al­ises to ar­bi­trary rings rather than just or­dered rings. The GCD of \(a\) and \(b\) is the num­ber \(c\) such that \(c \mid a\), \(c \mid b\), and when­ever \(d \mid a\) and \(d \mid b\), we have \(d \mid c\). (That is, it is the max­i­mal el­e­ment of the par­tially or­dered set that con­sists of the di­vi­sors of \(a\) and \(b\), or­dered by di­vi­sion.)

Examples

show the two differ­ent defi­ni­tions in ac­tion and how they prepare

Equiv­alence of the definitions

prove this

Re­la­tion to prime factorisations

al­gorithm given ac­cess to prime fac­tori­sa­tions; ex­plain why this is unhelpful

Calcu­lat­ing the GCD efficiently

link to Eu­clidean algorithm

Children:

  • Bézout's theorem

    Bé­zout’s the­o­rem is an im­por­tant link be­tween high­est com­mon fac­tors and the in­te­ger solu­tions of a cer­tain equa­tion.

Parents:

  • Mathematics

    Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.