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?
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 $&gt;0$ closed under subtraction $&gt; 0,\,$ i.e. for all $\rm\,n,m\in S, \,$ $\rm\ n &gt; 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)
I have a unique method to prove the existence of gcd

Since Euclidean Algorithm provides gcd,so proving that Euclidean Algorithm terminates might help us to prove that gcd exists.

So let's start.... Consider "a", "b" such that "a", "b"$\in$ $Z^+$

We know that Euclidean Algorithm ends when remainder becomes "0" ---(1)

Let us assume that Euclidean Algorithm never ends, So according to statement (1) none of remainder should be zero.

Applying euclidean algorithm to "a","b"....

a=bq1+r1, 0&lt; r1 &lt; b

b=r1q2+r2, 0&lt; r2 &lt; r1

r1=r2q3+r3, 0&lt; r3 &lt; r2

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

So continuing the process will give us b>r1>r2>r3>r4>r5>r6..... ∞ .Since b,r1,r2,r3,r4,r5...∞ are positive integers

So we got a infinite sequence of strictly decreasing positive integers ...

But according to statement of infinite descent which is a consequence of well ordering Principle, no such sequence exists.

So we are left with a contradiction!!

Hence Euclidean Algorithm terminates.

Since Euclidean Algorithm provides gcd

So gcd also exists!!!!

Hope it helps