Can we prove the existence of a gcd in $\mathbb Z$ without using division with remainder?

Question

For $a,b\in\mathbb Z$ not both $0$, we say $d$ is a gcd of $a$ and $b$ if $d$ is a common divisor of $a$ and $b$ and if every common divisor of $a$ and $b$ divides $d$. With this definition, can we prove the existence of a gcd of two integers (not both zero) without using

• Division with remainder (that is, without proving that $\mathbb Z$ is Euclidean first)

or anything that relies on this, such as

• Euclid's lemma: $p\mid ab\implies p\mid a\vee p\mid b$
• Uniqueness of prime factorisation (which already relies on Euclid's lemma)?

I am aware that "without using ..." is quite vague, so I'll reformulate my question as follows:

Is any proof known of the existence of the gcd which does not rely on the above?

Answer 1

One can eliminate explicit use of the division algorithm by replacing its use by its inductive essence (i.e. rewriting the proof in mathematical "assembly language"). Below is one simple way.

The set $\rm\:S\:$ of all integers of the form $\rm\:a\:x + b\:y,\,\ x,y\in \mathbb Z,\:$ is closed under subtraction so, by the Lemma below, every positive $\rm\:n\in S\:$ is divisible by $\rm\:d = $ least positive $\rm\in S,\:$ so $\rm\:a,b\in S\:$ $\Rightarrow$ $\rm\:d\:|\:a,b.\:$ So $\rm\:d\:$ is a common divisor of $\rm\:a,b,\:$ necessarily greatest: $\rm\:c\:|\:a,b\:$ $\Rightarrow$ $\rm\:c\:|\:d = a\,x_1\!+\! b\,y_1\,$ ($\Rightarrow$ $\rm\:c\le d).$

Lemma $\ \ $ Let $\,\rm S\ne\emptyset \,$ be a set of integers $>0$ closed under subtraction $> 0,\,$ i.e. for all $\rm\,n,m\in S, \,$ $\rm\ n > m\ \Rightarrow\ n-m\, \in\, S.\,$ Then every element of $\rm\,S\,$ is a multiple of the least element $\rm\:\ell = \min\, S.$

Proof $\ $ If not there is a least nonmultiple $\rm\,n\in S,\,$ contra $\rm\,n-\ell \in S\,$ is a nonmultiple of $\rm\,\ell.$

Remark $\ $ Using the same idea one can give "elementary" proofs of other theorems of number theory, e.g. the proof of FTA = Fundamental Theorem of Arithmetic due to Zermelo (and others).

However, this is exactly the opposite of what one desires from a pedagogical standpoint. The innate ideal theoretic structure that underlies many of these results should be highlighted - not eliminated (for example, see posts on denominator ideals and order ideals)

Answer 2

For the greatest common divisor to exist and be well defined, we need a unique factorization domain. So if you do not allow the use of unique prime factorization, it is probably not possible. Of course we could come up with a proof, which implicitly shows unique prime factorization on its way, but this would be cheating.

Answer 3

Building on previous comments and on MooS' answer, it seems that you definitely need unique factorization to prove the existence of the gcd. But most importanly, I think that one piece of information deserves to be highlighted, namely:

Euclidean domain $\implies$ principal ideal domain $\implies$ unique factorization domain,

and these arrows can't be reversed (i.e., there are rings falsifying each converse). That means, that unique factorization (UF) is strictly weaker than having division with remainder, and thus it could be said that an argument using UF doesn't rely on the algorithm of division. In that sense, the answer to the question stated in the title would be "Yes", but "No" to the one expanded in the text.