GCD

Let , and be arbitrary integers, and assume that .
Now either and are not zero, or they are both zero, and we consider these possibilities.

Prove ALL parts of the definition of GCD

Case 1: and are not both zero
Let
By definition of GCD, and
and by DIC, for all , . We set and , so
If we rearrange , we find that
So , so is a common divisor of and

Now let be an arbitrary common divisor of and .
Since and , we have by DIC.
Now, , so .

Since and and , then from the definition of gcd, we have . Hence

Case 2: and are both zero
becomes , so .
Thus, , and , giving

Let and be arbitrary integers, and be an arbitrary non-negative integer. Assume that is a common divisor of and , and that there exist integers and such that . We consider the two cases given in the definition of GCD

Case 1: and are both not zero.
Since is a common divisor of and , this means , so

Let be an arbitrary common divisor of and . Hence, and .
By DIC, we have for all integers and .
Therefore
Since , . Then, by bounds by divisibility, we obtain , so by the positivity of we get .
From the definition of GCD,

Case 2:
From the assumptions that there exists integers and such that , we must have , since for all integers and .
Also, is a divisor of , so is a common divisor of and .
Since , then .

We wish to prove that the greatest common divisor and is .

First, we find that is true and are true.

Is turns out that and work, with .

Thus, the

Let , , and be arbitrary integers, and assume that and .
By BL, there exists integers and such that , where .
Since , by DIC we get , which gives .

Prove the statement: For all integers and , and non-negative integers , we have

Let .
We have and , so there exists integers and such that and .
Multiplying these equations by , we obtain , and
Hence, by definition of divisibility, we have and

Also, by BL, there exists integers and such that , and multyplying this equation by gives

Now we have , ,
We conclude from GCD CT that

Let and be arbitrary integers. We prove the two implications.

Assume that . Then, by BL, there exists integers and so that

Assume that there exists integers and such that . Now, and for all integers and , so from GCD CT, we have .

Prove: For all integers and , and all natural numbers , if , then

Let and be arbitrary integers. We prove tis result by induction on , where is the open sentence:

Base Case
The statement is immediately true, because the conclusion and hypothesis will be identical.

Inductive Step
Let be an arbitrary natural number. Assume the inductive hypothesis, .
We wish to prove

Assume .
By CCT (or BL), there exists integers s$ and such that

Since from the inductive hypothesis, we can also use CCT (or BL) again, to give that there exists integers and such that

Multiplying these two equations together gives

Let and .
Then, from the previous equation, and are integers such that
Hence, from the CCT, we deduce that

This result is true for , and hence holds for all integers by POMI

Let and be arbitrary integers, not both zero.
By BL, there exists integers and so that .
since and are not both zero, so we can divide the equation to obtain:

Since , we have and
By definition of divisibility, and
Hence, by CCT,

Prove: for all rational numbers , there exist coprime integers and , with , such that

Let be an arbitrary rational number.
Then we can write in the form , where and are integers with .
Let .
Since , then and are not both zero, so .
We have and , so by the definition of divisibility, and
Hence, from DB GCD, we have , and of course, , where we have divided both numerator and denominator by the non-zero integer

Let and be arbitrary integers, and assume that and .
Since , by CCT (or BL), there exists integers and such that .
Multiplying this equation by gives

Now, we have from the hypothesis, and ,
so by DIC, we have .
Using the previous equation, we obtain .