Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 3 down vote accepted

There are multiple methods, here are 3 :

1) you can show that the euclidian algorithm is a finite sequence (see 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))$.

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer
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$ – Bill Dubuque Oct 9 '11 at 16:10
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)$. – Frank Murphy Oct 9 '11 at 21:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.