Can we prove the existence of a gcd in $\mathbb Z$ without using division with remainder? 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?


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.
