Tracking mistake in the Proof

Question

I was going through this proof related to existence of $\gcd$, I want to know that, is this proof right or wrong??

PROOF:–(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$ belongs to set of positive integers.

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=bq_1+r_1$, $0< r_1 < b$

$b=r_1q_2+r_2$, $0< r_2 < r_1$

$r_1=r_2q_3+r_3$, $0< r_3 < r_2$

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

So continuing the process will give us $b>r_1>r_2>r_3>r_4>r_5>r_6>. . .$

Since $b,r_1,r_2,r_3,r_4,r_5,. . .$ 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!!!!

Answer 1

You can proof existence of GCD for positive integers using prime factorization of both numbers, since GCD equals to product of all primes used for factorizations of both numbers to the minimumum of two powers. If there are no common primes, GCD equals to 1, else it equals to product of common primes to the least of two powers.