# the greatest common divisor exists!

for the sake of all of us, let us assert and demonstrate:

$\forall a,b\in{\mathbb{Z}}$ the $GCD(a,b)$ exists and its is unique

Proof:

Consider the auxiliar set $T_{ab}=\{am+bn>0\ :\ m,n\in{\mathbb{Z}}\}$

as a piece of ${\mathbb{N}}$ there exists $c=\min\ T_{ab}$.

But if $c\in T_{ab}$ then $c=a\mu+b\nu$ for some $\mu,\nu\in{\mathbb{Z}}$.

We are going to check that $c$ satisfy the $GCD$ for $a,b$:

Claim: $c|a$

Applying the divisions’ algorithm to this  pair we get

$a=ct+r$ with $0\le r

Since $r=a-ct=a-(a\mu+b\nu)t=a(1-\mu t)+b(-\nu t)\ge0$

If $r>0$ then $r\in T_{ab}$ and $0.

This contradicts the choice for $c$, then $r=0$ and the claim follows.

Similarly $c|b$.

So $c$ is a common divisor of $a,b$.

Uniqueness:

Now suppose that $d$ is a positive integer that $d|a$, $d|b$ and for any other $l$ which divides $a,b$ implies $l|d$.

Then, since $c$ divides both $a,b$ then $c|d$.

Additionally $d|a,\ d|b$ implies $d|a\mu,\ d|b\nu$ and $d|(a\mu+b\nu)$, hence $d|c$

Then $c|d$ and $d|c$. That is $d=\pm c$, but $d=c$ is the only possible.

$\Box$

Filed under cucei math, group theory, numbers

### 15 responses to “the greatest common divisor exists!”

1. Yes, but ….
My adaptation was specialized to Q; and I generalized incorrectly.
Actually my intent was to generalize (in a reasonable manner) the GCD to; extensions of Principal Ideal Rings (PIR) to (a,b),(c,d) where
a,b,c,d are members of P
(a,b)+(c,d)=(d*a+b*c)/bd
(a,b)*(c,d)=(a*c,d*d)

Where according to Newman in “Integer Matrices” page 3 (with very minor substitutions of symbols):
“R a principal ideal ring guarantees the existence of at least one greatest common divisor of \alpha and \beta . We let [\alpha,\beta] denote the ideal consisting of the totality of elements u*\alpha+v*\beta, where u,v run over R independently”

But in order to avoid confounding I replace u,v with summation operators. This is moot for Q; but not for other PIR’s. And upon reflection I am not sure whether this generalizes, specializes, or just has overlap with common GCD/Newman usage.
I am thinking about your responses. The lack of ideals in Q; that’s true but I redefined u,v (multiplication) to be summation.

I wonder whether this is worth following up. (I think I have ADD; everything seems interesting). Perhaps recasting both of our arguments in terms of PIR’s is relevant.

Ray

• Let me check PIR’s.
But wandering: perhaps some extension $E$ of the ring $(\mathbb{Z},+,\cdot)$, in which $E=R[X]/(p)$ and $p$ is not irreducible in $R[X]$?

With $q=q(x)$ irreducible, is it always $R[X]/(q)$ a field?

• I don’t understand. Is R[X] really Z[X] ? And p a member of Z[X] that is not irreducible, and q irreducible a member of Z[X] ?
If so then I can check; this seems to be a standard question in polynomial extensions. It is certainly true that in some cases it doesn’t lead to UFD’s; but I do _think_ they are fields.
Ray

• i was wandering for R and an extensions Z<Q<R<R[X], which by a "magical" procedure gives a subset in $\mathbb{N}$ worth of being g.c.d. … And, i am not a far man crying and/or begging in the streets for some maths spurred somehow…

• oops! that last sentence must be a joke, don’t take it so serious please.

• Got it:
First we have to define a special subset I* of the ring R; I* is the sums of “1” including negatives. This provides a subset indexed by Z but not necessarily in Z.
Then “divides” on the planet math page has to refined to D* ;
a|b (D*(a,b) ) iff the result is in I*. i.e. there exists m in I*, such that ma=b.
Some properties of D* has to be postulated (or proved).
Then the question is:
Given an extension of R, S: RXR.
Will the gcd function on RXR that I defined elsewhere satisfy the GCD properties?

Obviously not in general; but what are the required properties? And does the fractional extension have the gcd function I mentioned?

Are you still interested in an explicit mathematical write up? Or have I driven you and this subject over the edge :)
Ray

• “I found for G.C.D.:”
Why do I have the feeling of a little man in the back of my head curling up and crying?
Nevertheless: There is another article on PlanetMath on GCD domains.
http://planetmath.org/?op=getobj&from=objects&id=5800
Taking that as a starting point my statements would boil down to:
Given G a gcd domain and extending it to the fractional domain H= (G,G) as above then there exists a meaningful interpretation using summation where H is something like a GCD domain.
Perhaps the summation operator replacement is not needed if GCD in H is _defined_ as
gcd(p*s,r*q)/q*s
for (p,g),(r,s) members of H, and p,s,r,q are members of G.
In other words are the mathematical properties of a GCD domain satisfied by this definition on H.
Now this is a statement that can be proved! (at last)

• I slipped in the last comment and did the notational substitutions:
(p,q) ~ p/q
(actually did that earlier as well, in (a,b)+(c,d)=(d*a+b*c)/bd ).
And dropped in g for q in the statement:
for (p,g),(r,s) members of H
(they are so… close together, sigh )

• A side note:
Given the presumptions of the PlanetMath page and treating GCD as a function on two variables:
Is the the GCD operator unique; mod units of a ring?
Ray

2. Perhaps an explicit answer would be enlightening.
Let a=p/q,b=r/s be drawn from a well ordered field and p,q,r,s are drawn from a euclidean domain. and m,n be summation operators.
Then I believe
min(m*a+n*b>0) =gcd(p*s,r*q)/q*s
The formal definition would require considerable work though. Something like taking a euclidean domain extending it to field and then reasoning.
Ray

3. This really sounds dingy but it seems to hang together mathematically.
Would anybody be interested in discussing an extension of gcd(a,b) to;
a,b members of the rationals: Q.
I believe that I concocted a mathematically meaningful interpretation of such a statement. But it’s indirect using an implicit definition.
Side-note: In m*a+n*b the multiplications have to be replaced by summation operations (which yield the same result but are from a different domain) in order to prevent confusion. This also allows an extension to any field; well perhaps countable field.
If you actually look at gcd reasoning the discrete coefficients (members of Z) don’t do anything but set up fences/filters on the underlying field and you can ask for the min(m*a+n*b>0); where m is an summation operator applied to a and similarly for n,b. This can be done on any field.
1) If anybody know of the this let me know.
2) Or anybody having thoughts (or doubts) let me know.
Ray

• i gotta think this challenge : )

• Ray, in a field there is not non-trivial ideals: basically the minimal object which is the g.c.d. is the generator of the (principal) ideal in an euclidean domain. In fact $\mathbb{Q}$ is the field of fractions for the integers, so each nontrivial ideal J in $\mathbb{Q}$ is J$=\mathbb{Q}$. And so there is not minimal element different from zero in J…

• not $\exists\min>0$ for ideals in fields F, we use that the gcd generates an ideal in F. This is the main-core-central idea in the above proof. Actually works for polynomials and another beasts : )