# Prove that gcd exists and it is unique

How can I show using division algorithm on $\mathbb{N}$ that there is a gcd for every pair of number $a,b \in \mathbb{N}$ and this gcd is unique?

-

There are multiple methods, here are 3 :

1) you can show that the euclidian algorithm is a finite sequence (see http://en.wikipedia.org/wiki/Euclidean_algorithm) and thus when it stops you get the pgcd.

2) you can also using the division of $\mathbb{N}$ show that the ring $\mathbb{Z}$ is principal, hence just take a positive generator of the sum of the ideals generated by $a$ and $b$ in $\mathbb{Z}$. This is less elementary but not less illuminating.

3) assuming the existence and unicity of decompositions of $a$ and $b$ has a product of power of prime, you can define the gcd by taking for any prime $v_p(gcd(a,b))=\min (v_p(a),v_p(b))$.

-

You will find an excellent description of the Euclid algorithm and the validity proof in Wikipedia. It cannot be done better by repeating it here.

-

Define $D_a=\{c\in\mathbb{Z}: c\vert a\}$ and $D_b=\{c\in\mathbb{Z}: c\vert a\}$, that is the set of the divisor of $a$ and the divisor of $b$, then $D_a\cap D_b$ is the set of common divisors. Note that $1\in D_a\cap D_b$, so $max( D_a\cap D_b)=max( D_a\cap D_b \cap \mathbb{N})$ and $D_a\cap D_b \cap \mathbb{N}$ is bounded subset of the naturals so the maximum exists, and by definition is unique. You need that $a\neq0$ or $b\neq 0$ so the upper bound is $max\{\vert a\vert,\vert b\vert\}$.

-
Conceptually this proof is wrong (or incomplete), because for gcds "greatest" doesn't mean numerically greatest but, rather, divisibly greatest, i.e. $\rm\:c\:|\:a,b\ \Rightarrow\ c\:|\:(a,b)\:.\:$ In other words $\rm\ c\:|\:a,b\:\ \iff\ c\:|\:(a,b)\:.\quad$ – Bill Dubuque Oct 9 '11 at 16:10
Ok, it depends of the order, but consider that if is the greatest by de division order it doesn't have to be unique, so for uniqueness you ask to $(a,b)\geq 0$. And you could prove that the definition you gave is equivalente to $\(a,b)\vert a$, $\(a,b)\vert b$ and if $c\vert a$,$c\vert b$ then $c\leq (a,b)$. – Frank Murphy Oct 9 '11 at 21:22