2

Recall the general definition of a gcd in a commutative ring $R$.

For $a \in R$, $\mathcal D(a)$ is the set of elements that divide $a$ and if $S \subset R$, $\mathcal D(S) = \cap_{s \in S} \mathcal D(s)$

We say that $d$ is a gcd of $a$ and $b$ and we write $d \in \gcd(a,b)$ whenever we have $ d \in \mathcal D(a,b) \subset \mathcal D(d) $.

I would like to prove that, within the ring $\mathbb Z$ every pair of natural numbers has a gcd, that is, $\forall a,b \in \mathbb{N} \quad \gcd(a,b) \neq \emptyset $. Of course, they all have a gcd for the order in $\mathbb Z$, in which case I'd like to prove that the greatest common divisor for the order is a (the) greatest common divisor in the purely algebraic sense.

Once done, it almost goes without saying that the gcd is unique. Indeed, since $\forall x,y \in \mathbb N \quad (x|y \implies x \leq y)$, $\quad \mathcal D(a,b)$ is bounded by $\min(a,b)$ and has a unique maximal element. If $a$ and $b$ do have a gcd, then, once again by $x|y \implies x \leq y$ the gcd can only be that maximal element.

Therefore, proving that $a$ and $b$ have a gcd is equivalent to proving that the greatest element of $\mathcal D(a,b)$ (the "usual" greatest common divisor of $a$ and $b$) is a gcd of $a$ and $b$, that is, that every element of $\mathcal D(a,b)$ divides its greatest element.

I'm stuck here.

James Well
  • 1,209
  • I don't understand this sentence: ‘whenever $d \in \mathcal D(a,b) \subset \mathcal D(d)$’. – Bernard Jul 20 '17 at 22:00
  • This means $d$ divides $a$ and $b$ and is divisible by every common divisor of $a$ and $b$. – James Well Jul 20 '17 at 22:02
  • That's not what your formula means. Actually it is ill-formed. – Bernard Jul 20 '17 at 22:04
  • If you do unterstand what I meant, would you mind helping me to reformulate ? – James Well Jul 20 '17 at 22:05
  • @Rob Arthan: you meant $\mathcal D({a, {\color{red}b}})\subset \mathcal D({d})$. – Bernard Jul 20 '17 at 22:23
  • You seem to be lost in your own notation. When you write ${\cal D}(a, b)$, you probably mean ${\cal D}({a, b})$. Defining $\gcd(a, b)$ to be the set of $d$ such that $d \in {\cal D}({a, b}$ and ${\cal D}({a, b}) \subseteq {\cal D}({d})$ is a very convoluted way of defining greatest common divisors. – Rob Arthan Jul 20 '17 at 22:27
  • @Bernard: sure! but that just reinforces my point - convoluted notation encourages errors. – Rob Arthan Jul 20 '17 at 22:28
  • Yes that's exactly what I meant. I thought I'd lighten the notation, as we do when we write $f(x,y)$ instead of $f((x,y))$ when $(x,y)$ is an argument of $f$. We have no trouble writing $(a,b)$ and $(S)$ for ideals generated by subsets or several elements. – James Well Jul 20 '17 at 23:02
  • @James The definition is so $,c\mid a,b,\ldots!! \iff! c\mid \gcd(a,b,\ldots)\ $ i.e they have exactly the same set of common divisors $,c,,$ that is $\ \cal D(a,b\ldots), =, \cal D(\gcd(a,b\ldots))\ \ $ – Bill Dubuque Jul 20 '17 at 23:41
  • @BillDubuque There is "greatest" for the order on $\mathbb Z$ and "greatest" for the partial order that is divisibility. – James Well Jul 20 '17 at 23:44
  • @James My comment refers to the general (divisibility-greatest) definition of gcd. – Bill Dubuque Jul 20 '17 at 23:47
  • @BillDubuque 1st comment : Yes, but $d$ is my $\gcd $, so isn't that what I've written ? 2nd comment : exactly, and in $\mathbb Z$ there is of course a greatest common divisor in the order sense, and I was seeking to prove that that element is the $\gcd $ in the divisibility sense. – James Well Jul 21 '17 at 21:35
  • @James My point was to show you how to say it more clearly. – Bill Dubuque Jul 21 '17 at 21:37
  • Right, I'll edit that, I can tell that I haven't made it clear. Thx – James Well Jul 21 '17 at 21:39
  • I understand well what you are trying to prove (I've written far more on this site about gcds than any other user - including the topic you mention) – Bill Dubuque Jul 21 '17 at 21:56

2 Answers2

1

Euclid's algorithm for computing the GCD can be turned directly into a proof that the any two naturals $a$ and $b$ have a unique GCD, by long induction on $a+b$:

If $a=b$, then their common value is obviously their GCD.

Otherwise, suppose without loss of generality that $a>b$. Then the common divisors of $a-b$ and $b$ are easily seen to be the same as the common divisors of $a$ and $b$. But the induction hypothesis tells us that $a-b$ and $b$ have a unique GCD.

hmakholm left over Monica
  • 286,031
1

$\mathbf Z$ is a P.I.D., hence the ideal $\langle a,b\rangle$ has a generator $d$, and every generator is unique modulo units. The units of $\mathbf Z$ are $\pm 1$, so we can choose the positive generator.

By definition, $a, b\in\langle d\rangle$, so $d\mid a, b$.

On the other hand, we can write $d=ua+vb$ for some $u,v\in\mathbf Z$ since $d\in\langle a,b\rangle$. Let $e$ be a common divisor of $a$ and $b$: we can write $a=a'e$, $b=b'e$, so $$d=ua'e+vb'e=(ua'+vb()e\in\langle e\rangle ,$$ which means $e$ is a divisor of $d$.

Note

This proof is valid for any P.I.D., even if it has no Euclid's algorithm.

Bernard
  • 175,478
  • Oh yes! It only uses that a non-empty set of natural numbers has a smallest element (of course, this property is also used to prove the existence of a Euclidean division). – Bernard Jul 20 '17 at 23:30
  • I think I deleted my question by mistake. It was : Can one prove that $\mathbb Z$ is a PID without using that it is Euclidean ? – James Well Jul 20 '17 at 23:42
  • It was this question indeed and I didn't delete my comment-answer. In short: if $I$ is a non-zero ideal, it is generated by the smallest positive integer it contains. – Bernard Jul 21 '17 at 00:04