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?
 A: 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))$.
A: 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.
A: 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\}$.
A: If $d$ is the greates common divisor of $a$ and $b$, then by def.  $d|a$ and $d|b$ and if $c$ is any other common divisor then $c|d$. Now suppose on the contrary. Suppose $a$ and $b$ have another greatest common divisor $d'$ then $d'|d$ and $d|d'$ i.e $d=d'h_1$ and $d'=dh_2$  where $h1, h2 \in \mathbb{N}$
$d'=d'h_1h_2$ which means
$h_1h_2=1$. This is possible only when $h_1=h_2=1$.
So $d=d'$.
Hence proved that the gcd of $a$ and $b$ is unique.
