2
$\begingroup$

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?

  • 0
    @jim Came here to write exactly this. Hello, fellow myopic!2018-11-29

3 Answers 3

3

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

1

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.

1

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\}$.

  • 0
    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)$.2011-10-09