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?

 A: 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) 
A: 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.
A: 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< r1 < b
b=r1q2+r2, 0< r2 < r1
r1=r2q3+r3, 0< r3 < 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  
A: 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.
