# Can we prove the existence of a gcd in $\mathbb Z$ without using division with remainder?

For $a,b\in\mathbb Z$ not both $0$, we say $d$ is a gcd of $a$ and $b$ if $d$ is a common divisor of $a$ and $b$ and if every common divisor of $a$ and $b$ divides $d$. With this definition, can we prove the existence of a gcd of two integers (not both zero) without using

• Division with remainder (that is, without proving that $\mathbb Z$ is Euclidean first)

or anything that relies on this, such as

• Euclid's lemma: $p\mid ab\implies p\mid a\vee p\mid b$
• Uniqueness of prime factorisation (which already relies on Euclid's lemma)?

I am aware that "without using ..." is quite vague, so I'll reformulate my question as follows:

Is any proof known of the existence of the gcd which does not rely on the above?

• If Bill D. cannot think of one, I'll believe the answer is no. – punctured dusk Feb 6 '15 at 14:00
• Not an answer, but rather an observation of a route that doesn't work: Even the approach of defining the gcd of $a,b$ integers as the unique positive integer $c$ such that $a\mathbb{Z}+b\mathbb{Z}=c\mathbb{Z}$ uses division with remainder to show that every subgroup of $\mathbb{Z}$ is of the form $n\mathbb{Z}$. – Hayden Feb 6 '15 at 14:03
• By the way, that is not the definition of "a greatest common divisor." You didn't state that $d$ has to be a common divisor... – Thomas Andrews Feb 6 '15 at 14:11

## 4 Answers

One can eliminate explicit use of the division algorithm by replacing its use by its inductive essence (i.e. rewriting the proof in mathematical "assembly language"). Below is one simple way.

The set $\rm\:S\:$ of all integers of the form $\rm\:a\:x + b\:y,\,\ x,y\in \mathbb Z,\:$ is closed under subtraction so, by the Lemma below, every positive $\rm\:n\in S\:$ is divisible by $\rm\:d =$ least positive $\rm\in S,\:$ so $\rm\:a,b\in S\:$ $\Rightarrow$ $\rm\:d\:|\:a,b.\:$ So $\rm\:d\:$ is a common divisor of $\rm\:a,b,\:$ necessarily greatest: $\rm\:c\:|\:a,b\:$ $\Rightarrow$ $\rm\:c\:|\:d = a\,x_1\!+\! b\,y_1\,$ ($\Rightarrow$ $\rm\:c\le d).$

Lemma $\ \$ Let $\,\rm S\ne\emptyset \,$ be a set of integers $>0$ closed under subtraction $> 0,\,$ i.e. for all $\rm\,n,m\in S, \,$ $\rm\ n > m\ \Rightarrow\ n-m\, \in\, S.\,$ Then every element of $\rm\,S\,$ is a multiple of the least element $\rm\:\ell = \min\, S.$

Proof $\$ If not there is a least nonmultiple $\rm\,n\in S,\,$ contra $\rm\,n-\ell \in S\,$ is a nonmultiple of $\rm\,\ell.$

Remark $\$ Using the same idea one can give "elementary" proofs of other theorems of number theory, e.g. the proof of FTA = Fundamental Theorem of Arithmetic due to Zermelo (and others).

However, this is exactly the opposite of what one desires from a pedagogical standpoint. The innate ideal theoretic structure that underlies many of these results should be highlighted - not eliminated (for example, see posts on denominator ideals and order ideals)

• As i said: One can cheat. And I definitely agree with your last paragraph. – MooS Feb 6 '15 at 16:36

Building on previous comments and on MooS' answer, it seems that you definitely need unique factorization to prove the existence of the gcd. But most importanly, I think that one piece of information deserves to be highlighted, namely:

Euclidean domain $\implies$ principal ideal domain $\implies$ unique factorization domain,

and these arrows can't be reversed (i.e., there are rings falsifying each converse). That means, that unique factorization (UF) is strictly weaker than having division with remainder, and thus it could be said that an argument using UF doesn't rely on the algorithm of division. In that sense, the answer to the question stated in the title would be "Yes", but "No" to the one expanded in the text.

• I think your arrows are backwards. – GPerez Feb 6 '15 at 15:33
• @GPerez, absolutely right, typo. Just edited it – Pedro Sánchez Terraf Feb 6 '15 at 15:34

For the greatest common divisor to exist and be well defined, we need a unique factorization domain. So if you do not allow the use of unique prime factorization, it is probably not possible. Of course we could come up with a proof, which implicitly shows unique prime factorization on its way, but this would be cheating.

• I think the existence of gcd as stated implies that you have a principal ideal domain, which in turns implies UFD, isn't it? So without UFD you couldn't do it. – Pedro Sánchez Terraf Feb 6 '15 at 14:11
• Principal ideal domain indeed implies UFD. But we do not need a PID to have a gcd. If you have 2 elements in an UFD, just look at their prime factorizations and for each prime occuring take minimum of the exponents to build the gcd. But one should point out: We need a PID if we want Bezout's Lemma to hold. – MooS Feb 6 '15 at 14:17
• The first sentence is false. For example, the ring of all algebraic integers is Bezout so a GCD domain, but it is not a UFD since it has no irreducibles, since $\, \alpha = \sqrt\alpha \sqrt\alpha.\,$ – Bill Dubuque Feb 6 '15 at 20:32

I have a unique method to prove the existence of gcd

Since Euclidean Algorithm provides gcd,so proving that Euclidean Algorithm terminates might help us to prove that gcd exists.

So let's start.... Consider "a", "b" such that "a", "b"$$\in$$ $$Z^+$$

We know that Euclidean Algorithm ends when remainder becomes "0" ---(1)

Let us assume that Euclidean Algorithm never ends, So according to statement (1) none of remainder should be zero.

Applying euclidean algorithm to "a","b"....

a=bq1+r1, 0< r1 < b

b=r1q2+r2, 0< r2 < r1

r1=r2q3+r3, 0< r3 < r2

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

So continuing the process will give us b>r1>r2>r3>r4>r5>r6..... ∞ .Since b,r1,r2,r3,r4,r5...∞ are positive integers

So we got a infinite sequence of strictly decreasing positive integers ...

But according to statement of infinite descent which is a consequence of well ordering Principle, no such sequence exists.

So we are left with a contradiction!!

Hence Euclidean Algorithm terminates.

Since Euclidean Algorithm provides gcd

So gcd also exists!!!!

Hope it helps 😋