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?
-
1$\begingroup$ I'll have to go for an eye test, I thought you wanted a proof that god existed and is unique. $\endgroup$– jimNov 28, 2018 at 22:53
-
$\begingroup$ @jim Came here to write exactly this. Hello, fellow myopic! $\endgroup$– Kilian FothNov 29, 2018 at 8:02
4 Answers
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\}$.
-
$\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.mxOct 9, 2011 at 21:22
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.
-
$\begingroup$ Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. $\endgroup$ Nov 21, 2020 at 10:14