Greatest Common Divisor

[smoky light]

Let ax0 + bx0 = d be the smallest element of the set C defined by: C = {n non-zero Z+ | n = ax + bx for x, y ∈ Z }, where d | a and d | b.

Why does this make d the greatest common divisor of a and b? What guarantees that 2d does not divide a and b? Or more generally, that there is an n.d that does not divide a and b for n ∈ N (d | a and d | b -> d | d.k and d | t.d, k and t are coprime?)? If it does divide, then d is not the greatest common divisor of a and b.

Support video: https://www.youtube.com/watch?v=E_mU_fCmcxc

[unkempt blaze]

If d≠gcd(a,b) then you can find the remainder r such that a=dq+r for which r<d and r=a-(ax0+by0)q=a(1-x0q)+b(y0q). So r=0 which means a is divisible by d. By analogy b is divisible by d. And any other common divisor of a an b also divides d, so it is ≤d.

[smoky light]

QD2718 I think you misunderstood. What I'm trying to understand with the question is that only d that belongs to C divides a and b even considering their multiples (2d, 3d...). With that, the question is restricted (I think) to proving that k and t are prime: d | a and d | b -> d | d.k and d | t.d, k and t are coprime? (d is the smallest element of C)
Sorry if my question was confusing, but I appreciate your attention.

[unkempt blaze]

If you have d=gcd(a,b) then a/d and b/d are of course coprime. Otherwise d would not be their largest common divisor.

And the fact that d is the largest possible common divisor is proved by the fact that any other common divisor of a and b should also be a divisor of d as d=a * x0+b * y0.

[smoky light]

But we are assuming that we do not know that d=gcd(a,b). Normally, it is proven that d | a and d | b using the fact that it is the smallest element of C, which makes the remainder 0. But from there, what guarantees that there is a multiple of d that divides a and b? Because if there were, all the common divisors of a and b would divide this greatest divisor.

[unkempt blaze]

this d=a * x0+b * y0 guarantees that if you take ANY common divisor of a and b then it divides d. So, it is ≤d, which means that d is the largest of them all.

[smoky light]

But this only proves that all divisors of a and b that are not a linear combination of a and b will be smaller than the others that are, so much so that the smallest of them is already larger among those that are not. This is guaranteed. But how can we prove that there is only one number that is a linear combination of a and b such that it divides a and b?

[unkempt blaze]

but we have taken d as a minimal element of C. So it is unique. And we have proved that this d is a common divisor of a and b and it is the largest of all the common divisors (because any other common divisor divides d). So it is gcd. What else?

[smoky light]

You conclude that d is the greatest common divisor of a and b because it really is the greatest common divisor among those that are not a linear combination of a and b (because it is the smallest of all and therefore unique) and with that, you conclude that it is the largest of all and consequently k and t are coprime. You assume that it is the only one because it is the only one that can be proven to divide a and b with certainty, but wouldn't that be incorrect? Because we would be disregarding the question of whether there are more of the form ax + bx such that divides a and b. If not, why not?

[unkempt blaze]

It does not matter which the form of a common divisor is, be it linear combination or not. ANY common divisor of a and b divides d, as it divides a and divides b, so it divides any linear combination of a and b.

[smoky light]

Of course, the form of the common divisor matters. If there is another one of the form ax + bx, it clearly does not divide d, since it is greater than it.

[unkempt blaze]

that s right. Then what does confuse you in the proof, as all types of common divisors whatever they can be, they are less than or equal to d?

[unkempt blaze]

and it means that there are no positive common divisors of a and b of the form ax+by other than d (because all of them would be greater than d, and we showed that any common divisor should be less than or equal to d).