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))$.
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.