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?

$\endgroup$
2
  • 1
    $\begingroup$ I'll have to go for an eye test, I thought you wanted a proof that god existed and is unique. $\endgroup$
    – jim
    Nov 28, 2018 at 22:53
  • $\begingroup$ @jim Came here to write exactly this. Hello, fellow myopic! $\endgroup$ Nov 29, 2018 at 8:02

4 Answers 4

3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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$ $\endgroup$ Oct 9, 2011 at 16:10
  • $\begingroup$ 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)$. $\endgroup$
    – Math.mx
    Oct 9, 2011 at 21:22
-1
$\begingroup$

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.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .