gcd as the greatest common factor wrt divisibility partial order relation

Question

Take $60$ and $100$. Their respective divisors lists are:

1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

1, 2, 4, 5, 10, 20, 25, 50, 100

The common divisors are:

1, 2, 4, 5, 10, 20

According to these answers : https://math.stackexchange.com/a/495125/1021982 & https://math.stackexchange.com/a/495127/1021982, the $gcd$ of two numbers is the greatest common factor (greatest in terms of divisibility).

My question is how can we compare the two common factors (in terms of divisibility) $4$ and $5$ when finding the $gcd(60,100)$

$4$ and $5$ are not comparable in terms of divisibility.

Answer 1

One misconception is that the factors are written out in order of magnitude size when we are trying to compare divisibility order, not size order. It might be confusing to do what I am about to do (which is why most text don't) but let's try listing the strings in order of divisibility

The factors of 60 can be in the following "threads":

$1, 2, 4, 12, 60$
$1, 2, 6, 12, 60$
$1, 2, 10, 20, 60$
$1, 2, 10, 30, 60$
$1, 3, 6, 12, 60$
$1, 3, 15, 30, 60$
$1, 5, 10, 20, 60$
$1, 5, 10, 30, 60$
$1, 5, 15, 60$.

Woosh, I probably missed a few. (That was actually more tedious than I thought it would be).

We can't compare $2$ with $3$ or $10$ with $12$ because the do not divide. But we don't have to.

A "total" order is one where any to values can be compared and one will be bigger and the other will be smaller. This is not a total order. But it is a partial order. And it does have transitivity so that if $a\mid b$ and $b\mid c$ we have $a\mid c$.

As such and these are all divisors of $60$ we will have $60\mid 60$ and $60 = 60\times 1$ that $60$ is the "biggest" and top of all the threads.

Now common divisors..... We can compare the common divisors and make the following threads:

$1, 2 , 4, 20$
$1, 2, 10, 20$
$1, 5, 10, 20$

In both cases $20$ is the biggest of all threads. We do not need to compare the incomparable. We do not need to compare $5$ to $2$ or $4$, nor do we have to compare $4$ to $5$ or $10$.

Answer 2

First of all, the "greatest" used in "greatest common divisor" refers to the usual $\le$ relation on the integers (and real numbers), so 4 and 5 are certainly comparable under the relevant relation. However, if we wanted to consider the divisibility relation from here on out:

The definition of the greatest common divisor is a common divisor that's greater than every other common divisor. Nothing about greatest common divisors requires that all common divisors can be compared; the only necessary fact is that every divisor can be compared, under the divisibility relation, to the greatest common divisor. (That fact in turn needs be derived from the definition, which utilizes the $\le$ relation, and properties of divisibility.)

A simpler version of this phenomenon avoids common divisors entirely: the set of divisors of a positive integer $n$ is only partially ordered under the divisibility relation, but $n$ itself is greater than (hence comparable to) every other divisor of $n$.